Liczby Fibonacciego - szybsze rozwiązanie
Ostatnio zmodyfikowano 2015-03-06 17:55
Malina94 Temat założony przez niniejszego użytkownika |
Liczby Fibonacciego - szybsze rozwiązanie » 2015-03-06 15:45:24 Mam za zadanie napisać program obliczający liczby fibonacciego. Niestety prosta rekurencja lub opisanie kodu w pętli to za mało, bo program wykonuje się za długo. Mogę skorzystać z tych zależności
F(2n) = F(n) (F(n) + 2 F(n - 1))
F(2n + 1) = F(n + 1)^2 + F(n)^2
plus dodatkowo część wartości trzymać w tablicy, ale nie bardzo wiem jak ich użyć. Czy ktoś mógłby mi podpowiedzieć jak je wykorzystać? |
|
pekfos |
» 2015-03-06 15:51:55 Całkiem wyraźnie widać, że jedna zależność dotyczy obliczania liczby fibonacciego dla parzystego argumentu, a druga dla nieparzystego. Mając wybraną zależność możesz redukować duże liczby do mniejszych, których obliczenie jest szybsze. No i oczywiście możliwie dużo liczb buforuj w tablicy. |
|
Malina94 Temat założony przez niniejszego użytkownika |
» 2015-03-06 16:11:09 Okej, dzięki :)
|
|
Malina94 Temat założony przez niniejszego użytkownika |
» 2015-03-06 17:23:28 Chodziło o coś takiego? cin >> n;
if( n % 2 == 0 ) {
wynik =( f( n / 2 ) *( f( n / 2 ) + 2 * f( n / 2 - 1 ) ) ) % 70001;
}
else {
wynik =( f( n / 2 + 1 ) * f( n / 2 + 1 ) + f( n / 2 ) * f( n / 2 ) ) % 70001;
}
cout << wynik << endl;
f(n) - funkcja obliczająca liczbę za pomocą pętli Najgorsze jest to, że testy obejmują takie n: n < 10^4, 10^7 i 10^10. Dla n = 10^7 wynik jest niemal od razu, ale dla wyższych nadal trzeba sporo poczekać. |
|
aksen |
» 2015-03-06 17:28:49 Pokaż kod f(n).
(a najlepiej kod całego programu) |
|
Malina94 Temat założony przez niniejszego użytkownika |
» 2015-03-06 17:55:25 już ogarnęłam, zamykam |
|
| « 1 » |