Fibonacci

hejsan

skulle jag kunna få lite tips på övning 4.7?

Hej Biorr God morgon!

Jag har läs programmering C och C++ en gång i tiden och jag kom ihåg att Fibonacci talen och rekursion var en stor del av kursen. Väldigt klurig till att börja med. Men när man förstår går det lättare särskilt när man programmerar.

Vi gör det ett försökt så här:

Om man tittar i början av övningen det är källkoden (i språket C) som uppgiften syftar på.

När programmet körs ser vi i koden att:

Om n == 0 körs return 0; (basfallet $f_{0}$ som uppgiften frågar efter).

Om n == 1 körs return 1; (Basfallet $f_{1}$ ).

Annars delas anropet upp i två nya grenar: fibo(n-1) + fibo(n-2).

Den rekursiva formeln för följden $b_{n}$ ger $b_{0}$ = 1, $b_{1}$ = 0

Följden $b_{n}$ beskriver hur många gånger funktionen hamnar i basfallet n == 0 (vilket ger $f_{0}$ . Genom att titta noga på källkoden får vi följande rekursiva definition: $b_{0}$ = 1 , $b_{1}$ = 0.

För att beräkna ett steg delas koden upp i de två föregående stegen, gör att antalet basfallsanrop adderas på samma sätt som i Fibonacciföljden : $b_{n} = b_{n - 1} + b_{n - 2}$ ==> $n \geq 2$

Genom att räkna ut värdena steg för steg från $b_{0}$ till $b_{9}$ får vi följande tio tal:

$b_{0} = 1$ om n = 0 körs basfallet direkt 1 gång ; $b_{1} = 0$ om n=1 andra basfallet körs och $f_{0}$ plockas fram 0 gånger.

$b_{2} = b_{1} + b_{0} = 0 + 1 = 1$ ; $b_{3} = b_{2} + b_{1} = 1 + 0 = 1$ ; $b_{4} = b_{3} + b_{2} = 1 + 1 = 2$ ; $b_{5} = b_{4} + b_{3} = 2 + 1 = 3$

$b_{6} = b_{5} + b_{4} = 3 + 2 = 5$ ; $b_{7} = b_{6} + b_{5} = 5 + 3 = 8$ ; $b_{8} = b_{7} + b_{6} = 8 + 5 = 13$ ; $b_{9} = b_{8} + b_{7} = 13 + 8 = 21$

De tio forsta talen är : 1, 0, 1, 1, 2, 3, 5, 8, 13, 21

Det är min lösning utifrån utifrån den givna C-koden för Fibonaccifunktionen. Om någon vill addera ytterligare synpunkter eller kommentera resultatet, måste du även iaktta och ta hänsyn till de kommentarerna.

Lycka till med matte studierna!

Svara