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

Aus Wikiversity
Zur Navigation springen Zur Suche springen




Fibonacci Zahlen: Funktional vs. Imperativ[Bearbeiten]

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:

Literatur[Bearbeiten]

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.


Vorheriges Thema.jpg Discussion Nächstes Thema.jpg