Wczytywanie liczb Fibonacciego i błędna odpowiedź – dlaczego?

0

Cześć mam które brzmi następująco:

W pierwszym wierzy masz podać ilość Testów x<=100
W następnych liniach T liczby Ni<=10^9+7
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)
{

    const unsigned int M = 1000000007;
int elementA=0;
int elementB=1;
int wynik=0;

if(n<2)
    return n;

for(int i=2;i<=n;i++){

wynik=(elementA+elementB)%M ;
elementA=elementB;
elementB=wynik ;
}
return wynik ;

}

int main()
{
int n;

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

    cout<< fib(n);

 }
return 0;

}

Na spoju mój problem brzmi "Błąd odpowiedzi". W czym problem i jak go zjeść ?

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

int fib(int n)
{

int elementA=0;
int elementB=1;
const unsigned int M = 1000000007;
int wynik;

if(n<2)
    return n;

for(int i=2;i<=n;i++){

wynik=(elementA+elementB)%M;
elementA=elementB;
elementB=wynik ;
}
return wynik ;

}

int main()
{
int n;

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

    cout<< fib(n)<<endl;;

}

return 0;

}

Kod poprawiony i wyrzuca bląd Przekroczono limit czasu .

0

Jesli(a + b) mod m = c to (a mod m + b mod m) mod m = c. Czyi Masz za Malo mod:). Testuj sobie dla malych liczb I Sprawdzaj wyniki.

0

Nie wiem czy ciebie dobrze rozumiem mój bląd jest w tym miejscu tak ?

for(int i=2;i<=n;i++){

wynik=(elementA+elementB)%M;
elementA=elementB;
elementB=wynik ;
}
return wynik ;

powinno być ?

for(int i=2;i<=n;i++){

wynik=(elementA%M+elementB%M)%M;
elementA=elementB;
elementB=wynik ;
}
return wynik
0

No to teraz kombinuj jak przyspieszy obliczania. Jest kilka sposobów.
Twój obecny algorytm ma złożoność o(n) a da się szybciej .
Jeśli przedstawisz obliczania ciągu Fibonacciego jako rachunek macierzowy, to potem można użyć algorytmu szybkiego potęgowania. i dostaniesz złożoność o(log n).

A jeszcze popraw tak, żeby IO nie było wąskim gardłem:

int main()
{
    int n;
    int ile;

    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

        cout << fib(n) << '\n';
    }
    return 0;
}
0
#include<iostream> 
#include<cstdlib> 
#include <math.h>
#include <cstdio>
using namespace std;

int fib(int n)
{

int elementA=0;
int elementB=1;
const unsigned int M = 1000000007;
int wynik;

if(n<2)
    return n;

for(int i=2;i<=n;i++){

wynik=(elementA+elementB)%M;
elementA=elementB;
elementB=wynik ;
}
return wynik ;

}

int main()
{

std::ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
int ile;
cin >> ile;

if(ile>100)
     return 100;

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

    cout<< fib(n)<<'\n';
    }
 return 0;

}

Teraz kod wygląda w następujący sposób lecz problemem jest przekroczony limit czasu , poprzednio nie miałem zakończenia linii i wyskakiwał mi błąd złego odczytu , teraz z tym przekroczeniem limitu czasu nie wiem co jest grane

0

Chcę nadmienić iż wolałbym pozostać przy takiej formie kodu niż bawić się z macierzami,jeśli ktoś z was wie z czym zjeść problem przekroczonego czasu . bardzo bym prosił o radę

0

Kod z użyciem scanfa również wyświetla błąd "przekroczony limit czasu"


#include<iostream> 
#include<cstdlib> 
#include <cmath>
#include <cstdio>
#include<stdio.h>

int fib(int n)
{

int elementA=0;
int elementB=1;
const unsigned int M = 1000000007;
int wynik;

if(n<2)
    return n;

for(int i=2;n>=i;i++){
wynik=(elementA+elementB)%M;
elementA=elementB;
elementB=wynik ;
}
return wynik ;

}

int main()
{

int n;
int ile;
scanf("%i",&ile);

if(ile>100)
     return 100;

for(int i=0;ile>i;i++){
   scanf("%i",&n);

    std::cout<< fib(n)<<'\n';
    }
 return 0;

}
0

Zobacz na moj ostatni post.

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0