Pascal-Dreieck

… warum bricht das nicht ab?

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

Pascal-Dreieck
Moin,

hat jemand ne Idee, warum meine Rekursion nicht abbricht, bzw., was muss ich machen, dass sie abbricht? Wir rätseln hier schon seit ner Ewigkeit rum, kommen aber nicht drauf…

pascal(0, 0, 1).

pascal(_, S, X) :- S < 0, X is 0.
pascal(Z, S, X) :- S > Z, X is 0.

pascal(Z, S, X) :- S < 0, Z < 0, X is 0.

pascal(Z, S, X) :- S1 is S - 1, Z1 is Z - 1, 
                   pascal(Z1, S1, A), pascal(Z1, S, B),
                   X is A + B.

Wenn ich nach

pascal(5, 2, X) frage, liefert er mir zwar korrekt X = 10; hört aber nicht auf sondern wiederholt immer X = 10; X = 10; X = 10; X = 10; …

Any Prolog-Freaks here? :slight_smile:

Gruß,
Seb


Das liegt unter anderem wohl daran, dass die letzte Regel unendlich oft angewendet werden kann, bis dann endlich mal die Regel für zwei negative Werte greift. Das heißt wenn Prolog nach weiteren Möglichkeiten sucht, so nimmt es beim ersten mal zwar gleich die Regel aus Zeile 6, danach aber wieder einmal mehr die Regel in Zeile 8 und dann erst die aus Zeile 6 usw…

In Zeile 8 sollte noch sowas wie Z > 0, S > 0 mit rein. Oder eben mit !-Operator das Backtracking verhindern, wenn eine der vorherigen Regeln gegriffen hat.

Hier eine etwas andere Lösung:

pascal(Z,S,0) :- (Z < 0; S < 0; Z < S), !.

pascal(N,N,1).
pascal(Z,0,1) :- Z > 0.
pascal(Z,S,X) :- Z > 0, S > 0, Z =\= S,
                 S1 is S-1, Z1 is Z-1,
                 pascal(Z1,S1,A), pascal(Z1,S,B),
                 X is A + B.

Die erste Regel kann man auch weglassen, dann kommt “falsche” Anfragen als Antwort “No.” statt “0”.


Wow, danke Goethe! Hat mir sehr geholfen - schöne Lösung.

Mit dem cut-Operator hatte ich auch herumgefrickelt, habs aber nicht hinbekommen.

Gruß,
Sebastian