Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/6: Рейтинг темы: голосов - 6, средняя оценка - 5.00
26 / 4 / 1
Регистрация: 20.04.2011
Сообщений: 60
1

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

12.10.2013, 20:21. Просмотров 1134. Ответов 1
Метки нет (Все метки)

Доброго времени суток.
Нужна помощь: как с помощью динамического программирования реализовать решение такой вот задачи:
"найти количество разбиений числа на не повторяющиеся слагаемые".
То есть, для числа 3 ответом будет 2:
- 1 + 2
- 3
Буду благодарен за полностью рабочую программу, потому как пытаюсь разобраться с ДП, а без примеров не могу. В рунете же мало статей на эту тему. Заранее спасибо.
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
12.10.2013, 20:21
Ответы с готовыми решениями:

Написать функцию для разбиения числа на числа
Помогите написать функцию для разбиения числа на числа! Например ввели 12345 а должна вывести 1...

Разбиения числа
Здравствуйте, уважаемые форумчане. Требуется помощь с кодом. Имеется код, который должен находить...

разбиения заданного числа
Разработайте программу, которая находит все разбиения заданного числа.

Генератор разбиения числа
Есть программа!! а теперь суть, каким образом это должно осуществляться!! когда она запрашивает N я...

1
_
316 / 150 / 27
Регистрация: 08.10.2011
Сообщений: 432
12.10.2013, 21:34 2
Лучший ответ Сообщение было отмечено s3lf как решение

Решение

как-то так:
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 Посмотреть сообщение
В рунете же мало статей на эту тему.
читай лучше умные книги по алгоритмам
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
12.10.2013, 21:34

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Разбиения натурального числа N
Помогите с задачей пожалуйста Дано натуральное число n. Напечатать все его разбиения на целые...

Алгоритм разбиения числа на простые слагаемые
Есть код для разложения числа на простые слагаемые. Если число большое, то количество слагаемых...

Алгоритм разбиения числа на простые слагаемые
Помогите написать алгоритм разбиения числа на простые слагаемые. Пример Ввод: 21 Вывод: 19+2...

Перечислить все разбиения натурального числа n
Перечислить все разбиения натурального числа n на натуральные слагаемые в следующих порядках...

Перечислить все разбиения целого положительного числа на слагаемые
Ребята, в общем хотел обратиться за помощью, сижу ломаю голову, но не могу догадаться как...

Перечислить все разбиения натурального числа на натуральные слагаемые
у меня есть код, но он работает неправильно. Я так понимаю, что где-то надо сделать рекурсию,...


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

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

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