Fibonacci-Zahlenpaare (2)

Zur Lösung unserer einstufigen Rekursionsgleichung nehmen wir zwischendurch die Existenz eines Abstrakten Datentyps Paar  an
ADT Paar IS
SORTS: Paar, CARDINAL
OPERATIONS:
Komb: CARDINAL CARDINAL Paar
Teil1: Paar CARDINAL
Teil2: Paar CARDINAL
RULES:
Teil1(Komb(x,y)) = x
Teil2(Komb(x,y)) = y
END Paar.
oder als Definitionsmodul geschrieben: 
DEFINITION MODULE Paar;

TYPE Paar;

PROCEDURE Komb(x, y: CARDINAL): Paar;

PROCEDURE Teil1(z: Paar): CARDINAL;

PROCEDURE Teil2(z: Paar): CARDINAL;

END Paar.
Damit können wir nun eine rein funktional-rekursive Lösung aufbauen: 
PROCEDURE Fib(n: CARDINAL): CARDINAL;
BEGIN RETURN Teil1(FPaar(n);
END Fib;

PROCEDURE FPaar(n: CARDINAL): Paar;
BEGIN IF n <= 2 THEN RETURN Komb(1, 1)
      ELSE RETURN FKomb(FPaar(n-1))
      END:
END FPaar;

PROCEDURE FKomb(x: Paar): Paar;
BEGIN RETURN Komb(Teil1(x)+Teil2(x), Teil1(x))
END FKomb;
Damit hätten wir im Prinzip unser Problem gelöst, wenn wir den Typ Paar  zur Verfügung hätten. Leider ist das aber nicht so; wir können ihn in Modula 2 nicht verwenden, ja nicht einmal realisieren: für einen opaken Typ belegen seine Werte zu viel Speicher, und er ist auch als Resultat einer Funktion nicht zulässig, weil Modula 2 dort aus historischen Gründen nur einfache Grundtypen erlaubt.

Wir müssen uns also irgendwie behelfen: entweder durch Übergang auf eine mächtigere Programmiersprache wie etwa Ada oder LISP; oder aber indem wir den Typ Paar  auflösen und Hilfsvariablen sowie Ergebnisparameter verwenden. 

PROCEDURE Fib(n: CARDINAL): CARDINAL;
VAR x, y: CARDINAL;
BEGIN FPaar(n, x, y); RETURN x;
END Fib;

PROCEDURE FPaar(n: CARDINAL; VAR x, y: CARDINAL);
VAR u, v: CARDINAL;
BEGIN IF n <= 2 THEN x := 1; y := 1;
      ELSE FPaar(n-1, u, v);
           x := u+v; y := u;
      END:
END FPaar;
Der Algorithmus und sein Verhalten ändert sich dabei nicht grundsätzlich: wir haben hier auch nichts anderes getan, als was eigentlich ein Compiler für uns erledigen sollte!

Wenn wir nun auf diese letzte Lösung wieder Dynamische Programmierung anwenden und die Teillösungen von unten nach oben einsammeln, so kommen wir im wesentlichen bei unserer früheren iterativen Lösung heraus. So hat sich der Kreis geschlossen.

zurück | Inhalt | Index | Vorlesung
Klaus Lagally, 22. Februar 2000, 19:36