Liczby Fibonaccieg a modulo

Question

Witam wszystkich mój problem polega na pewnym zadaniu ze spoja które brzmi następująco:

Mając daną liczbę N oblicz N-tą liczbę fibonacciego modulo 1000000007 = 10^9 +7.

W pierwszym wierszu liczba testów T<=100.

W następnych T liniach liczby Ni

Ni<=10^9

Dla każdego testu w osobnej linii Ni-ta liczba ciągu fibonacciego modulo 10^9+7

 

oto mój kod:

#include<iostream>
#include<cstdlib>
#include <math.h> 
using namespace std;

int fib(int n){
    
if(n==1 || n==2)
    return 1;
float x=(pow(10.0,9.0)+7);
return (fib(n-1)+ fib(n-2)%int(x));

    }

int main(){
    int ile;
    cin>>ile;
    if(ile>100)
        return 100;

    int n;
    for(int i=0;i<ile;i++){
    cin>>n;

   

cout<<fib(n)<<endl;
system("pause");

    }

    return 0;

}

Komunikat który mi wyskakuje brzmi że przekroczono czas.Czy jest ktoś w stanie mi pomóc z tym zadaniem ?

 

Answer 1

Rekurencja w takim wykonaniu jest bardzo wolna. Zobacz sobie, ile wykonujesz niepotrzebnie operacji np. żeby obliczyć 5 wyraz:

1) fibonacci(4) + fibonacci(3)

2) fibonacci(3)+fibonacci(2) + fibonacci(2) + fibonacci(1)

itd. Już tutaj można zauważyć, że w 1 i 2 kroku powtarza się fibonacci(3). W drugim kroku 2 razy musisz obliczyć fibonacci(2). Jeżeli to byłoby fibonacci(100) to zauważ ile niepotrzebnie razy będziesz wywoływał rekurencję.

Szybciej byłoby gdybyś zamiast rekurencji zastosował albo:

1) Iteracyjne podejście

2) Do rekurencyjnego podejścia, dołożył memoizację.