Форум программистов, компьютерный форум CyberForum.ru

Кэширование рекурсии - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 15, средняя оценка - 4.93
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
12.08.2011, 12:39     Кэширование рекурсии #1
Доброго времени суток.
Есть задача.
Ириска весит X грамм, мандарин – Y грамм, пряник – Z грамм.

Требуется написать программу, которая определит, сколько различных вариантов подарков весом ровно W грамм может сделать Дед Мороз.
Сделать хотелось именно рекурсией(с циклами тривиально слишком), но я наткнулся на подводный камень - значения вычислялись по несколько раз и это приводило к неверному ответу. Додумался только до матрицы, в которой хранилась информация, вычислял ли я эти значения.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <fstream>
 
int x, y, z, w;
 
const int SIZE = 9999;
char was_here[SIZE][SIZE];
 
int f(int a = 0, int b = 0){
    if (a * x + b * y > w || was_here[a][b])
        return 0;
    
    was_here[a][b] = 1;
    return f(a + 1, b) + f(a, b + 1) + ( (w - a * x - b * y) % z == 0 );
}
    
int main(){
    std::fstream("input.txt") >> x >> y >> z >> w;
    std::ofstream("output.txt") << f();
}
Но это во-первых быдлокод, во-вторых жрет много памяти, в-третьих для нового использования придется обнулять матрицу, в-четвертых размер матрицы ограничен.
Поэтому вопрос - есть ли лучшие способы узнать, вычислялось ли то или иное значение?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.08.2011, 12:39     Кэширование рекурсии
Посмотрите здесь:

C++ из рекурсии - цикл
По поводу рекурсии C++
рекурсии... C++
C++ Рекурсии.
C++ Инкремент в рекурсии
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
solar_wind
 Аватар для solar_wind
740 / 731 / 39
Регистрация: 06.07.2009
Сообщений: 2,937
Завершенные тесты: 1
12.08.2011, 12:52     Кэширование рекурсии #2
Циклом тривиально? Это как раз рекурсией тривиально и глупо....если значение переборов будет большое, то тебя ждет переполнение стека.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
12.08.2011, 12:56  [ТС]     Кэширование рекурсии #3
Цитата Сообщение от vitaly1981 Посмотреть сообщение
Циклом тривиально? Это как раз рекурсией тривиально и глупо...
Нет... Тривиально в смысле слишком просто и неинтересно. Про то, что рекурсию не стоит применять в реальных программах я знаю, но уметь ею пользоваться-то надо =) Это учебная задача, в которой ограничения позволяют воспользоватся рекурсией, т.е. стэк не переполнится.
DoZZer_
11 / 11 / 1
Регистрация: 09.08.2011
Сообщений: 53
12.08.2011, 16:02     Кэширование рекурсии #4
Что-то накликал, только производительностью и удобством не блещет )

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
//
 
#include "stdafx.h"
#include <iostream>
 
using namespace std ;
 
int _tmain(int argc, _TCHAR* argv[])
{
 
    float w_iriska, w_mand, w_pryan, all_pres ;
    int iris_max, mand_max, pryan_max, ves;
 
    cout << "Введите вес ириски : " ; cin >> w_iriska ; cout << "Мандарин : " ; cin >> w_mand ; cout << "Пряник : " ; cin >> w_pryan ;
    cout << " Вес всего подарка : " ; cin >> all_pres ;
 
    if (w_iriska > 0 && w_mand > 0 && w_pryan > 0 && all_pres > 0) {} else {cout << "Не жадничать ! "; return 1; }
 
    iris_max = (int) all_pres / w_iriska ;          //задаю мах количество ирисок / мандарин / пряников, которые можно положить в данный общий вес по отдельности
    mand_max = (int) all_pres / w_mand ;
    pryan_max = (int) all_pres / w_pryan ;
 
    if(!iris_max && !mand_max && !pryan_max ) {cout << "Ваш общий подарок слишком мал, увеличьте общий вес. "; return 1 ;}
    
 
    for(int tek_iris = 0 ; tek_iris <= iris_max ; tek_iris++ )          //прохожу по элементам цикла, сравнивая их с общим весом
        for(int tek_mand = 0 ; tek_mand <= mand_max ; tek_mand++)
            for(int tek_pryan = 0, stopp = 0; tek_pryan <= pryan_max && !stopp ; tek_pryan++) //если больше - прекращаю ход по данной ветви
            { 
                ves = tek_iris * w_iriska + tek_mand * w_mand + tek_pryan * w_pryan ;
                if( ves >= all_pres ) 
                { 
                        if (ves == all_pres) 
                    { 
                        cout << "Вариант :  ирис: " << tek_iris << ", мандарин: " << tek_mand << ", пряник: " << tek_pryan << endl ;  //вывожу количество мандаринов и т.п.
                        stopp = 1 ;
                    }
                        else{ stopp = 1 ; }
                }
            }
 
 
        return 0;
}
Оцените что ли, полезно будет узнать свои ошибки)

Добавлено через 18 минут
З.Ы.: diagon, а у вас в этой рекурсии переменная Z вообще меняется? Или вы ее меняете из сохраненной матрицы в текстовике?
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
12.08.2011, 16:07  [ТС]     Кэширование рекурсии #5
Цитата Сообщение от DoZZer_ Посмотреть сообщение
diagon, а у вас в этой рекурсии переменная Z вообще меняется? Или вы ее меняете из сохраненной матрицы в текстовике?
Нет, я ее вычисляю из первых двух.
Z = W - X - Y;
И в общем-то код проходит все тесты, меня интересуют только альтернативные способы решения с помощью рекурсии...
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
12.08.2011, 16:18     Кэширование рекурсии #6
Создавать на стеке матрицу объёмом 100 мегабайт это немного самонадеянно...

Добавлено через 5 минут
Тем более, что в ней мусор.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
12.08.2011, 16:23  [ТС]     Кэширование рекурсии #7
Цитата Сообщение от Deviaphan Посмотреть сообщение
Создавать на стеке матрицу объёмом 100 мегабайт это немного самонадеянно...
Добавлено через 5 минут
Тем более, что в ней мусор.
Кстати странно, матрица 100 метров вешает, а в информации о сданной задаче написано, что задача всего 4.5 мегабайта съела...
А вот мусора в ней нету, глобальная область же.
Ну я и сам пониманию, что способ не айс, поэтому и спрашиваю - как по другому можно решить проблему с повторяющимися вычислениями?
Вопрос относится к рекурсии вообще, а не к конкретно этой задаче, ее скорее как пример привел.
Noname2512
4 / 4 / 1
Регистрация: 25.06.2010
Сообщений: 106
12.08.2011, 16:33     Кэширование рекурсии #8
Цитата Сообщение от vitaly1981 Посмотреть сообщение
то тебя ждет переполнение стека.
вот вот, че делать если переполнение стека в этой ф-ии
C++
1
2
3
4
5
6
7
unsigned long long int nod  (unsigned long long int a,unsigned long long int b)
{
    unsigned long long int p;
    if (a*b == 0) return max(a,b);
    else p = nod (max(a,b)-min(a,b),min(a,b));
    return p;
}
из-за чего возникает переполнение и как его обойти ?
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
12.08.2011, 16:41  [ТС]     Кэширование рекурсии #9
Цитата Сообщение от Noname2512 Посмотреть сообщение
вот вот, че делать если переполнение стека в этой ф-ии
C++
1
2
3
4
5
6
7
unsigned long long int nod  (unsigned long long int a,unsigned long long int b)
{
    unsigned long long int p;
    if (a*b == 0) return max(a,b);
    else p = nod (max(a,b)-min(a,b),min(a,b));
    return p;
}
из-за чего возникает переполнение и как его обойти ?
Во-первых, что такое unsigned long long int =)
Во-вторых, здесь-то на кой рекурсия
C++
1
2
3
4
unsigned long long gcd(unsigned long long a, unsigned long long b){
    while (b^=a^=b^=a%=b);
    return a;
}
Mayonez
 Аватар для Mayonez
379 / 271 / 20
Регистрация: 26.12.2009
Сообщений: 875
13.08.2011, 14:11     Кэширование рекурсии #10
DoZZer_, Ваш пример - это не рекурсия

Добавлено через 2 часа 7 минут
Цитата Сообщение от diagon Посмотреть сообщение
Поэтому вопрос - есть ли лучшие способы узнать, вычислялось ли то или иное значение?
есть, если рекурсивное углубление контролируемое
возьмем, например, рекурсивную функцию вычысления факториала
мы всегда знаем, что получим на следующем уровне
поэтому, нужно написать такую рекурсию, которая бы не допускала
Цитата Сообщение от diagon Посмотреть сообщение
значения вычислялись по несколько раз
Olga_
 Аватар для Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
13.08.2011, 14:20     Кэширование рекурсии #11
Задача вроде бы с диофантовыми уравнениями связана, разубедите меня, если я не права
Mayonez
 Аватар для Mayonez
379 / 271 / 20
Регистрация: 26.12.2009
Сообщений: 875
13.08.2011, 14:25     Кэширование рекурсии #12
Olga_,
aX + bY + cZ = W
ну... да
Olga_
 Аватар для Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
13.08.2011, 14:31     Кэширование рекурсии #13
Цитата Сообщение от Mayonez Посмотреть сообщение
Olga_,
aX + bY + cZ = W
ну... да
И сначала делается проверка: если НОД(a,b,c) не делит число W, то уравнение не имеет решений в целых числах.
Mayonez
 Аватар для Mayonez
379 / 271 / 20
Регистрация: 26.12.2009
Сообщений: 875
13.08.2011, 18:12     Кэширование рекурсии #14
вот рекурсивное решение. Проверь, может, где напартачил
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
 
using namespace std;
 
int m[3];
 
int gift(int step, int w)
{
    if(w == 0)
        return 1;
    if(w > 0)
    {
        switch(step)
        {
        case 0:
            return gift(0, w-m[0]) + gift(1, w-m[1])+ gift(2, w-m[2]);
        case 1:
            return gift(1, w-m[1]) + gift(3, w-m[2]);
        case 2: 
            if (w%m[2] == 0)
                return 1;
            else
                return 0;
        }
    }
    return 0;
}
 
int main()
{
    int w;
    cin >> m[0]
        >> m[1]
        >> m[2]
        >> w;
    for(int i = 0; i < 1; i++)
        for(int j = 0; j < 2-i; j++)
            if(m[j] > m[j+1])
            {
                m[j] = m[j] + m[j+1];
                m[j+1] = m[j] - m[j+1];
                m[j] = m[j] - m[j+1];   
            }
    cout << gift(0, w) << endl;
    return 0;   
}
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
13.08.2011, 18:17  [ТС]     Кэширование рекурсии #15
Цитата Сообщение от Mayonez Посмотреть сообщение
вот рекурсивное решение. Проверь, может, где напартачил
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
 
using namespace std;
 
int m[3];
 
int gift(int step, int w)
{
    if(w == 0)
        return 1;
    if(w > 0)
    {
        switch(step)
        {
        case 0:
            return gift(0, w-m[0]) + gift(1, w-m[1])+ gift(2, w-m[2]);
        case 1:
            return gift(1, w-m[1]) + gift(3, w-m[2]);
        case 2: 
            if (w%m[2] == 0)
                return 1;
            else
                return 0;
        }
    }
    return 0;
}
 
int main()
{
    int w;
    cin >> m[0]
        >> m[1]
        >> m[2]
        >> w;
    for(int i = 0; i < 1; i++)
        for(int j = 0; j < 2-i; j++)
            if(m[j] > m[j+1])
            {
                m[j] = m[j] + m[j+1];
                m[j+1] = m[j] - m[j+1];
                m[j] = m[j] - m[j+1];   
            }
    cout << gift(0, w) << endl;
    return 0;   
}
Странно, но на первом же тесте заваливается, хотя тест из примера проходит.
И вообще, код из первого поста полностью рабочий, но неэффективный.
Mayonez
 Аватар для Mayonez
379 / 271 / 20
Регистрация: 26.12.2009
Сообщений: 875
13.08.2011, 18:30     Кэширование рекурсии #16
а так?
код
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
 
using namespace std;
 
int m[3];
 
int gift(int step, int w)
{
    if(w == 0)
        return 1;
    if(w > 0)
    {
        switch(step)
        {
        case 0:
            return gift(0, w-m[0]) + gift(1, w-m[1])+ gift(2, w-m[2]);
        case 1:
            return gift(1, w-m[1]) + gift(3, w-m[2]);
        case 2: 
            if (w%m[2] == 0)
                return 1;
            else
                return 0;
        }
    }
    return 0;
}
 
int main()
{
    int w;
    cin >> m[0]
        >> m[1]
        >> m[2]
        >> w;
    for(int i = 0; i < 2; i++)
        for(int j = 0; j < 2-i; j++)
            if(m[j] > m[j+1])
            {
                m[j] += m[j+1];
                m[j+1] = m[j] - m[j+1];
                m[j] -= m[j+1]; 
            }
    cout << gift(0, w) << endl;
    return 0;   
}
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
13.08.2011, 18:49  [ТС]     Кэширование рекурсии #17
Цитата Сообщение от Mayonez Посмотреть сообщение
а так?
код
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
 
using namespace std;
 
int m[3];
 
int gift(int step, int w)
{
    if(w == 0)
        return 1;
    if(w > 0)
    {
        switch(step)
        {
        case 0:
            return gift(0, w-m[0]) + gift(1, w-m[1])+ gift(2, w-m[2]);
        case 1:
            return gift(1, w-m[1]) + gift(3, w-m[2]);
        case 2: 
            if (w%m[2] == 0)
                return 1;
            else
                return 0;
        }
    }
    return 0;
}
 
int main()
{
    int w;
    cin >> m[0]
        >> m[1]
        >> m[2]
        >> w;
    for(int i = 0; i < 2; i++)
        for(int j = 0; j < 2-i; j++)
            if(m[j] > m[j+1])
            {
                m[j] += m[j+1];
                m[j+1] = m[j] - m[j+1];
                m[j] -= m[j+1]; 
            }
    cout << gift(0, w) << endl;
    return 0;   
}
Тоже нет... Ну там входные и выходные данные из файлов берутся, я просто в начало кода поставил
freopen'ы, может из-за этого.
Вообще вот условие
http://********/index.asp?main=task&id_task=317
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
15.08.2011, 19:26     Кэширование рекурсии
Еще ссылки по теме:

C++ Использование рекурсии
C++ Возврат рекурсии
C++ Ошибка в рекурсии

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Mayonez
 Аватар для Mayonez
379 / 271 / 20
Регистрация: 26.12.2009
Сообщений: 875
15.08.2011, 19:26     Кэширование рекурсии #18
diagon, нашел две опечатки, дописал комментарии, посмотрел условие - вот окончательная версия:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <fstream>
 
using namespace std;
 
int m[3];
 
//w - ГўГҐГ±, êîòîðûé ГҐГ±ГІГј Гў Г°Г*ñïîðÿæåГ*ГЁГЁ ГґГіГ*êöèè
//step - Г*îìåð ïîäГ*ðêГ* ГЁ ГёГ*ГЈ óãëóáëåГ*ГЁГї
int gift(int step, int w)
{
    if(w == 0)
        return 1;
    //åñëè ìîæГ*Г® ñäåëГ*ГІГј ГҐГ№ГҐ îäèГ* ГўГ*ðèГ*Г*ГІ ïîäГ*ðêГ*
    if(w > 0)
    {
        switch(step)
        {
        case 0:
            //ôîðìèðóåì ГўГ*ðèГ*Г*ГІГ» Г± òðåõ
            return gift(0, w-m[0]) + gift(1, w-m[1])+ gift(2, w-m[2]);
        case 1:
            //Г± äâóõ
            return gift(1, w-m[1]) + gift(2, w-m[2]);
        case 2: 
            //ïîñêîëüêó Г¬Г*Г±Г±ГЁГў áûë îòñîðòèðîâГ*Г* ГЇГ® Г*åóáûâГ*Г*ГЁГѕ,
            //ГІГ® Г*Г* ýòîì ГЅГІГ*ГЇГҐ îñòГ*ëñÿ òîëüêî òðåòèé ïîäГ*ðîê
            //ГўГҐГ± äîëæåГ* áûòü ðîâГ*Г® w ïîýòîìó èëè îäèГ* ГўГ*ðèГ*Г*ГІ  
            if (w%m[2] == 0)
                return 1;
            else
            //èëè Г*îëü
                return 0;
        }
    }
    return 0;
}
 
int main()
{
    ifstream fin("input.txt");
    int w;
    fin >> m[0]
        >> m[1]
        >> m[2]
        >> w;
    //ñîðòèðóåì ГЇГ® Г*åóáûâГ*Г*ГЁГѕ
    for(int i = 0; i < 2; i++)
        for(int j = 0; j < 2-i; j++)
            if(m[j] > m[j+1])
            {
                m[j] += m[j+1];
                m[j+1] = m[j] - m[j+1];
                m[j] -= m[j+1]; 
            }
    //âûâîäèì ðåçóëüòГ*ГІ
    ofstream fout("output.txt");
    fout << gift(0, w) << endl;
    return 0;   
}
Yandex
Объявления
15.08.2011, 19:26     Кэширование рекурсии
Ответ Создать тему
Опции темы

Текущее время: 14:02. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru