%%  Datei:  arithmetik.pl
%%
%%  Programmierkurs Prolog (Sommersemester 2002),
%%  Material fuer Uebungsblatt 3, Aufgabe 3.3


%%  Das Praedikat 'gcd(+I,+J,?G)' berechnet den groessten gemeinsamen Teiler
%%  der beiden Zahlen 'I' und 'J' mit Hilfe des Euklidischen Algorithmus und
%%  matcht das Ergebnis mit 'G':
%%
%%  Induktionsbeginn:  Falls J=0, dann G=I.

gcd(I,0,I).

%%  Induktionsschritt:  Falls J>0, berechne gcd(J, I mod J, G).

gcd(I,J,G) :-
    J > 0,
    K is I mod J,
    gcd(J,K,G).



%%  Das Praedikat 'fact(+N,?F)' berechnet die Fakultaet von 'N; und matcht
%%  das Ergebnis mit 'F' (rekursive, nicht-iterative Fassung):
%%
%%  Induktionsbeginn:  Falls N=0, gilt F(N) = 1.

fact(0,1).

%%  Induktionsschritt:  Falls N>0, berechne F(N) = N * F(N-1).

fact(N,F) :-
    N > 0,
    N1 is N - 1,
    fact(N1,F1),
    F is N*F1.



%%  Das Praedikat 'fact2(+N,?F)' berechnet die Fakultaet von 'N; und matcht
%%  das Ergebnis mit 'F' (end-rekursive, also iterative Fassung):
%%
%%  Abbildung auf ein dreistelliges Hilfspraedikat 'fact2(+N,+A,?F)' mit 
%%  Akkumulator-Argument ('N' wird heruntergezaehlt und dabei 'A=N*N-1*...'
%%  akkumuliert).  Um 'fact2(N,F)' zu beweisen, beweise 'fact2(N,1,F):

fact2(N,F) :- fact2(N,1,F).

%%  Induktionsbeginn:  Falls N=0, gilt F(N) = A.

fact2(0,F,F).

%%  Induktionsschritt:  Falls N>0, berechne fact(N-1,A*N,F).

fact2(N,A,F) :-
    N > 0,
    N1 is N-1,
    A1 is A*N,
    fact2(N1,A1,F).