Как разбить число на составляющие

проще всего крепко сжать его в руках, отойти подальше от стены, сильно размахнуться и швырнуть со всей дури это число в стену.
Проверено на опыте - число разбивается на много-много слагаемых! Только успевай их собирать и лОжить в сумку!



Редактировалось 1 раз(а). Последний 10.01.2013 16:30.

число может состоять максимум из 24 елементов
количество елементов около 100 один елемент может повторятся несколько раз (в большенстве случаев от 2 до 20)
сума может быть от 620 до 35000

привожу реальный пример

12150=9720+810+810+810

12150 на какие состовляющие?
на еденицы? 1+1+1+1,,,,,,,,+1 и так 12150 раз.

Цитата
provincialka

Имеется набор чисел ( в Вашем примере это 5, 25, 500, 525). Необходимо разложить заданное число на слагаемые из этого множества, возможно, с повтором .
Но в чем вопрос? Проверить существование такого разбиения? Найти количество таких разбиений? В любом случае задача нетривиальная, алгоритм без перебора вряд ли существует.

Вот это уже более или менее чёткая постановка задачи! Кроме того будем считать, что каждое из чисел 5, 25, 500, 525 встречается в разложении хотя бы один раз, иначе решений будет слишком много.
Следующая прога, написанная в Maple, решает эту задачу. Если решений нет, то возвращается строка Решений нет. Каждое решение возвращается в виде списка коэффициентов разложения, т.е. решение [ i, j, k, m] означает, что заданное число N равно 525*i+500*j+25*k+5*m

Код:

P:=proc(N)
local L, i, j, k, m;
if type(N/5, fraction) then return `Решений нет` else
L:=[ ]:
for i to floor(N/525) do
for j to floor(N/500) do
for k to floor(N/25) do
for m to floor(N/5) do
if 525*i+500*j+25*k+5*m=N then L:=[op(L), [i, j, k, m]]; fi;
od; od; od; od; fi;
if nops(L)=0 then `Решений нет` else op(L); fi;
end proc:

Примеры:

P(1055);
[1, 1, 1, 1]

То есть существует единственное решение $1055=525+500+25+5$

P(1095);
[1, 1, 1, 9], [1, 1, 2, 4]

Здесь уже два решения $1095=525+500+25+9*5=525+500+2*25+4*5$

P(2000);
[1, 1, 1, 190], [1, 1, 2, 185], [1, 1, 3, 180], [1, 1, 4, 175],

[1, 1, 5, 170], [1, 1, 6, 165], [1, 1, 7, 160],

[1, 1, 8, 155], [1, 1, 9, 150], [1, 1, 10, 145],

[1, 1, 11, 140], [1, 1, 12, 135], [1, 1, 13, 130],

[1, 1, 14, 125], [1, 1, 15, 120], [1, 1, 16, 115],

[1, 1, 17, 110], [1, 1, 18, 105], [1, 1, 19, 100],

[1, 1, 20, 95], [1, 1, 21, 90], [1, 1, 22, 85],

[1, 1, 23, 80], [1, 1, 24, 75], [1, 1, 25, 70],

[1, 1, 26, 65], [1, 1, 27, 60], [1, 1, 28, 55],

[1, 1, 29, 50], [1, 1, 30, 45], [1, 1, 31, 40],

[1, 1, 32, 35], [1, 1, 33, 30], [1, 1, 34, 25],

[1, 1, 35, 20], [1, 1, 36, 15], [1, 1, 37, 10], [1, 1, 38, 5],

[1, 2, 1, 90], [1, 2, 2, 85], [1, 2, 3, 80], [1, 2, 4, 75],

[1, 2, 5, 70], [1, 2, 6, 65], [1, 2, 7, 60], [1, 2, 8, 55],

[1, 2, 9, 50], [1, 2, 10, 45], [1, 2, 11, 40], [1, 2, 12, 35],

[1, 2, 13, 30], [1, 2, 14, 25], [1, 2, 15, 20],

[1, 2, 16, 15], [1, 2, 17, 10], [1, 2, 18, 5], [2, 1, 1, 85],

[2, 1, 2, 80], [2, 1, 3, 75], [2, 1, 4, 70], [2, 1, 5, 65],

[2, 1, 6, 60], [2, 1, 7, 55], [2, 1, 8, 50], [2, 1, 9, 45],

[2, 1, 10, 40], [2, 1, 11, 35], [2, 1, 12, 30],

[2, 1, 13, 25], [2, 1, 14, 20], [2, 1, 15, 15],

[2, 1, 16, 10], [2, 1, 17, 5]

Здесь уже совсем много решений!