Problème avec Fibonacci et les grands nombres
eva
-
KX Messages postés 19031 Statut Modérateur -
KX Messages postés 19031 Statut Modérateur -
Bonjour,
J'ai un problème avec trois fonctions qui calculent le nombre de Fibonacci, normalement je dois calculer le temps de leurs exécution et les comparer et delà dans plusieurs cas, mais quand je mets un grand nombre j'obtient un résultat très bizarre genre -9264578..... !
voici un exemple de fonction :
#include<stdio.h>
#include <time.h>
int fibo1(int n){
if(n<2){
return n;
}
else{
return fibo1(n-1)+fibo1(n-2);
}
}
int main(){
clock_t tempsDebut, tempsFin;
int n,x;
printf("Veuillez saisir un entier positif\n");
scanf("%d",&n);
tempsDebut = clock();
x=fibo1(n);
tempsFin = clock();
printf("Le résultat du calcul de Fibonacci pour n=%d est: %d\n",n,x);
printf("L'exécution de la fonction Fibo1 a mis %.332f \n", (long)(tempsFin - tempsDebut) / CLOCKS_PER_SEC);
system("pause");
return 0;
}
J'ai un problème avec trois fonctions qui calculent le nombre de Fibonacci, normalement je dois calculer le temps de leurs exécution et les comparer et delà dans plusieurs cas, mais quand je mets un grand nombre j'obtient un résultat très bizarre genre -9264578..... !
voici un exemple de fonction :
#include<stdio.h>
#include <time.h>
int fibo1(int n){
if(n<2){
return n;
}
else{
return fibo1(n-1)+fibo1(n-2);
}
}
int main(){
clock_t tempsDebut, tempsFin;
int n,x;
printf("Veuillez saisir un entier positif\n");
scanf("%d",&n);
tempsDebut = clock();
x=fibo1(n);
tempsFin = clock();
printf("Le résultat du calcul de Fibonacci pour n=%d est: %d\n",n,x);
printf("L'exécution de la fonction Fibo1 a mis %.332f \n", (long)(tempsFin - tempsDebut) / CLOCKS_PER_SEC);
system("pause");
return 0;
}
A voir également:
- Rémi et safia ont découvert le code binaire des nombres en cours d'informatique. ils l'utilisent pour se donner des rendez-vous secrets. ils ont décidé que : un message comporte 5 bits et donne le jour puis le moment les jours et les moments sont traduits par les nombres comme ci-dessous
- Le code ascii en informatique - Guide
- Comment déverrouiller un téléphone quand on a oublié le code - Guide
- Nombre de jours entre deux dates excel - Guide
- Code binaire des nombres - Guide
- Winrar 64 bits - Télécharger - Compression & Décompression
1 réponse
Ton problème provient sans doute du dépassement de capacité du type Int : Le bit de signe est le poids le plus élevé donc si tu dépasse 2^31, tu passe en nombre négatif...
Pour contourner ce problème il suffit de passer à un type 64 bits.
Et es-tu obligée de relever le temps d'exécution d'une méthode particulièrement lente ? Car L'approche utilisée dans la fonction Fibo1 est horriblement coûteuse en calculs ! Une meilleure méthode serais de partir du début et calculer jusqu'à l'indice voulu : en conservant les deux valeurs précédentes, on les additionnes pour calculer une nouvelle valeur, on garde les deux dernières, etc...
De toute façon, ta méthode sera très vite limitée par la taille de pile, car chaque fonction en appelle une autre...
Le chêne aussi était un gland, avant d'être un chêne
Pour contourner ce problème il suffit de passer à un type 64 bits.
Et es-tu obligée de relever le temps d'exécution d'une méthode particulièrement lente ? Car L'approche utilisée dans la fonction Fibo1 est horriblement coûteuse en calculs ! Une meilleure méthode serais de partir du début et calculer jusqu'à l'indice voulu : en conservant les deux valeurs précédentes, on les additionnes pour calculer une nouvelle valeur, on garde les deux dernières, etc...
De toute façon, ta méthode sera très vite limitée par la taille de pile, car chaque fonction en appelle une autre...
Le chêne aussi était un gland, avant d'être un chêne
Il y aura plus d'appel dans la pile que la valeur du résultat attendu...
Une boucle for est effectivement bien moins coûteuse pour ce problème [O(n) contre O(1.618^n)]
Après je doute qu'un type 64 bits soit toujours suffisant, mais il y a des librairies de calculs comme GMP
Et pour autant que je me représente bien le déroulement, chaque fonction appelle bien une seule fonction, car elle les appelle l'une après l'autre...
Il est donc en effet probable que pour la pile la complexité en espace soit linéaire, mais ça ne change rien à la complexité en temps qui reste exponentielle avec la méthode récursive !
Remarque (en supposant n=0 --> 1, n=1-->1)
Avec des types sur 32 bits on peut atteindre au maximum n=46 (unsigned int / unsigned long int)
Avec des types sur 64 bits on peut atteindre au maximum n=92 (unsigned long long int)
Donc ça reste effectivement assez limité, mais avec GMP on peut aller bien au delà (autant que voulu)