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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 15, средняя оценка - 4.93
diagon
Higher
1929 / 1195 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
#1

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

12.08.2011, 12:39. Просмотров 2012. Ответов 17
Метки нет (Все метки)

Доброго времени суток.
Есть задача.
Ириска весит 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();
}
Но это во-первых быдлокод, во-вторых жрет много памяти, в-третьих для нового использования придется обнулять матрицу, в-четвертых размер матрицы ограничен.
Поэтому вопрос - есть ли лучшие способы узнать, вычислялось ли то или иное значение?
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.08.2011, 12:39
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Кэширование рекурсии (C++):

рекурсии... - C++
задание: Во входном файле задано без ошибок логическое выражение следующего вида : &lt;логическое выражение&gt;::=...

Возврат рекурсии - C++
Подскажите пожалуйста почему при выполнении второго for возвращается одно и то же значение.void r(int* ar,int n) { if(n==1) return; ...

из рекурсии - цикл - C++
помогите убрать рекурсию и поставить while. int perest(int l,int **a,int **r,int *p,int n,int &amp;sum,int &amp;max) { int i,temp; ...

Ошибка в рекурсии - C++
почему то переменная y не меняется во время рекурсии. что за? #include &lt;iostream&gt; using namespace std; int n, m, a; int f(...

Избавиться от рекурсии - C++
Каким способом лучше всего избавиться от рекурсии ?

нужен ли while в рекурсии? - C++
Сказали переделать код, нужно что то сделать с while. Что не так объясните) #include &lt;stdio.h&gt; #include &lt;conio.h&gt; #include...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
solar_wind
756 / 747 / 42
Регистрация: 06.07.2009
Сообщений: 2,969
Завершенные тесты: 1
12.08.2011, 12:52 #2
Циклом тривиально? Это как раз рекурсией тривиально и глупо....если значение переборов будет большое, то тебя ждет переполнение стека.
0
diagon
Higher
1929 / 1195 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
12.08.2011, 12:56  [ТС] #3
Цитата Сообщение от vitaly1981 Посмотреть сообщение
Циклом тривиально? Это как раз рекурсией тривиально и глупо...
Нет... Тривиально в смысле слишком просто и неинтересно. Про то, что рекурсию не стоит применять в реальных программах я знаю, но уметь ею пользоваться-то надо =) Это учебная задача, в которой ограничения позволяют воспользоватся рекурсией, т.е. стэк не переполнится.
0
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 вообще меняется? Или вы ее меняете из сохраненной матрицы в текстовике?
0
diagon
Higher
1929 / 1195 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
12.08.2011, 16:07  [ТС] #5
Цитата Сообщение от DoZZer_ Посмотреть сообщение
diagon, а у вас в этой рекурсии переменная Z вообще меняется? Или вы ее меняете из сохраненной матрицы в текстовике?
Нет, я ее вычисляю из первых двух.
Z = W - X - Y;
И в общем-то код проходит все тесты, меня интересуют только альтернативные способы решения с помощью рекурсии...
0
Deviaphan
Делаю внезапно и красиво
Эксперт C++
1287 / 1221 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
12.08.2011, 16:18 #6
Создавать на стеке матрицу объёмом 100 мегабайт это немного самонадеянно...

Добавлено через 5 минут
Тем более, что в ней мусор.
0
diagon
Higher
1929 / 1195 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
12.08.2011, 16:23  [ТС] #7
Цитата Сообщение от Deviaphan Посмотреть сообщение
Создавать на стеке матрицу объёмом 100 мегабайт это немного самонадеянно...
Добавлено через 5 минут
Тем более, что в ней мусор.
Кстати странно, матрица 100 метров вешает, а в информации о сданной задаче написано, что задача всего 4.5 мегабайта съела...
А вот мусора в ней нету, глобальная область же.
Ну я и сам пониманию, что способ не айс, поэтому и спрашиваю - как по другому можно решить проблему с повторяющимися вычислениями?
Вопрос относится к рекурсии вообще, а не к конкретно этой задаче, ее скорее как пример привел.
0
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;
}
из-за чего возникает переполнение и как его обойти ?
0
diagon
Higher
1929 / 1195 / 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;
}
0
Mayonez
380 / 272 / 21
Регистрация: 26.12.2009
Сообщений: 875
13.08.2011, 14:11 #10
DoZZer_, Ваш пример - это не рекурсия

Добавлено через 2 часа 7 минут
Цитата Сообщение от diagon Посмотреть сообщение
Поэтому вопрос - есть ли лучшие способы узнать, вычислялось ли то или иное значение?
есть, если рекурсивное углубление контролируемое
возьмем, например, рекурсивную функцию вычысления факториала
мы всегда знаем, что получим на следующем уровне
поэтому, нужно написать такую рекурсию, которая бы не допускала
Цитата Сообщение от diagon Посмотреть сообщение
значения вычислялись по несколько раз
1
Olga_
841 / 183 / 16
Регистрация: 01.08.2011
Сообщений: 502
13.08.2011, 14:20 #11
Задача вроде бы с диофантовыми уравнениями связана, разубедите меня, если я не права
0
Mayonez
380 / 272 / 21
Регистрация: 26.12.2009
Сообщений: 875
13.08.2011, 14:25 #12
Olga_,
aX + bY + cZ = W
ну... да
0
Olga_
841 / 183 / 16
Регистрация: 01.08.2011
Сообщений: 502
13.08.2011, 14:31 #13
Цитата Сообщение от Mayonez Посмотреть сообщение
Olga_,
aX + bY + cZ = W
ну... да
И сначала делается проверка: если НОД(a,b,c) не делит число W, то уравнение не имеет решений в целых числах.
0
Mayonez
380 / 272 / 21
Регистрация: 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;   
}
0
diagon
Higher
1929 / 1195 / 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;   
}
Странно, но на первом же тесте заваливается, хотя тест из примера проходит.
И вообще, код из первого поста полностью рабочий, но неэффективный.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.08.2011, 18:17
Привет! Вот еще темы с ответами:

По поводу рекурсии - C++
Обязательно ли использовать, если рекурсивно проще чем итеративно или же нет? Пытаюсь полностью понять рекурсию и как-то не особо понимаю....

сложности по рекурсии в С++ - C++
Правильно ли, что в функции: { if (number &lt; 0) { cout &lt;&lt; '-' &lt;&lt; endl; super_write_vertical(abs(number)); } else if...

Ошибка в Рекурсии с++ - C++
Здравствуйте,у меня в данном коде выбивает ошибку в строке 23 .В рекурсии я не силён и прошу вашей помощи в решении данной...

Рекурсия от рекурсии - C++
Люди, помогите! Я в с++ относительно недавно, в паскале-делфи никаких проблем не было. Значит мне нужно: int pekypc() { ... ...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
13.08.2011, 18:17
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru