Кодинг
★ Рубрика: Кодинг
★ Тема: Алгоритм

Найти все разложения целого числа на слагаемые

Задача. Перечислить все разбиения целого положительного числа n на целые положительные слагаемые (разбиения, отличающиеся лишь порядком слагаемых, считаются за одно). (Пример: n=4, разбиения 1+1+1+1, 2+1+1, 2+2, 3+1, 4.)
Решение. Договоримся, что в разбиениях слагаемые идут в невозрастающем порядке, а сами разбиения мы перечисляем в лексикографическом порядке. Разбиение храним в начале массива x[1]...x[n], при этом количество входящих в него чисел обозначим k. В начале x[1]=...=x[n]=1, k=n, в конце x[1]=n, k=1. В каком случае x[s] можно увеличить не меняя предыдущих? Во-первых, должно быть x[s-1] > x[s] или s = 1. Во-вторых, s должно быть не последним элементом (увеличение s надо компенсировать уменьшением следующих). Увеличив s, все следующие элементы надо взять минимально возможными.
s := k - 1;
 while not ((s=1) or (x[s-1] > x[s])) do begin
 s := s-1;
 end;
 {s - подлежащее увеличению слагаемое}
 x [s] := x[s] + 1;
 sum := 0;
 for i := s+1 to k do begin
 sum := sum + x[i];
 end;
 {sum - сумма членов, стоявших после x[s]}
 for i := 1 to sum-1 do begin
 x [s+i] := 1;
 end;
 k := s+sum-1;
 Похожие публикации: Алгоритм

Войдите, чтобы добавить Ваш ответ. [ Регистрация | Вход ]