Wyznaczanie modulo z ciągu fibonacciego
Ostatnio zmodyfikowano 2017-11-07 19:00
garlonicon |
» 2017-10-28 20:44:28 dlaczego program wywala dla f(100)? |
Bo stos rośnie bardzo szybko. Zauważ, że: f( 100 ) = f( 99 ) + f( 98 ); f( 99 ) = f( 98 ) + f( 97 ); f( 98 ) = f( 97 ) + f( 96 ); Czyli: f( 100 ) = f( 98 ) + f( 97 ) + f( 97 ) + f( 96 );
Jak zaczniesz to sobie rozpisywać dalej, to zobaczysz, że zanim dojdziesz do jakiegokolwiek wyniku potrzebujesz mnóstwa wywołań funkcji f . A każde takie wywołanie powoduje przyrost stosu. Zobaczysz również, że obliczasz w kółko te same wyniki pośrednie. To jeśli nie tym to jakim sposobem liczyć ciąg fibonacciego? |
Ustaw sobie dwie zmienne zawierające dwa kolejne wyrazy ciągu fibonacciego i po kolei obliczaj kolejne wartości. Dlaczego modulo jest wewnątrz pętli? |
Skoro to ma być modulo, to jeśli wynik przekroczy m , to możesz użyć reszty z dzielenia. |
|
jatoprzechuj Temat założony przez niniejszego użytkownika |
» 2017-10-28 20:52:48 No tak, ale reszta z dzielenia nie powinna byc dopiero po obliczeniu liczby z ciągu? |
|
mateczek |
» 2017-10-28 20:53:33 możesz dać na zewnątrz ale wtedy musisz operować na wielkich liczbach (wewnątrz jest dla optymalizacji) (5+8)%4= 5%4+8%4=1 #include <iostream> using namespace std; int main() { int t, n, m; cin >> t; while( t-- ) { cin >> n >> m; int an_1 = 1, an_2 = 1, an = 1; for( int i = 3; i <= n; i++ ) { an =( an_2 + an_1 ) % m; an_2 = an_1; an_1 = an; } cout << an << endl; } } |
|
jatoprzechuj Temat założony przez niniejszego użytkownika |
» 2017-10-28 21:05:57 Dzięki, teraz rozumiem działanie. A czy oprócz zmiany obliczania liczb z ciągu da się jeszcze jakoś przyspieszyć algorytm? Po prostu w sprawdzarce dostaje time limit exceeded. |
|
garlonicon |
» 2017-10-28 21:07:48 Tak, używając odejmowania zamiast modulo (bo przy sumie dwóch liczb wystarczy wykonać je co najwyżej raz). |
|
mateczek |
» 2017-10-28 21:11:12 ten co wkleiłem przekracza limit?? czasowy ?? |
|
jatoprzechuj Temat założony przez niniejszego użytkownika |
» 2017-10-28 21:15:12 Tak, Pierwszy test zalicza, lecz drugi wyrzuca błąd TLE |
|
garlonicon |
» 2017-10-28 21:17:49 Spróbuj użyć odejmowania zamiast modulo. Poza tym, dla m == 1 od razu znasz wynik. |
|
1 « 2 » 3 4 5 6 7 |