liczby fibonacciego - algorytm

[kkk]

Witam! Poszukuję algorytmu na wyznaczenie kolejnych liczb ciągu fibonacciego. Jak ktoś posiada linki to prosze o wrzucenie. Z góry dzięki za pomoc

[soku11]

Kod: Zaznacz cały

long Fibonacci( unsigned int which )
{
  if( which==0 ) return 0;
  if( which==1 ) return 1;
  long Prev=0;
  long Act=1;
  long Tmp=0;
  for( unsigned int i=2;i<=which;++i )
  {
    Tmp=Prev+Act;
    Prev=Act;
    Act=Tmp;
  }

  return Act;
}

O ja widze to jakos tak Funkcja zwraca liczbe o numerze 'which' z ciagu Fibonnaciego. Zastosowanie czyli wypisanie np 10 poczatkowych:

Kod: Zaznacz cały

for( int i=0;i<10;++i )
  std::cout<<Fibonacci(i);

POZDRO

[eloar]

No moze jeszcze rekurencyjny Fibonacci?

Kod: Zaznacz cały

long fib(int n)
{
  if(!n) return 0;
  if(n==1) return 1;
  return fib(n-1)+fib(n-2);
}

Funkcja ta jest pozornie prosta i latwa w przygotowaniu, ale wersja iteracyjna jest mimo wszystko lepsza i szybsza, a do tego wersja iteracyjna dziala dla wyzszych liczb. Warto jednak pamietac o wersji rekurencyjnej algorytmu, poniewaz jest to zadanie podstawowe z rekurencji.

Aby zbadac dlaczego wersja rekurencyjna jest niewydajna wystarczy rozrysowac sobie drzewo wywolan tak powiedzmy dla n=5 . Ale w sumie nie musi Cie to interesowac .

[nivwusquorum]

No tak, ale w sumie to można napisać zdecydowanie szybszy program,
Wystarczy macież
1 1
1 0
podnieść do potęgi n-tej. Wtedy wychodzi macież(dla fib(0)=0
fib(n+1) fib(n)
fib(n) fib(n-1)
A, że macieże da się łatwo potęgować w czasie lg n no to nasz program działa szybciej prawie o rząd. Oczywiście można obliczać fib(n) w czasie stałym, ze wzoru jawnego, ale wymaga to już pewnej wprawy, bo zapisanie sqrt(5) na liczbach zmiennoprzecinkowych może się okazać niedokładne.

[MGT]

Ktoś tu wspominał o rekurencji. Dla liczb, powiedzmy Fib(x

[mol_ksiazkowy]

ale w Pascalu to chyba petla for robi:
a:=1
b:=0
for j:=1 to n do
begin
a:=a+b;
b:=a-b;
end;
write(b, "=Fn");

[eloar]

MGT, nawet wspomniał coś o drzewie wywołań, tak więc odnosząc się do Twojej wypowiedzi powiem, że mija się to z celem...

[MGT]

późno jest, więc mogę się mylić, ale śmiem twierdzić, że jak zrobisz to dynamicznie, to drzewo wywołań wcale się nie rozrośnie. Dla x=5 będzie 8 wywołań funkcji, gdzie w czterech przypadkach zwróci ona wynik w czasie stałym. Nie twierdzę, że to lepsza metoda (choćby ze względu na bardzo dużą złożoność pamięciową), ale warto czasem inaczej spojrzeć na temat

[kkk]

dziękuję wszystkim za pomoc, pozdrawiam

[eloar]

MGT, chodzi o to, że funkcja jest wielokrotnie niepotrzebnie wywoływana dla tych samych wartości i odkładana na stosie. Głównie dlatego wersja rekurencyjna szybko się "zapycha". Zasoby się szybko wyczerpują. Wersja iteracyjna w zależności od wybranego typu liczby może spokojnie podać ponad 200 kolejnych liczb fibonacciego i to w krótkim czasie.

[MGT]

nie chcę tu prowadzić niepotrzebnej dyskusji
w każdym zwykła rekurencyjna i owszem, jednak dynamiczna rekurencyjna działa niemal identycznie jak iteracyjna, a liczba wykonań nie jest wykładnicza, jak przy zwykłej metodzie rekurencyjnej, a liniowa. (rzecz w tym, że w dynamicznej metodzie, jeśli wywołujesz drugi raz funkcję z takim samym parametrem, to dostajesz odpowiedź natychmiast, a więc kolejnych wywołań już nie ma). fakt, faktem, w pewnym momencie pojawia się problem kolejnych wywołań funkcji, ale tą przeszkodę można banalnie wyeliminować nie wpływając na złożoność, czy czas działania. Mi chodzi tylko i wyłącznie o to, że złożoność jest taka sama.
tylko i aż tyle, pozdrawiam.

[eloar]

MGT, no chyba, ze tak. w wolnej chwili sprobuje bardziej zglebic to zagadnienie.