Algoritam glasi
- Kôd: Obeleži sve
def fibonacci(n):
if n == 0 or n == 1:
return 1
else:
return fibonacci(n - 1) + fibonacci(n - 2)
Traži se [inlmath]n[/inlmath]-ti član Fibonačijevog niza.
Naredba return izlazi iz funkcije i prebacuje tok izvršavanja na funkciju u okviru koje je pozvana istovremeno vraćajući određenu vrednost.
Algoritam je rekurzivan i nadam se da je jasan.
Merimo efikasnost na sledeči način. Ukoliko nije ispunjen uslov, izvršavaju se [inlmath]4[/inlmath] komande (provera u uslovu, dva rekurzivna poziva i operacija sabiranja). A ukoliko je uslov ispunjen (to će se desiti kada dođemo do funkcija sa argumentom 0 ili 1), imamo [inlmath]2[/inlmath] komande (proveru uslova i naredbu return).
Ja sam ovako započeo:
Neka je [inlmath]n[/inlmath] neki veliki broj tj. tražimo član u nizu sa veoma velikim indeksom.
Imamo:
[inlmath]f(n)=4+f(n-1)+f(n-2)[/inlmath]
Kada pozovemo prvi put ovu funkciju za to veliko [inlmath]n[/inlmath], izvršiće se one [inlmath]4[/inlmath] instrukcije. Dalje razlažemo [inlmath]f(n)=4+\bigg(4+f(n-2)+f(n-3)\bigg)+f(n-2)[/inlmath]
U primerima koje smo radili, dovoljno je razložiti još malo i uočiti neku pravilnost. Ovde nikako ne mogu da dokučim posle koliko koraka dolazimo do funkcija sa argumentima 0 ili 1, Takođe, ne znam kako da odredim koliko imamo ovih rekurzivnih funkcija u kojima će se izvršiti ove [inlmath]4[/inlmath] operacije (broj tih funkcija bi trebao da se izrazi preko [inlmath]n[/inlmath]).
Jasnije će biti sa slike o čemu se radi, iako nije baš neko umetničko delo . Ukoliko uzmemo da je [inlmath]n=5[/inlmath] imaćemo [inlmath]7[/inlmath] funkcija koje će izvršiti po [inlmath]4[/inlmath] operacije (obeležene crvenom bojom), i one koje će izvršiti dve operacije (obeležene crnom). Ovde možete videti principe rešavanja na jednostavnijim primerima, ukoliko nisam nešto objasnio kako treba.
Objašnjenje je malo opširnije, jer se verovatno niste susretali sa ovakvim tipom zadatka.