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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ чтение строки http://www.cyberforum.ru/cpp-beginners/thread341379.html
а не не ниче))
C++ Нужна помощь с классом Вот напечатал это: #include <iostream> #define maxN 10 //количество вершин using namespace std; class directed_graph { public: class directed_graph next; http://www.cyberforum.ru/cpp-beginners/thread341377.html
Правильно ли я написал? C++
Начал изучать С++. Книга "Язык программирования С++. Лекции и упражнения". Хочется узнать насколько правильно я пишу код. Вот два первых задания: #include <iostream> #include <locale> double astrUnits (double); int main() { setlocale(LC_ALL,"Rus");
C++ Расскажите пожалуйста про флаги
Доброго времени суток. Помогите пожалуйста разобраться с фалагми. Вот код: #include <iostream> #define ID_F 1001 #define ID_D 1002 #define ID_E 1003 using namespace std; int main() { int n = ID_F; if(n&ID_F)
C++ как можно ипользовать многомерный массив? http://www.cyberforum.ru/cpp-beginners/thread341343.html
Изучил массивы и стало интересно,как можно использовать многомерные массивы, в книги не написано про их использование а только упомянуто их существование.
C++ Использование указателя на объект шаблонного класса в шаблонном классе. Всем привет! Мне нужно реализовать граф. Начал с вершин и ребер, причем и ребра и вершины - шаблонные классы, для того чтобы и ребро и вершина могли содержать разные данные. В ребре указатели на 2 вершины. Класс вершины: template <class T> class Vertex { private: char* name; T data; подробнее

Показать сообщение отдельно
diagon
Higher
1924 / 1190 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2

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

12.08.2011, 12:39. Просмотров 1949. Ответов 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();
}
Но это во-первых быдлокод, во-вторых жрет много памяти, в-третьих для нового использования придется обнулять матрицу, в-четвертых размер матрицы ограничен.
Поэтому вопрос - есть ли лучшие способы узнать, вычислялось ли то или иное значение?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru