Zahl in Summanden zerlegen

[fiasko]

Man kann das noch ein bißchen optimieren. Idee:

Code:

z=20    ; Zahl X
n= 5    ; Summanden 

k=1  k=2  k=3  k=4  k=5
16
14
13
12
11
10
 9
 8    9
 7    7
 6    6    7
 5    5    5    6
 4    4    4    4    5
 3    3    3    3    3
 2    2    2    2    2
 1    1    1    1    1

höchster Wert einer Spalte:
 (z-(n-k+1))/k+1

Das sollten alle möglichen Kombinationen von Summanden enthalten. Wenn man nun die Zahl aufbaut einfach von der rechten Spalte an immer eine Zahl nehmen, dann eine Spalte nach links und eine Zahl die größer-gleich der letzten ist nehmen. Damit dürften auch keine Dopplungen mehr auftreten.

Delphi-Quellcode:

uses sysutils;              

{
  n: Anzahl Summanden
  k: aktueller Summand (start bei k=n)
  z: Zahl X
  s: aktuelle Summe
  l: letzter Summand (start bei 1)
  str: aktuelle Zahl
}

procedure zahl(n,k,z,s,l: Integer; str: String);
var
  i: Integer;
begin
  if k=0 then
  begin
    if(s=z) then
      writeln(str);
    exit;
  end;                                                                                                                                                           

  for i:=l to ((z-(n-k+1)) div k)+1 do
    zahl(n,k-1,z,s+i,i,str+inttostr(i)+' ');
end;

begin
  { Zahl 20 in 5 Faktoren zerlegen }
  zahl(5,5,20,0,1,'');
end.

(kA ob da alle Lösungen rauskommen... müßte man mal überprüfen )