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

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

Войти
Регистрация
Восстановить пароль
 
s3lf
26 / 4 / 1
Регистрация: 20.04.2011
Сообщений: 60
#1

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

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

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

Написать функцию для разбиения числа на числа - C++
Помогите написать функцию для разбиения числа на числа! Например ввели 12345 а должна вывести 1 2 3 4 5

Написать рекурсивную процедуру генераций разбиения числа n на сумму слагаемых - C++
Задача : Написать рекурсивную процедуру генераций разбиения числа n на сумму слагаемых. Например при n=4 3 1 2 2 2 1 1 1 1 1 1 ...

Не работает прогр. Ошибки! - C++
Помогите исправить ошибки.

Одномерный динам массив - C++
вычислить количество элементов больших C вычислить произведение элементов расположенных после максимального по модулю элемента ...

Динам. массив в классе - C++
Здравствуйте, За пример брал пободный код (он работает и делает дин.массив из нолей): #include <iostream> using namespace std; ...

подключение динам либ - C++
подскажите никак не пойму вот создал *.so создаю проект добавляю эту либу в иде для линковки из main.cpp вызываю функу либы и...

1
ya_noob
_
203 / 147 / 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 Посмотреть сообщение
В рунете же мало статей на эту тему.
читай лучше умные книги по алгоритмам
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.10.2013, 21:34
Привет! Вот еще темы с ответами:

помощь(консультация) в написании прогр.на Си-текст.редактор - C++
Тут вот задали написать текстовой редактор на си,выдана программа-заготовка,она по идее якобы тот же текст.ред.но урезанный,в общем беру...

Динам. память, указатели, строки - C++
хелп) а то не успеваю все решить))) Задание 2 Написать программу которая позволяет пользователю ввести любое количество целых чисел,...

В чем опасность Double-Checked Locking (параллельное прогр-е) - C++
В учебнике Энтони Уильямса &quot;Параллельное программирование на C++&quot; описана проблема при использовании блокировки с двойной проверкой...

Перегрузка индексации двумерного динам. массива - C++
решил реализовать такое: обращение к эл-ту двумерного массива происходит следующим образом а, я решил перегрузить чтобы обращаться к...


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

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

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