Kurs:Algorithmen und Datenstrukturen/Vorlesung/Fibonacci-Zahlen Vergleich

Fibonacci Zahlen: Funktional vs. Imperativ

In diesem Kapitel werden wir den funktionalen Algorithmus der Fibonacci-Zahlen mit dem imperativen Algorithmus vergleichen.

Funktionale Umsetzung

fib(x)  :=  if (x==0) then 0
       else if (x==1)  then  1 
                else  fib(x-1) + fib(x-2)

Imperative Umsetzung

FIB var X,A,B,C: int;
                  input X; 
                  A := 0; B:=1; C:=1;
                  while  X > 0 { 
                           C :=  A+B;
                           A := B; 
                           B := C;
                           X := X-1; 
                  }
                  output A;

Für beliebige X gibt die Auswertung das Ergebnis von FIB(X). Wir erkennen, der imperative Algorithmus FIB berechnet folgende Funktion:

$[[FIB]](x)=\{\begin{array}{cc}x-teFib.Zahl& fallsx\ge 0\\ 0& sonst\end{array}$

Literatur

Da die Vorlesungsinhalte auf dem Buch Algorithmen und Datenstrukturen: Eine Einführung mit Java von Gunter Saake und Kai-Uwe Sattler aufbauen, empfiehlt sich dieses Buch um das hier vorgestellte Wissen zu vertiefen. Die auf dieser Seite behandelten Inhalte sind in Kapitel 3.3.3 zu finden.