La suite de Fibonacci est une suite de nombres dans laquelle chaque nombre est la somme des deux précédents. La définition récursive de la suite de Fibonacci est la suivante :

• $F(0) = 0$
• $F(1) = 1$
• $F(n) = F(n-1) + F(n-2)$ pour $n \geq 2$

1. Écrire une fonction récursive fibo pour calculer le nème nombre de Fibonacci

Voici comment vous pouvez écrire une fonction récursive en Python pour calculer le nème nombre de Fibonacci :

python
Copy
def fibo(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibo(n-1) + fibo(n-2)

2. Lancer cette fonction pour de petites, puis de grandes valeurs de n

Pour de petites valeurs de $n$, la fonction fonctionne bien. Par exemple :

python
Copy
print(fibo(5))  # Affiche 5
print(fibo(10)) # Affiche 55

Pour de grandes valeurs de $n$, la fonction devient très lente. Par exemple :

python
Copy
print(fibo(30)) # Peut prendre un certain temps
print(fibo(50)) # Peut prendre beaucoup de temps

3. Que constatez-vous ?

Vous constatez que pour de grandes valeurs de $n$, la fonction devient extrêmement lente. Cela est dû au fait que la fonction récursive effectue de nombreux appels répétitifs, ce qui entraîne une complexité exponentielle.

4. Expliquer ce constat en listant tous les appels à votre fonction

Pour comprendre pourquoi la fonction devient lente, examinons les appels récursifs pour $n = 5$ :

Copy
fibo(5)
  fibo(4) + fibo(3)
    fibo(3) + fibo(2) + fibo(2) + fibo(1)
      fibo(2) + fibo(1) + fibo(1) + fibo(0) + fibo(1) + fibo(0)
        fibo(1) + fibo(0) + fibo(1) + fibo(1) + fibo(0) + fibo(1) + fibo(0)

Vous pouvez voir que fibo(2) est calculé trois fois, fibo(1) est calculé cinq fois, etc. Ce phénomène s'aggrave à mesure que $n$ augmente, car chaque appel à fibo(n) entraîne deux appels supplémentaires à fibo(n-1) et fibo(n-2), ce qui conduit à une explosion combinatoire des appels récursifs.

Pour résoudre ce problème, vous pouvez utiliser la mémoïsation (ou memoization en anglais), qui consiste à stocker les résultats des appels précédents pour éviter de les recalculer. Voici comment vous pouvez implémenter cela en Python :

python
Copy
def fibo_memo(n, memo={}):
    if n in memo:
        return memo[n]
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        memo[n] = fibo_memo(n-1, memo) + fibo_memo(n-2, memo)
        return memo[n]

Avec cette version, les appels répétitifs sont évités, ce qui rend la fonction beaucoup plus efficace pour de grandes valeurs de $n$.

D'accord, refaisons cet exercice en C. Nous allons suivre les mêmes étapes que précédemment : écrire une fonction récursive pour calculer les nombres de Fibonacci, tester cette fonction pour de petites et grandes valeurs, observer les performances, et expliquer les résultats.

1. Écrire une fonction récursive fibo pour calculer le nème nombre de Fibonacci

Voici comment vous pouvez écrire une fonction récursive en C pour calculer le nème nombre de Fibonacci :

c
Copy
#include <stdio.h>

int fibo(int n) {
    if (n == 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    } else {
        return fibo(n-1) + fibo(n-2);
    }
}

int main() {
    int n = 10; // Exemple avec n = 10
    printf("Fibonacci de %d est %d\n", n, fibo(n));
    return 0;
}

2. Lancer cette fonction pour de petites, puis de grandes valeurs de n

Pour de petites valeurs de $n$, la fonction fonctionne bien. Par exemple :

c
Copy
int main() {
    printf("Fibonacci de 5 est %d\n", fibo(5));  // Affiche 5
    printf("Fibonacci de 10 est %d\n", fibo(10)); // Affiche 55
    return 0;
}

Pour de grandes valeurs de $n$, la fonction devient très lente. Par exemple :

c
Copy
int main() {
    printf("Fibonacci de 30 est %d\n", fibo(30)); // Peut prendre un certain temps
    printf("Fibonacci de 50 est %d\n", fibo(50)); // Peut prendre beaucoup de temps
    return 0;
}

3. Que constatez-vous ?

Vous constatez que pour de grandes valeurs de $n$, la fonction devient extrêmement lente. Cela est dû au fait que la fonction récursive effectue de nombreux appels répétitifs, ce qui entraîne une complexité exponentielle.

4. Expliquer ce constat en listant tous les appels à votre fonction

Pour comprendre pourquoi la fonction devient lente, examinons les appels récursifs pour $n = 5$ :

Copy
fibo(5)
  fibo(4) + fibo(3)
    fibo(3) + fibo(2) + fibo(2) + fibo(1)
      fibo(2) + fibo(1) + fibo(1) + fibo(0) + fibo(1) + fibo(0)
        fibo(1) + fibo(0) + fibo(1) + fibo(1) + fibo(0) + fibo(1) + fibo(0)

Vous pouvez voir que fibo(2) est calculé trois fois, fibo(1) est calculé cinq fois, etc. Ce phénomène s'aggrave à mesure que $n$ augmente, car chaque appel à fibo(n) entraîne deux appels supplémentaires à fibo(n-1) et fibo(n-2), ce qui conduit à une explosion combinatoire des appels récursifs.

Pour résoudre ce problème, vous pouvez utiliser la mémoïsation (ou memoization en anglais), qui consiste à stocker les résultats des appels précédents pour éviter de les recalculer. Voici comment vous pouvez implémenter cela en C :

c
Copy
#include <stdio.h>

#define MAX 100

int memo[MAX];

int fibo_memo(int n) {
    if (n == 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    } else if (memo[n] != -1) {
        return memo[n];
    } else {
        memo[n] = fibo_memo(n-1) + fibo_memo(n-2);
        return memo[n];
    }
}

int main() {
    for (int i = 0; i < MAX; i++) {
        memo[i] = -1; // Initialiser le tableau de mémoïsation
    }
    int n = 50; // Exemple avec n = 50
    printf("Fibonacci de %d est %d\n", n, fibo_memo(n));
    return 0;
}

Avec cette version, les appels répétitifs sont évités, ce qui rend la fonction beaucoup plus efficace pour de grandes valeurs de $n$.

Si vous appelez fibo_memo(200) avec le code fourni précédemment, vous allez rencontrer plusieurs problèmes :

1. Dépassement de la taille du tableau memo : Le tableau memo est défini avec une taille maximale de 100 (#define MAX 100). Si vous appelez fibo_memo(200), vous allez accéder à des indices du tableau memo qui sont hors des limites, ce qui entraînera un comportement indéfini et probablement un crash du programme.

2. Dépassement de la capacité des entiers : Les nombres de Fibonacci croissent exponentiellement. Pour $n = 200$, le nombre de Fibonacci est extrêmement grand. Le type int en C ne peut pas stocker des valeurs aussi grandes. Vous aurez besoin d'utiliser un type de données capable de gérer de très grands entiers, comme unsigned long long ou une bibliothèque pour les grands nombres.

Pour résoudre ces problèmes, vous devez :

1. Augmenter la taille du tableau memo pour qu'il puisse stocker au moins 200 valeurs.
2. Utiliser un type de données capable de stocker de très grands entiers.

Voici comment vous pouvez modifier le code pour gérer ces problèmes :

c
Copy
#include <stdio.h>
#include <stdlib.h>

#define MAX 201

unsigned long long memo[MAX];

unsigned long long fibo_memo(int n) {
    if (n == 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    } else if (memo[n] != -1) {
        return memo[n];
    } else {
        memo[n] = fibo_memo(n-1) + fibo_memo(n-2);
        return memo[n];
    }
}

int main() {
    for (int i = 0; i < MAX; i++) {
        memo[i] = -1; // Initialiser le tableau de mémoïsation
    }
    int n = 200; // Exemple avec n = 200
    printf("Fibonacci de %d est %llu\n", n, fibo_memo(n));
    return 0;
}

Explications :

1. Type unsigned long long : Ce type est utilisé pour stocker les résultats des calculs de Fibonacci, car il peut gérer des valeurs beaucoup plus grandes que le type int.

2. Taille du tableau memo : La taille du tableau memo est augmentée à 201 pour pouvoir stocker les résultats jusqu'à fibo_memo(200).

Avec ces modifications, le programme devrait être capable de calculer fibo_memo(200) sans dépasser les limites du tableau memo et sans dépasser la capacité des entiers.

En théorie, vous pouvez choisir une taille pour MAX qui garantit que vous n'aurez jamais de débordement de tampon en fonction de la taille maximale de n que vous prévoyez de traiter. Cependant, il y a plusieurs considérations pratiques à prendre en compte :

1. Limites de la mémoire : La taille maximale de MAX dépend de la quantité de mémoire disponible sur votre système. Si vous choisissez une valeur très grande pour MAX, vous risquez de consommer trop de mémoire, ce qui peut rendre votre programme inefficace ou même provoquer des erreurs de mémoire.

2. Limites des types de données : Même avec des types de données capables de stocker de très grands entiers (comme unsigned long long), il y a des limites pratiques à la taille des nombres que vous pouvez manipuler. Par exemple, le type unsigned long long en C peut stocker des valeurs jusqu'à $2^{64} - 1$, mais les nombres de Fibonacci croissent exponentiellement et dépassent rapidement cette limite.

3. Performance : Pour de très grandes valeurs de n, le calcul des nombres de Fibonacci devient très coûteux en termes de temps de calcul, même avec la mémoïsation. Il est important de trouver un équilibre entre la taille de MAX et les performances du programme.

Solution pratique

Pour garantir qu'il n'y ait jamais de débordement de tampon, vous pouvez dynamiquement allouer de la mémoire en fonction de la valeur de n que vous souhaitez traiter. Voici comment vous pouvez le faire en C :

c
Copy
#include <stdio.h>
#include <stdlib.h>

unsigned long long *memo;

unsigned long long fibo_memo(int n) {
    if (n == 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    } else if (memo[n] != -1) {
        return memo[n];
    } else {
        memo[n] = fibo_memo(n-1) + fibo_memo(n-2);
        return memo[n];
    }
}

int main() {
    int n = 200; // Exemple avec n = 200
    memo = (unsigned long long *)malloc((n + 1) * sizeof(unsigned long long));
    if (memo == NULL) {
        fprintf(stderr, "Erreur d'allocation de mémoire\n");
        return 1;
    }
    for (int i = 0; i <= n; i++) {
        memo[i] = -1; // Initialiser le tableau de mémoïsation
    }
    printf("Fibonacci de %d est %llu\n", n, fibo_memo(n));
    free(memo); // Libérer la mémoire allouée
    return 0;
}

Explications :

1. Allocation dynamique : Le tableau memo est alloué dynamiquement en fonction de la valeur de n. Cela garantit que vous avez toujours suffisamment de mémoire pour stocker les résultats intermédiaires.

2. Gestion des erreurs : Si l'allocation de mémoire échoue, le programme affiche un message d'erreur et se termine.

3. Libération de la mémoire : Après avoir utilisé le tableau memo, la mémoire est libérée pour éviter les fuites de mémoire.

Avec cette approche, vous pouvez garantir qu'il n'y aura jamais de débordement de tampon, tout en utilisant la mémoire de manière efficace.

Si vous souhaitez que la valeur de n puisse être saisie au clavier, vous pouvez utiliser la fonction scanf en C pour lire l'entrée de l'utilisateur. Voici comment vous pouvez modifier le programme pour permettre à l'utilisateur de saisir la valeur de n :

c
Copy
#include <stdio.h>
#include <stdlib.h>

unsigned long long *memo;

unsigned long long fibo_memo(int n) {
    if (n == 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    } else if (memo[n] != -1) {
        return memo[n];
    } else {
        memo[n] = fibo_memo(n-1) + fibo_memo(n-2);
        return memo[n];
    }
}

int main() {
    int n;
    printf("Entrez la valeur de n : ");
    if (scanf("%d", &n) != 1) {
        fprintf(stderr, "Erreur de saisie\n");
        return 1;
    }

    memo = (unsigned long long *)malloc((n + 1) * sizeof(unsigned long long));
    if (memo == NULL) {
        fprintf(stderr, "Erreur d'allocation de mémoire\n");
        return 1;
    }

    for (int i = 0; i <= n; i++) {
        memo[i] = -1; // Initialiser le tableau de mémoïsation
    }

    printf("Fibonacci de %d est %llu\n", n, fibo_memo(n));

    free(memo); // Libérer la mémoire allouée
    return 0;
}

Explications :

1. Lecture de l'entrée utilisateur : La fonction scanf est utilisée pour lire la valeur de n saisie par l'utilisateur. Le format %d est utilisé pour lire un entier.

2. Vérification de la saisie : La fonction scanf retourne le nombre d'éléments lus avec succès. Si scanf ne retourne pas 1, cela signifie que la saisie n'a pas été correcte, et le programme affiche un message d'erreur et se termine.

3. Allocation dynamique : Le tableau memo est alloué dynamiquement en fonction de la valeur de n saisie par l'utilisateur. Cela garantit que vous avez toujours suffisamment de mémoire pour stocker les résultats intermédiaires.

4. Gestion des erreurs : Si l'allocation de mémoire échoue, le programme affiche un message d'erreur et se termine.

5. Libération de la mémoire : Après avoir utilisé le tableau memo, la mémoire est libérée pour éviter les fuites de mémoire.

Avec ces modifications, le programme permet à l'utilisateur de saisir la valeur de n au clavier, tout en garantissant une gestion correcte de la mémoire et des erreurs.

Oui, il existe d'autres méthodes pour résoudre le problème de combinatoire observé lors du calcul de la suite de Fibonacci, sans utiliser la mémoïsation. Voici quelques approches alternatives :

1. Approche itérative

L'approche itérative est une méthode efficace pour calculer les nombres de Fibonacci sans utiliser de mémoïsation. Elle utilise une boucle pour calculer les valeurs de manière séquentielle, ce qui évite les appels récursifs répétitifs.

c
Copy
#include <stdio.h>

unsigned long long fibo_iterative(int n) {
    if (n == 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    }

    unsigned long long a = 0;
    unsigned long long b = 1;
    unsigned long long c;

    for (int i = 2; i <= n; i++) {
        c = a + b;
        a = b;
        b = c;
    }

    return b;
}

int main() {
    int n;
    printf("Entrez la valeur de n : ");
    if (scanf("%d", &n) != 1) {
        fprintf(stderr, "Erreur de saisie\n");
        return 1;
    }

    printf("Fibonacci de %d est %llu\n", n, fibo_iterative(n));
    return 0;
}

2. Approche matricielle

La suite de Fibonacci peut également être calculée en utilisant des matrices. Cette méthode est basée sur la propriété suivante :

Voici comment vous pouvez implémenter cette approche en C :

c
Copy
#include <stdio.h>

void multiply(unsigned long long F[2][2], unsigned long long M[2][2]) {
    unsigned long long x = F[0][0] * M[0][0] + F[0][1] * M[1][0];
    unsigned long long y = F[0][0] * M[0][1] + F[0][1] * M[1][1];
    unsigned long long z = F[1][0] * M[0][0] + F[1][1] * M[1][0];
    unsigned long long w = F[1][0] * M[0][1] + F[1][1] * M[1][1];

    F[0][0] = x;
    F[0][1] = y;
    F[1][0] = z;
    F[1][1] = w;
}

void power(unsigned long long F[2][2], int n) {
    if (n == 0 || n == 1) {
        return;
    }
    unsigned long long M[2][2] = {{1, 1}, {1, 0}};

    power(F, n / 2);
    multiply(F, F);

    if (n % 2 != 0) {
        multiply(F, M);
    }
}

unsigned long long fibo_matrix(int n) {
    unsigned long long F[2][2] = {{1, 1}, {1, 0}};
    if (n == 0) {
        return 0;
    }
    power(F, n - 1);

    return F[0][0];
}

int main() {
    int n;
    printf("Entrez la valeur de n : ");
    if (scanf("%d", &n) != 1) {
        fprintf(stderr, "Erreur de saisie\n");
        return 1;
    }

    printf("Fibonacci de %d est %llu\n", n, fibo_matrix(n));
    return 0;
}

3. Approche utilisant la formule de Binet

La formule de Binet est une formule explicite pour calculer les nombres de Fibonacci. Elle est basée sur le nombre d'or $\phi$ :

où $\phi = \frac{1 + \sqrt{5}}{2}$.

Cependant, cette formule peut entraîner des erreurs d'arrondi en raison des calculs en virgule flottante. Elle est donc moins couramment utilisée pour des calculs exacts.

Conclusion

L'approche itérative est généralement la plus simple et la plus efficace pour calculer les nombres de Fibonacci sans utiliser de mémoïsation. L'approche matricielle est également très efficace et peut être utilisée pour des calculs plus avancés. La formule de Binet est intéressante d'un point de vue théorique, mais elle est moins pratique pour des calculs exacts en raison des erreurs d'arrondi.