liczby fibonacciego - algorytm
-
- Użytkownik
- Posty: 578
- Rejestracja: 2 paź 2007, o 19:48
- Płeć: Mężczyzna
- Lokalizacja: ww
- Podziękował: 59 razy
- Pomógł: 35 razy
liczby fibonacciego - algorytm
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
-
- Użytkownik
- Posty: 6607
- Rejestracja: 16 sty 2007, o 19:42
- Płeć: Mężczyzna
- Podziękował: 119 razy
- Pomógł: 1823 razy
liczby fibonacciego - algorytm
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;
}
Kod: Zaznacz cały
for( int i=0;i<10;++i )
std::cout<<Fibonacci(i);
- eloar
- Użytkownik
- Posty: 106
- Rejestracja: 18 cze 2007, o 16:59
- Płeć: Mężczyzna
- Lokalizacja: Kobyłka
- Podziękował: 8 razy
- Pomógł: 12 razy
liczby fibonacciego - algorytm
No moze jeszcze rekurencyjny Fibonacci?
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 .
Kod: Zaznacz cały
long fib(int n)
{
if(!n) return 0;
if(n==1) return 1;
return fib(n-1)+fib(n-2);
}
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 .
-
- Użytkownik
- Posty: 93
- Rejestracja: 31 maja 2007, o 17:53
- Płeć: Mężczyzna
- Lokalizacja: Chojnice
- Podziękował: 1 raz
- Pomógł: 3 razy
liczby fibonacciego - algorytm
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.
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.
- mol_ksiazkowy
- Użytkownik
- Posty: 11367
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3153 razy
- Pomógł: 747 razy
liczby fibonacciego - algorytm
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");
a:=1
b:=0
for j:=1 to n do
begin
a:=a+b;
b:=a-b;
end;
write(b, "=Fn");
-
- Użytkownik
- Posty: 107
- Rejestracja: 7 lis 2006, o 12:03
- Płeć: Mężczyzna
- Lokalizacja: Gdańsk
- Pomógł: 20 razy
liczby fibonacciego - algorytm
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
- eloar
- Użytkownik
- Posty: 106
- Rejestracja: 18 cze 2007, o 16:59
- Płeć: Mężczyzna
- Lokalizacja: Kobyłka
- Podziękował: 8 razy
- Pomógł: 12 razy
liczby fibonacciego - algorytm
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.
-
- Użytkownik
- Posty: 107
- Rejestracja: 7 lis 2006, o 12:03
- Płeć: Mężczyzna
- Lokalizacja: Gdańsk
- Pomógł: 20 razy
liczby fibonacciego - algorytm
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.
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.