TP : 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 1 : Fibonacci, version tableau

• Écrire la documentation puis implanter la fonction fibonacciTableau:

// REMPLACER CETTE LIGNE PAR VOTRE RÉPONSE

int fibonacciTableau(int n) {
    // REMPLACER CETTE LIGNE ET LA SUIVANTE PAR VOTRE RÉPONSE
    throw std::runtime_error("À faire");
}

• 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 2 : Fibonacci, version trois variables

• Écrire la documentation puis implanter la fonction fibonacciVariables:

// REMPLACER CETTE LIGNE PAR VOTRE RÉPONSE

int fibonacciVariables(int n) {
    // REMPLACER CETTE LIGNE ET LA SUIVANTE PAR VOTRE RÉPONSE
    throw std::runtime_error("À faire");
}

• 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 3 : Fibonacci, version récursive

• Écrire la documentation puis implanter la fonction fibonacciRecursive:

// REMPLACER CETTE LIGNE PAR VOTRE RÉPONSE

int fibonacciRecursive(int n) {
    // REMPLACER CETTE LIGNE ET LA SUIVANTE PAR VOTRE RÉPONSE
    throw std::runtime_error("À faire");
}

• 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?

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