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

Представление числа в виде суммы

Задача. Перечислить все представления положительного целого числа n в виде суммы последовательности невозрастающих целых положительных слагаемых.
Решение. Программа оперирует с массивом a[1..n] (максимальное число слагаемых равно n) и с целой переменной t. Предполагая, что a[1],...,a[t] - невозрастающая последовательность целых чисел, сумма которых не превосходит n, процедура generate печатает все представления требуемого вида, продолжающие эту последовательность. Для экономии вычислений сумма a[1]+...+a[t] хранится в специальной переменной s.
procedure generate;
 | var i: integer;
 begin
 | if s = n then begin
 | | печатать последовательность a[1]..a[t]
 | end else begin
 | | for i:=1 to min(a[t], n-s) do begin
 | | | t:=t+1;
 | | | a[t]:=i;
 | | | s:=s+i;
 | | | generate;
 | | | s:=s-i;
 | | | t:=t-1;
 | | end;
 | end;
 end;
Основная программа при этом может быть такой:
t:=1;
 for j:=1 to n do begin
 | a[1]:=j
 | s:=j;
 | generate;
 end;
Замечание. Можно немного сэкономить, вынеся операции увеличения и уменьшения t из цикла, а также не возвращая s каждый раз к исходному значению (а увеличивая его на 1 и возвращая к исход- ному значению в конце). Кроме того, добавив фиктивный элемент a[0]=n, можно упростить основную программу:
t:=0; s:=0; a[0]:=n; generate;
 Похожие публикации: Алгоритмы

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