Fibonacci oraz modulo ze SPOJ-a – przekroczono limit czasu

0

Cześć mam oczywiście ze spoja które brzmi następująco:

  1. W pierwszym wierzy masz podać ilość Testów x<=100
  2. 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> 
#include <stdio.h>
using namespace std;

int fib(int n){

if(n==1 || n==2)
	return 1;


return fib(n-1)+fib(n-2);
	
	}
	


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 wyskakuje brzmi że przekroczono limit czasu czy jesteś w stanie mi powiedzieć co robię źle ? i jak to poprawić ?

0

2)W następnych liniach T liczby Ni<=2^2

2^2 to 4, więc zapisz po prostu w tablicy pierwsze cztery wartości ciągu fibonacciego zamiast je ciągle wyliczać. Dla tak małych wartości to nie ma znaczenia, ale już przy kilku więcej będziesz marnował bardzo dużo czasu na wyliczenie czegoś, co dawno już policzyłeś.

0

To nie było 2^2 ale 10^9+7

Mój błąd mam wiele kart mam otworzonych.Za zamieszania przepraszam.

Poprawione.

0

Ok , czy teraz jak już treść zadanie jest prawidłowa mógła/a byś mnie nakierować na jego prawidłowe rozwiązanie.?

1

To rozwiązanie jest w wykładnicze, nie ma szans czasowych. Znajdź algorytm szybkiego liczenia Fibonacci, Pamiętaj, czym jest suma dwóch liczb modulo, oraz Poszukaj pomocnego faktu, jaki spełniaja takie rekurencyjne zalezności modulo.

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