Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Алгоритмы > Разложение натурального числа на возможные суммы


Автор: RobinHack 27.1.2009, 16:00
Есть ли готовый агоритм, при помощи которого можно разложить число n на всевозможные суммы его состовляющие. Скажем есть число 6. Алгоритм должен вернуть множество вида {1+1+1+1+1+1, 1+2+3, 2+2+2, 4+2, 1 + 4 + 1, 5 + 1, .......}. Причем без повторений, т.е без элементы 4+2 и 2+4 это одно и тоже. Спасибо.

Автор: Akina 27.1.2009, 16:38
Да, есть... обычный рекурсивный подбор.

Автор: esperanto 28.1.2009, 11:56
да есть - динаммическое программирование

Автор: RobinHack 28.1.2009, 14:10
Цитата(esperanto @ 28.1.2009,  11:56)
да есть - динаммическое программирование

Чем я сейчас и занимаюсь.  smile Спасибо. Выложу код для будущих поколений, как только завершу.

Автор: maxdiver 28.1.2009, 18:29
Странно. Задача ведь не в нахождении количества, а в нахождении самих разбиений. Динамическое программирование в этом плане ничуть не лучше перебора. 

Автор: Akina 31.1.2009, 23:51
Я бы даже сказал, что перебор лучше - накладнЫе расходы меньше.

Автор: esperanto 1.2.2009, 20:21
Цитата(maxdiver @ 28.1.2009,  18:29)
Странно. Задача ведь не в нахождении количества, а в нахождении самих разбиений. Динамическое программирование в этом плане ничуть не лучше перебора.

голословное заключение.

Автор: Silent 12.2.2009, 19:46
Как-то так
Код

const int nmax=100;
int a[nmax];

void f(int x, int level)
{
    if (x=0) 
    {
        for (int i=0;i<level;i++) cout << a[i] << "/t";
        cout << "\n";
    }
    else
    {
        for (int i=x;i>0;i--)
        {
            a[level] = i;
            f(x-i,level+1);
        };
    }
}

int main()
{
    int n = 0;
    cin >> n;
    f(n,0);
}

Автор: Rimch 18.2.2009, 15:24
Представление числа в виде суммы чисел - классическая задача теории алгоритмов.
Пример разложения числа 7
7= 1+1+1+1+1+1+1
7= 2+1+1+1+1+1
7= 2+2+1+1+1
7= 2+2+2 +1

7= 3+1+1+1+1
7= 3+2+1+1
7= 3+2+2
7= 3+3+1

7= 4+1+1+1
7= 4+2+1
7= 4+3

7= 5+1+1
7= 5+2

7= 6+1
7= 7
Идея решения 
Пусть дано число N которое надо разложить
1. Заполняем массив А(массив суммируемых чисел) из N элементов единичками
2. Начиная с последнего элемента ищем позицию элемента который надо увеличить на +1,
    удовлетворяющего условию A[pos-1]>A[pos], pos>1
3. Увеличиваем элемент на позиции pos на 1, остальные заполняем необходимым количеством 1
4. Повторяем шаги 2 и 3 пока первый элемент массива не станет равным N

Автор: SoWa 19.2.2009, 06:52
Вооот, пришел человек с мозгом, не загруженым большущими знаниями и высказал простейшее и нормальное решение smile За что ему плюсъ. (А мы как студенты. решающие задачу 1 класса с помощью интегралов)
А так, соглашусь с Akina и maxdiver

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)