Suite de Fibonacci

Dans cette feuille, vous allez implanter les trois algorithmes vus en TD pour calculer la suite de Fibonacci.

#include <iostream>
#include <vector>
using namespace std;

Exercice (Fibonacci, version tableau)

  • Écrire la documentation puis implanter la fonction fibonacciTableau:

// VOTRE CODE ICI
int fibonacciTableau(int n) {
    // VOTRE CODE ICI
}
  • Vérifier que votre fonction passe les tests:

CHECK( fibonacciTableau(1) == 1 );
CHECK( fibonacciTableau(2) == 1 );
CHECK( fibonacciTableau(3) == 2 );
CHECK( fibonacciTableau(4) == 3 );
CHECK( fibonacciTableau(5) == 5 );
CHECK( fibonacciTableau(6) == 8 );
CHECK( fibonacciTableau(9) == 34 );

Exercice (Fibonacci, version trois variables)

  • Écrire la documentation puis implanter la fonction fibonacciVariables:

// VOTRE CODE ICI
int fibonacciVariables(int n) {
    // VOTRE CODE ICI
}
  • Tests :

CHECK( fibonacciVariables(1) == 1 );
CHECK( fibonacciVariables(2) == 1 );
CHECK( fibonacciVariables(3) == 2 );
CHECK( fibonacciVariables(4) == 3 );
CHECK( fibonacciVariables(5) == 5 );
CHECK( fibonacciVariables(6) == 8 );
CHECK( fibonacciVariables(9) == 34 );

Exercice (Fibonacci, version récursive)

  • Écrire la documentation puis implanter la fonction fibonacciRecursive:

// VOTRE CODE ICI
int fibonacciRecursive(int n) {
    // VOTRE CODE ICI
}
  • Tests :

CHECK( fibonacciRecursive(1) == 1 );
CHECK( fibonacciRecursive(2) == 1 );
CHECK( fibonacciRecursive(3) == 2 );
CHECK( fibonacciRecursive(4) == 3 );
CHECK( fibonacciRecursive(5) == 5 );
CHECK( fibonacciRecursive(6) == 8 );
CHECK( fibonacciRecursive(9) == 34 );
  • ♣ Exécuter la version récursive avec une grande valeur pour n (par exemple 200).

  • Que se passe-t-il? VOTRE RÉPONSE ICI

  • ♣ A votre avis, est-il possible de remédier à ce problème?