Eugie » 05 апр 2004, 16:50
Вот такой алгоритм (на Delphi):
Код: Выделить всё
program NumDecomp;
{$APPTYPE CONSOLE}
uses
SysUtils;
var arr: array of Integer;
ArrSize, level, count: Integer;
s: String;
procedure Print;
var i: Integer;
begin
s := '';
for i := 0 to level do begin
s := s+IntToStr(arr[i]);
if i < level then
s := s+'+';
end;
WriteLn(s);
end;
// Recoursively finds all possible additive decompositions of N such that
// Min(addend) >= M; if the tryed composition is monotonely increasing,
// prints it to the screen.
procedure Decomp(N, M: Integer);
var i: Integer;
begin
if N > 0 then begin
Inc(level);
for i := M to N do begin
arr[level] := i;
Decomp(N-i,i);
end;
Dec(level);
end
else begin
Inc(count);
Print;
end;
end;
begin
Write('Enter a number to decompose additively: ');
ReadLn(s);
level := -1; count := 0;
if TryStrToInt(s, ArrSize) then begin
SetLength(arr, ArrSize);
Decomp(ArrSize,1);
end;
SetLength(arr, 0);
WriteLn(Format('The number of variants: %d', [count]));
end.
Смысл, надеюсь, понятен: генерим все возможные комбинации _неубывающих_ последовательностей, дающих в сумме заданное число. Можно и без рекурсии, но это пусть кто-нибудь другой попробует
Вот такой алгоритм (на Delphi):
[code]
program NumDecomp;
{$APPTYPE CONSOLE}
uses
SysUtils;
var arr: array of Integer;
ArrSize, level, count: Integer;
s: String;
procedure Print;
var i: Integer;
begin
s := '';
for i := 0 to level do begin
s := s+IntToStr(arr[i]);
if i < level then
s := s+'+';
end;
WriteLn(s);
end;
// Recoursively finds all possible additive decompositions of N such that
// Min(addend) >= M; if the tryed composition is monotonely increasing,
// prints it to the screen.
procedure Decomp(N, M: Integer);
var i: Integer;
begin
if N > 0 then begin
Inc(level);
for i := M to N do begin
arr[level] := i;
Decomp(N-i,i);
end;
Dec(level);
end
else begin
Inc(count);
Print;
end;
end;
begin
Write('Enter a number to decompose additively: ');
ReadLn(s);
level := -1; count := 0;
if TryStrToInt(s, ArrSize) then begin
SetLength(arr, ArrSize);
Decomp(ArrSize,1);
end;
SetLength(arr, 0);
WriteLn(Format('The number of variants: %d', [count]));
end.
[/code]
Смысл, надеюсь, понятен: генерим все возможные комбинации _неубывающих_ последовательностей, дающих в сумме заданное число. Можно и без рекурсии, но это пусть кто-нибудь другой попробует :)