Algoritmi za izračunavanje Fibonačijevih brojeva?

[clzola]

Tema za seminarski rad koju sam (tek) dobio je sledeca: Fibonačijevi brojevi i algoritmi za njihovo izračunavanje.

Ja znam sta su fibonacijevi brojevi i znam kako da ih nadjem. Medjutim jedini nacin (algoritam) koji znam je preko rekurzije odnosno koriscenjem tehnike "Dinamicko programiranje". Sad moje je pitanje da li postoje jos neki algoritmi za njihovo izracunavanje, posto bih zelio da opisem vise algoritama a ne samo jedan (treba da ispisem 15+ strana xD).
Uporedo gledao sam na Wikipediji, tamo ima jako dosta formula, ali sa obzirom da je kasno ne razaznajem ih bas najbolje, pa cu u toku sledecig dana da vidim sta tacno tamo pise. Eto, ako znate neki algoritam osim ovog koji sam ja spomenuo napisete ime algoritma i link ka tom algoritmu ili da ga objasnite u kratkim crtama, za njegove osobine cu se sam pobrinuti :D

Hvala :ciao:

[voodoo_]

Otkucaš na guglu npr. "fibonnaci numbers non recursive" i iskoči svašta korisno, kao recimo ovo:

http://www.codeproject.com/Tips/109443/Fibonacci-Recursive-and-Non-Recursive-C

[MG-RAY]

Have fun: http://nayuki.eigenstate.org/page/fast-fibonacci-algorithms

:D

[clzola]

Hvala vam, bice ovo jedan lijep seminarski rad !! :D

[clzola]

Da nema još koji algoritam osim ovih :)

- za sad imam rekurzivni
- isti taj preko dinamičkog
- preko matrica

I ovaj Fast Doubling mi nije jasan ako može neko da mi pojasni :D
http://nayuki.eigenstate.org/page/fast-fibonacci-algorithms

Volio bih da ima još jedan da nabacim još koju stranicu :D

I da li neko zna par zadataka koji u pozadini koriste fibonačijeve brojeve, ali da to nije lako uočljivo. Znači zadaci IOI (Informatička olimpijada it Informatike) tipa, što znači da ima viče rješenja ali da se svako rješenje drugačije boduje. Na primer brute force pristup je 20%, neka njegova optimizacija je 40%, onda neko rešenje koristeći neku strukturu je 70% i za 100% treba neka caka sa fibonačijevim brojevima. Na primer "Problem zečeva" je ovog tipa :D

[Belphegor]

Imas isto "template meta-programming fibonacci" compile-time izracunavanje, doduse i to je rekurzivno a i ograniceno je koliko u "dubinu" moze da ide u zavisnosti od kompajlera.

[clzola]

Znaci ideja je da napravim templeate klasu koja zracunava fibonacijeve brojeve zbog svojstva C++ da template kompajlira (generise kod, kako li vec xD) i kasnje samo treba da u main napravim klasu pomocu template koja mi vrace taj niz ili n-ti fibonacijev broj?

[Belphegor]

Pa obicno koriste fibonacci-jev broj kao primer meta-programming.


template < std::size_t N >
struct fib
{
enum { value = fib<N - 1>::value + fib<N - 2>::value };
};

template <>
struct fib<0>
{
enum { value = 0 };
};

template <>
struct fib<1>
{
enum { value = 1 };
};

...

std::cout << fib<30>::value << std::endl;