Suite de Fibonacci

Version imprimable

Suite de Fibonacci

Bonjour,

J'ai créer une petite fonction destinée à calculer le n-ième terme de la suite de Fibonacci : 1,1,2,3,5,8,13 ... (chaque terme égale la somme des deux précédents)

Pourriez-vous y jeter un coup d'oeil (tout marche, tout fonctionne mais j'aimerais avoir votre avis ...) :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
/* Suite de Fibonacci, chaque terme est égale à la somme de deux précdents : 1,1,2,3,5,8 ...
Le n ième terme est donc la somme des termes (n-1) et (n-2) si n>2 (n entier positif) */
long int fib(unsigned int n)
{
     long int resultat=1;                    // Le n ième terme
     long int terme_1 = 1, terme_2 = 1;      // Les termes n-1 et n-2
 
     if (n < 3) return 1;
 
     resultat = 2;
     for (int C=3; C<=n; C++)
     {
         // n = (n -1) + (n - 2)
         resultat = terme_1 + terme_2;
         /* Logiquement, lorsqu'on passe au terme suivant, le terme (n-1)devient le terme (n - 2) et le terme (n - 2) devient le terme n */
         terme_1 = terme_2;
         terme_2 = resultat;
     }
     return resultat;
}

Est ce qu'il y certaines choses que j'ai faites de travers (niveau de l'algo) ? Y a il des améliorations a apportées ?

merci :wink:

19/07/2005, 22h53
capitN.flam

la première chose que tu peux changer c'est le type de retour etant donné que ce sera toujours un nombre >0 tu peux retourner un unsigned long de plus tu prends en paramètre un unsigned donc...

en ce qui concerne la méthode en elle même étant donné que je n'ai codé fibonacci qu'en récursif je ne peux pas te dire si elle est bonne ou pas mais comme tu dis que cela fonctionne c'est que cela doit être vrai.

bonjour,

la suite de Fibonacci commence à 0

conditions initiales :
F(0)=0
F(1)=1

suite:
F(n)=F(n-1)+F(n-2)

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
type1 Fib(type2 n)
{
   type1 F" = 0;
   type1 F' = 1;
   type1 F = F";
 
   for (int i = 0; i <= n; i++)
   {
      F = F" + F';
      F" = F';
      F' = F;
   }
   return F;
}

20/07/2005, 14h19
Évariste Galois
Citation:

Envoyé par capitN.flam

la première chose que tu peux changer c'est le type de retour etant donné que ce sera toujours un nombre >0 tu peux retourner un unsigned long de plus tu prends en paramètre un unsigned donc...

Bonne idée, je vais changer ça :)

Citation:

Envoyé par bigboomshakala

la suite de Fibonacci commence à 0

Ah, dans mon livre C++ il prétendent que cela commence à 1 ...

Sinon ils proposent (dans le livre) une méthode en récursif :
Code:

1 2 3 4 5 6 7 8 int fib(int n) { if (n < 3) return 1; else return (fib(n-2) + fib(n-1)); }
Mais il parait qu'elle n'est pas très efficace (ils ne précisent pas pourquoi). Ma fonction est elle plus efficace que celle-ci ? Si oui pourquoi ?

merci
20/07/2005, 14h27
Évariste Galois

Oh oui. Ma fonction est bien plus rapide que celle utilisant la récursivité, mais je ne compend pas pourquoi ...

Faut-il en conclure que la récursivité est une méthode à proscrire lorsque c'est possible ?

merci
20/07/2005, 15h02
Tarrke
De mémoire :

lorsque tu fait une fonction récursive tu l'appel un nombre important de fois, à ce moment là le temps d'appel de la fonction entre en compte devant le temps de calcul.
Si tu appel 100 fois la même fonction avec 0.01 sec de temps d'appel et 0.1 sec de temps de calcul tu mettra 11 sec au lieu des 10 sec de temps de calcul.
La récursivité est bien mais pas top niveau performances.

tu peux faire le même essait avec le calcul de factoriel :
Code:

1 2 3 4 5 unsigned long fact( int n ) { if( n <= 2 ) return n; return n*fact( n-1 ); }
ou alors la version plus rapide :
Code:

1 2 3 4 5 6 7 8 9 unsigned long fact( int n ) { unsigned long res = 1; for( int i = n; i > 1; --i ) { res *= i; } return res; }
et là tu devrait voir la différence...

Tarrke
20/07/2005, 20h11
Évariste Galois

Ah bon, eh bien oui en fait c'est logique.
Chaque appel de fonction ralentit le programme. Et la récursivité ce n'est pas évident à maîtriser ...

Bon, conclusion -> vive les boucles for :mrgreen:

merci
21/07/2005, 08h53
Tarrke

De rien,

mais n'oublie pas, la programmation en réccursif est plus facil pour certains, en effet beaucoup de mathématiciens préfèrent un algo récursif car il le comprennent, mais à nous de le dérécursifier si possible.
Il ne faut pas bannir le récursif pour ses performances, une heure de codage et une heure d'execution valent peut-être meiux que dix heures de codage et 30 minutes d'execution non ?

Ravis d'avoir pu aider
Tarrke
21/07/2005, 10h30
JolyLoic

+1, surtout si on rajoute 5 minutes de maintenance d'un côté, et 5 jours de l'autre ;)

Pour info, il existe des cas de récursivité qu'un compilateur est à même d'optimiser plus aisément (cherche récursivité terminale pour plus d'info), mais on commence généralement à perdre en clarté et simplicité du code.

Enfin, en terme de performances, notons qu'il est possible si l'on souhaite calculer la valeur d'un membre dont le rang est connu au moment de la compilation de calculer cette valeur à la compilation elle aussi. Et là, comme pour tout calcul à la compilation, la récursivité est la seule méthode disponible.
21/07/2005, 13h36
Évariste Galois

Citation:

Envoyé par JolyLoic

comme pour tout calcul à la compilation, la récursivité est la seule méthode disponible

Ah, ça je ne savais pas tient.
De toute façon je ne jette pas la récursivité, je suppose que ça me servira bien un jour ... :wink:

merci

et puis faire de la récursivité n'empèvhe pas de réfléchir!
essayez ce programme, deux fonction qui calcule le nième terme de suite de fibonaci:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>
 
int string2int(char* s, int p = 0){
  if( *s != '\0' )
    return string2int(s+1, 10*p + *s -'0');
  else return p;
}
 
unsigned long fibonaci_recur(unsigned int n){
  if(n<2)return 1;
  else return fibonaci_recur(n-1) + fibonaci_recur(n-2);
}
 
unsigned long fibonaci_updated(unsigned int n){
  if(n<2)return 1;
  else {  // n>=2
    int fm2 = fibonaci_updated(n-2), fm3 = 0;
    if(n>2) fm3 = fibonaci_updated(n-3);
    return 2*fm2 + fm3;
  }
}
 
using namespace std;
 
int main(int argc, char* argv[]){
  if(argc<2)cerr << "Il faut un argument !" << endl;
  int n = string2int(argv[1]);
 
  cout << "lancement fonction 1..." << endl;
  cout << "le résultat est : " << fibonaci_recur(n) << endl << endl;
 
  cout << "lancement fonction 2..." << endl;
  cout << "le résultat est : " << fibonaci_updated(n) << endl << endl;
}

je ne sais pas comment chronométré alors je ne l'ai pas fait. si quelqu'un veux le faire ;)

ne pas oublier aussi que le C++ n'est pas spécialement optimiser pour la récursivité, un language tel que le CAML est beaucoup plus efficace dans ce domaine.

21/07/2005, 19h22
bruno_pages

oui C++ n'est pas le meilleur pour gerer les recursions, mais de toute facon une vraie gestion ne peut se faire qu'avec un interpreteur, et des langages que je connais la palme revient à Lisp de ce cote : Vlisp & LeLisp (et mon lisp et logo persos sur Goupil il y a pret de 20 ans !) traitait par exemple les recursions "enveloppé" du type de celle de factorielle en recursif : (* n (fact (- n 1))) qui n'empilait rien car la multiplication etait faite tout de suite et non au retour. Ceci est théoriquement possible à faire avec un langage compile même si ce n'est pas le cas, par contre les cas de recursions croisées (A appelle B qui appelle A etc ..., ou avec plus de fonctions intermediaires) sont plus dure à traiter à la compilation.

A part cela la récursion permet de faire des codes concis et clairs, ce ne sont pas les tours de hanoi qui vont me contredire :D
22/07/2005, 20h44
Évariste Galois

Citation:

et puis faire de la récursivité n'empèvhe pas de réfléchir!

Ah ben non, pour moi la récursivité ça oblige à réfléchire :wink:

merci
22/07/2005, 21h21
bigboomshakala

:resolu: :?:

Si oui, mettre le tag pour que tout le monde le sache.
merci