Wie wir noch aus Lerneinheit 1 wissen, ist die Folge der Fibonacci-Zahlen wie folgt definiert:
- Schreiben Sie eine Funktion F=fibonacci_rec(n), die die n-te Fibonacci-Zahl durch explizite rekursive Funktionsaufrufe berechnet!
- Schreiben Sie eine Funktion F=fibonacci_lop(n), die die n-te Fibonacci-Zahl analog zu Lerneinheit 1 ohne rekursive Aufrufe in einer Schleife berechnet!
- Schreiben Sie eine Testfunktion b=fibotest(n), die das Verhältnis b der Laufzeiten der beiden Funktionen aus a) und b) ermittelt.
Lösung
a )
function F=fibonacci_rec(n) % Lösungsvariante mit rekursivem Funktionsaufruf if n<=2 F=1; else F=fibonacci_rec(n-1)+fibonacci_rec(n-2); end end
b )
function f=fibonacci_lop(n) % Lösungsvariante mit Ringpuffer % Initialisierung buffer=[1 1]; for i = 3:n f=sum(buffer); % speichere aktuelle Zahl im Ringpuffer buffer(rem(i,2)+1)=f; end end
c )
function b=fibotest(n) tic fibonacci_lop(n); t1=toc; tic fibonacci_rec(n); t2=toc; b=t2/t1; end