Rekursionsproblem

[zack0r]

Hallo!
ich habe ein Problem: ich wollte die Ackermann-Funktion rekursiv programmieren. Das an sich stellt ja nun kein Problem da, aber ich wollte, dass die Zwischenschritte mit ausgegeben werden. Nun habe ich einen Prototyp in Pascal entworfen (der einfacherkeit halber, ist ja bei so Sachen im Grunde das selbe, wie Delphi) der sieht nun so aus:

Delphi-Quellcode:

program ackermann;
uses crt;

var n,m, ans, tmp, count : integer;
    key : char;

function f(m,n : integer): integer;
begin
  count := succ(count);
  if m = 0 then
  begin
    tmp := n;
    f := n + 1;
  end
  else if n = 0 then
  begin
    //write(' = f(',m,'-1, 1)');
    writeln(' = f(',m-1,', 1)');
    f := f(m-1, 1);
  end
  else
  begin
    //write(' = f(',m,'-1, f(', m,', ', n,'-1))');
    writeln(' = f(',m-1,', f(', m,', ',n-1,'))');
    f := f(m-1, f(m, n-1))
  end;
end;

begin
  clrscr;
  repeat
    count := 0;
    write('m = '); readln(m);
    write('n = '); readln(n);
    writeln;
    writeln('f(',m,', ',n,')');
    ans := f(m, n);
    writeln(' = f(0, ',tmp,') = ',ans);
    writeln;
    writeln('Anzahl Funktionsaufrufe: ',count);
    write('continue y/n ');
    readln(key);
    writeln
  until key='n'
end.

So das geht aber so nicht, weil bei jedem (!) Funktionsaufruf die Zwischenschritte ausgegeben werden, also auch bei Schritten, die garnicht angezeigt werden sollen, bzw. die man auch garnicht zuordnen kann. Die Ausgabe sollte etwa so wie in diesen Beispielen aussehen:kalle2000
Ich habe schon soeiniges probiert, zB hatte ich an einer zweiten Funktion, oder eher procedure für die Ausgabe gedacht, aber das ging auch nicht. Hab es mit einer temporären Variable probiert, die dann am Anfang auf 1 steht und danach auf 0 aber die Schritte nur ausgegeben werden, wenn die Variable auf 1 steht, aber das hat auch nur bei manchen Berechnungen funktioniert. Also eigentlich müsste man ja nur rausfinden, um welchen Aufruf es sich handelt, deswegen hab ich auch das mit dem count gemacht, dass hat aber auch nicht geholfen.

Wäre nett wenn ihr nochmal eure alten Turbo-Pascal Compiler auspacken würdet und mir helfen würdet :) (Delphi geht auch ^^)

naja schonmal danke im Vorraus, MFG F. Schmitt

[ibp]

welche sollen den nicht ausgegeben werden und welche sollen?

[zack0r]

f(2,0) = f(1,1) = f(0,f(1,0)) = f(0,2) = 3

Also, es soll so ausgegeben werden. Aber wenn man es mit dem Program, welches ich Oben eingefügt habe Berechnen lässt, dann wird auch das (z.B.) Fett gedruckte mit ausgegeben. Ist ja auch eigentlich klar, dass soll aber nicht ausgegeben werden, da es nichts mit der Eigentlichen Berechnung zu tun hat. Wenn du es mal compilierst und ein paar Zahlen ausprobierst (am besten mit dem Link oben vergleichen), dann weisst du sofort, was ich meine.

Danke, MFG

[ibp]

dann darfst du den else-teil nicht ausdrucken lassen!

[zack0r]

dann gehts nur für manche Zahlen: Ausgabe bei f(1,2)

Delphi-Quellcode:

m = 1
n = 2

f(1, 2)
 = f(0, f(1, 1))
 = f(0, f(1, 0))
 = f(0, 3) = 4

Anzahl Funktionsaufrufe: 6

mfg

[ibp]

Zitat:

Zitat von zack0r

f(2,0) = f(1,1) = f(0,f(1,0)) = f(0,2) = 3

Also, es soll so ausgegeben werden. Aber wenn man es mit dem Program, welches ich Oben eingefügt habe Berechnen lässt, dann wird auch das (z.B.) Fett gedruckte mit ausgegeben. Ist ja auch eigentlich klar, dass soll aber nicht ausgegeben werden, da es nichts mit der Eigentlichen Berechnung zu tun hat. Wenn du es mal compilierst und ein paar Zahlen ausprobierst (am besten mit dem Link oben vergleichen), dann weisst du sofort, was ich meine.

Danke, MFG

hab mir mal das pdf angesehen, da sieht es genauso aus! :gruebel:

[zack0r]

Da mir jetzt schon 3 mal der Internet Explorer abgestürzt ist schreib ichs jetz zum 4ten mal...
also

in der pdf steht für f(3,0) folgendes:

Delphi-Quellcode:

f(3,0) = f(2,1) = f(1,f(2,0)) = f(1,3) = f(0,f(1,2)) = f(0,4) = 5

was auch irgendwie Sinn macht, finde ich.

wenn ich nun in mein Program 3 und 0 eingebe kommt folgendes bei raus:

Delphi-Quellcode:

m = 3
n = 0

f(3, 0)
 = f(2, 1)
 = f(1, f(2, 0))
 = f(0, f(1, 0))
 = f(0, f(1, 2))
 = f(0, f(1, 1))
 = f(0, f(1, 0))
 = f(0, 4) = 5

Anzahl Funktionsaufrufe: 15
continue y/n

Da stimmt doch irgendwas nicht...manche Zwischenschritte stimmen, das Endergebnis auch, aber manche Zwischenschritte sind halt quatsch. Also ich denke, dass es einfach an der Rekursion liegt, weil theoretisch jeder der 15 Funktionsaufrufe mit einer Ausgabe verbunden ist(hab if m=0 then f:=1 mal weggelassen, der Übersicht halber). Da sich die Funktion immer wieder selbst aufruft und die einzelnen Aufrufe wieder Ausgaben haben kommen es halt zu ausgaben, wie = f(0, f(1, 1)), was ja nichts mit der Berechnung von f(3,0) zu tun hat.

Danke, MFG