Witam, napisałem metodę dla ciągu Fibonnacciego ale nie wiem czemu wylicza mi dla n+1 zawsze.Np dla 7 wylicza mi 21-tak jak powinno być dla 8. Ktoś podpowie ?
public class main {
public static int fib(int n){
if(n==0 || n==1)
return 1;
return fib(n-1) + fib(n-2);
}
public static void main(String[] args) {
System.out.print(fib(7));
}
}
Dla n=0 wynik powinien być 0 a Ty zwracasz 1, dlatego wszystko się przesuwa.
Początek ciągu: 1,1,2,3,5,8,13,21,...
Ty uważasz, że 21 jest ósmym wyrazem ciągu, ale w programie numerujesz wyrazy od zera. Wyraz 21 ma indeks siedem.
Dla n == 0 Twoja metoda zwróci 1, a powinna 0, przynajmniej jeżeli chcesz otrzymać takie wyniki, o których pisałeś. Wszystkie wyrazy ciągu są przesunięte o n-1 miejsc więc dla wyrazu nr 7 zwracana jest wartość tak jak dla wyrazu nr 8.
Powinno to wyglądać w ten sposób:
public static int fib(int n){
if (n == 0) return 0;
if (n > 0 && n < 3) return 1;
else return fib(n-1)+fib(n-2);
}
Zwrócę jeszcze uwagę na bardzo niewydajną metodę, każdy wyraz ciągu Fibonacciego jest obliczany przez sumowanie jedynek. Powinno się użyć rekurencji z zapamiętywaniem, stosunek czasu obliczeń w okolicy f(40) wynosi około 100 tysięcy.
@bogdans: zawsze można dopisać metodę iteracyjną i zrobić małego benchamarka. Sprawdźmy: http://ideone.com/LJVhyb
Przykładowy wynik dla 40'tego wyrazu (jednostka czasu: ms):
Recursive start: 0
Result: 102334155
Recursive stop: 586
Iteration start: 0
Result: 102334155
Iteration stop: 0
Różnicę widać od razu.
Dodatkowo kiedy odpali się to u siebie (bo ideone ma pewne ograniczenia) dla np 50 wyrazu to różnica jest kolosalna. Naturalnie trzeba było zmienić typ z int na long:
Recursive start: 0
Result: 12586269025
Recursive stop: 597376
Iteration start: 0
Result: 12586269025
Iteration stop: 0
Metodą rekurencyjną bez zapamiętywania liczył prawie 10min!
PS: Sorry za C# ale nie wiem jak się robi benchmarki w Jawie :P
Aż wrzucę: