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

Динамическое программирование - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Массивы. Найти наибольший и наименьший элементы, среди расположенных на главной и побочной диагоналях http://www.cyberforum.ru/cpp-beginners/thread848745.html
Заполнить матрицу А размера 10*10 случайными числами от -5 до 23. Найти наибольший и наименьший элементы, среди расположенных на главной и побочной диагоналях
C++ Работа с XML C++ Есть файл XML, его необходимо считать и разобрать по переменным, т.е. например BlendMode="norm" в переменную (string)BMode, но не столь критично, главное чтобы удобно было работать, т.к. таких данных будет очень много, и еще как лучше обрабатывать такого типа данные: Rect="{X=915,Y=132,Width=109,Height=143}" , спасибо Файл: <?xml version="1.0" encoding="UTF-8"?> <!DOCTYPE PsdLayers>... http://www.cyberforum.ru/cpp-beginners/thread848737.html
C++ В записной книжке указаны фамилии и номера телефонов 30-ти человек. Составить программу, которая определяет, есть ли в записной книжке информация о че
В записной книжке указаны фамилии и номера телефонов 30-ти человек. Составить программу, которая определяет, есть ли в записной книжке информация о человеке с заданным номером телефона, и, если есть, печатает фамилию этого человека. С использованием структур.
C++ Как преобразовать шестнадцатеричное число в строку?
как записать в строку шестнадцатеричное число? например 111111111 в основании 16 в строке должно выглядеть как 4581298449 в основании 10
C++ Проектирование шаблона класса http://www.cyberforum.ru/cpp-beginners/thread848720.html
Спроектировать шаблон класса. В основной программе создать соответствующие структуры простых и сложных структур и продемлонстрировать работу с ними. (Создание классов: Динамический одновымерний массив целых чисел Базовый класс: конструктори; деструктор; функції; Производный класс: динамический одновымерный массив целых чисел з произвольными границами.) Вот код (с перегрузками операторов) ...
C++ Условный оператор.Задача на полуокружность Дана точка на плоскости с координатами (х,у). Составить программу,которая выдаёт одно из сообщений:*Да*,*Нет*,*На границе* в зависимости от того,где лежит точка.Полуокружность по Х лежит от (-1;1) по У лежит от (1;0). подробнее

Показать сообщение отдельно
ya_noob
_
201 / 145 / 9
Регистрация: 08.10.2011
Сообщений: 432
26.04.2013, 16:41
Получается что-то типа этого
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
#include <iostream>
#include <vector>
using namespace std;
 
int A, B, C;
vector< vector< int > > v( 3, vector< int >( 1000000 + 1, 0 ) );
 
int mod( int x )
{
    return x % 1000000007;
}
 
int calc( int N, int x = -1 )
{
    if ( N == 0 ) return 1;
 
    int sum = 0;
 
    if ( x != 0 && N >= A )
        sum = mod( sum + ( v[ 0 ][ N - A ] > 0 ? v[ 0 ][ N - A ] : v[ 0 ][ N - A ] = calc( N - A, 0 ) ) );
    if ( x != 1 && N >= B )
        sum = mod( sum + ( v[ 1 ][ N - B ] > 0 ? v[ 1 ][ N - B ] : v[ 1 ][ N - B ] = calc( N - B, 1 ) ) );
    if ( x != 2 && N >= C )
        sum = mod( sum + ( v[ 2 ][ N - C ] > 0 ? v[ 2 ][ N - C ] : v[ 2 ][ N - C ] = calc( N - C, 2 ) ) );
 
    return sum;
}
 
int main()
{
    int N;
    
    cin >> N >> A >> B >> C;
    cout << calc( N ) << endl;
 
    return 0;
}
но ее слабость в том, что она рекурсивная. Для больших N (например, для входа "44000 1 1 1") системного стека не хватает и программа падает. Надо бы перенести ее на явный стек, но мне лень. Идею решения я написал, дальше думай сам.

Добавлено через 3 часа 14 минут
я тут подумал что проблему со стеком можно решить с помощью восходящего динамического программирования, переписал программу и всё заработало. теперь и для миллиона считает.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru