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

Реализация разбиения числа с Динам. Прогр - C++

Восстановить пароль Регистрация
 
s3lf
 Аватар для s3lf
26 / 4 / 1
Регистрация: 20.04.2011
Сообщений: 60
12.10.2013, 20:21     Реализация разбиения числа с Динам. Прогр #1
Доброго времени суток.
Нужна помощь: как с помощью динамического программирования реализовать решение такой вот задачи:
"найти количество разбиений числа на не повторяющиеся слагаемые".
То есть, для числа 3 ответом будет 2:
- 1 + 2
- 3
Буду благодарен за полностью рабочую программу, потому как пытаюсь разобраться с ДП, а без примеров не могу. В рунете же мало статей на эту тему. Заранее спасибо.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.10.2013, 20:21     Реализация разбиения числа с Динам. Прогр
Посмотрите здесь:

Динам. память, указатели, строки C++
подключение динам либ C++
C++ Реализация 128-битного числа
Написать функцию для разбиения числа на числа C++
Динам. массив в классе C++
C++ Одномерный динам массив
C++ Не работает прогр. Ошибки!
Написать рекурсивную процедуру генераций разбиения числа n на сумму слагаемых C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
12.10.2013, 21:34     Реализация разбиения числа с Динам. Прогр #2
как-то так:
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
#include <iostream>
using namespace std;
 
typedef unsigned long long ULL;
const int MAX_N = 791; // значение установлено опытным путем. результат для 792 уже не влезает в ULL
 
ULL cnt[ MAX_N + 1 ][ MAX_N + 1 ] = { { 0 } };
 
ULL calc( int x, int n )
{
    if ( !x ) return 1;
    if ( x < n ) return 0;
    if ( cnt[ x ][ n ] ) return cnt[ x ][ n ];
 
    ULL sum = 0;
 
    for ( int i = n; i <= x; ++i )
        sum += calc( x - i, i + 1 );
    return cnt[ x ][ n ] = sum;
}
 
int main()
{
    for ( int i = 1; i <= MAX_N; i += 10 )
        cout << i << ": " << calc( i, 1 ) << endl;
 
    return 0;
}
немного поясню. очевидно, что всю работу выполняет ф-ция calc. она принимает число, для которого надо посчитать кол-во разбиений, и наменьшее доступное слагаемое. для каждого рекурсивного вызова это наименьшее слагаемое постоянно возрастает, таким образом учитывается требование про неповторяющиеся слагаемые (каждое следующее слагаемое больше предыдущего).

P.S.: Ах да. функция calc может работать быстрее. она делает много лишней работы. попробуй догадаться как ее ускорить.

Добавлено через 5 минут
Цитата Сообщение от s3lf Посмотреть сообщение
В рунете же мало статей на эту тему.
читай лучше умные книги по алгоритмам
Yandex
Объявления
12.10.2013, 21:34     Реализация разбиения числа с Динам. Прогр
Ответ Создать тему
Опции темы

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