Перечислить все разбиения целого положительного числа  n  на целые положительные слагаемые (разбиения, отличающиеся лишь порядком слагаемых, считаются за одно). (Пример: n=4,  раз-
биения 1+1+1+1, 2+1+1, 2+2, 3+1, 4.)

Решение. Договоримся, что (1) в разбиениях слагаемые идут в невозрастающем порядке, (2) сами разбиения мы перечисляем в лексикографическом  порядке.  Разбиение  храним  в  начале  массива 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;


2009-12-04 • Просмотров [ 1738 ]