Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?

Wyznaczanie modulo z ciągu fibonacciego

Ostatnio zmodyfikowano 2017-11-07 19:00
Autor Wiadomość
garlonicon
» 2017-10-28 20:44:28
dlaczego program wywala dla f(100)?
Bo stos rośnie bardzo szybko. Zauważ, że:
C/C++
f( 100 ) = f( 99 ) + f( 98 );
f( 99 ) = f( 98 ) + f( 97 );
f( 98 ) = f( 97 ) + f( 96 );
Czyli:
C/C++
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.
P-166151
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?
P-166152
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

C/C++
#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; //an wyliczany wyraz ciągu; an_1 poprzedni wyraz ciągu; an_2-wyraz ciągu drugi od końca
        for( int i = 3; i <= n; i++ ) {
            an =( an_2 + an_1 ) % m;
            an_2 = an_1;
            an_1 = an;
        }
        cout << an << endl;
    }
}
P-166153
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.
P-166154
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).
P-166155
mateczek
» 2017-10-28 21:11:12
ten co wkleiłem przekracza limit?? czasowy ??
P-166156
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
P-166157
garlonicon
» 2017-10-28 21:17:49
Spróbuj użyć odejmowania zamiast modulo. Poza tym, dla
m == 1
 od razu znasz wynik.
P-166158
1 « 2 » 3 4 5 6 7
Poprzednia strona Strona 2 z 7 Następna strona