Fibonacci A2OJ

m_bess Messages postés 6 Date d'inscription   Statut Membre Dernière intervention   -  
Dalfab Messages postés 706 Date d'inscription   Statut Membre Dernière intervention   -
Bonsoir,
Je cherche à réaliser un programme qui calcul les termes de la suite de fibonacci dans A2OJ.
Voici mon code: 
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main ()
{long x,i,max=2,t=1,f[100001];
f[0]=0;
        f[1]=1;
 for (i=2;i<=100000;i++)
        f[i]=(f[i-1]%10+f[i-2]%10)%10;
    while (scanf("%li",&x))
       { if (x>100000)
       return 0;
       if (t>=100000)
       return 0;


        t++;
        printf("%li\n",f[x]%10);

    }

    return 0;}

Mais le résultat est toujours "Time Limit Exceeded"!!
Voici l'énoncé :
Problem Statement:
In this problem we don't care about the actual values of the Fibonacci sequence, we need to know just the last digit, too simple.

F (0) = 0;
F (1) = 1;
F (n) = F (n-1) + F (n-2);


Input Format:
The input consist of multiple lines (<100,000), each has one integer n: 0 <= n <= 100000.


Output Format:
For each line of the input, output the last digit of the term F (n).


Sample Input:
5
13
70007


Sample Output:
5
3
3
Pouvez-vous m'aider SVP?

1 réponse

Réponse 1 / 1
Dalfab Messages postés 706 Date d'inscription   Statut Membre Dernière intervention   101
 
Bonjour,
Le code me semble ok, il manque peut-être d'optimisations (taille et opérations inutiles) 
long x, i, t=1;
unsigned char f[100000+1]; // suffisant pour un chiffre
f[0]=0;
f[1]=1;
for (i=2;i<=100000;i++)
    f[i]=(f[i-1]+f[i-2])%10; // pas de modulo sur f[] ils sont déjà des chiffres
while (scanf("%li", &x))
{   if (x > 100000)
         return 0;               // test vraiment nécessaire ?
     if (t >= 100000)
         return 0;               // test vraiment nécessaire ?
    t++;
    printf("%li\n", f[x]);   // pas de modulo sur f[] ils sont déjà des chiffres
}

A compiler en release pour le temps d'exécution
0