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:

/// BEGIN SOLUTION
/** Suite de Fibonacci (variante utilisant un tableau)
 *  @param n un entier strictement positif
 *  @return le n-ième terme de la suite de Fibonacci
 **/
/// END SOLUTION

int fibonacciTableau(int n) {
    /// BEGIN SOLUTION
    if(n == 1 or n == 2) {
        return 1; 
    } else {
        vector<int> u(n);
        u[0] = 1;
        u[1] = 1;
        for (int i = 2; i < n; i++) {
            u[i] = u[i-1] + u[i-2];
        }
        return u[n-1]; }
    
    /// END SOLUTION
}

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

/// BEGIN SOLUTION
/** Suite de Fibonacci (variante utilisant trois variables)
 *  @param n un entier strictement positif
 *  @return le n-ième terme de la suite de Fibonacci
 **/
/// END SOLUTION

int fibonacciVariables(int n) {
    /// BEGIN SOLUTION
    int u1 = 1;
    int u2 = 1;
    int tmp = 0;
    if(n == 1 or n == 2) {
        return 1;
    } else {
        for (int i = 3; i <= n; i++) {
            tmp = u2;
            u2 = u1 + u2;
            u1 = tmp;
        }
        return u2;
    }
    /// END SOLUTION
}

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

/// BEGIN SOLUTION
/** Suite de Fibonacci (variante récursive)
 *  @param n un entier strictement positif
 *  @return le n-ième terme de la suite de Fibonacci
 **/
/// END SOLUTION

int fibonacciRecursive(int n) {
    /// BEGIN SOLUTION
    if(n == 1 or n == 2) {
        return 1;
    } else {
        return fibonacciRecursive(n-2) + fibonacciRecursive(n-1);
    }
    /// END SOLUTION
}

• 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? BEGIN SOLUTION La fonction met beaucoup de temps à s’exécuter, car la version récursive recalcule chaque f(n) beaucoup de fois. Plus précisément, si c(n) est le nombre d’appels à f pour calculer f(n), alors c(n)=1+c(n-1)+c(n-2), ce qui donne un nombre exponentiel d’appels récursifs. END SOLUTION

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