Exercice 1 :
La suite de Fibonacci est définie comme suit :
𝐹0 = 0,
𝐹1 = 1
𝐹𝑛 = 𝐹𝑛−1 + 𝐹𝑛−2, ∀ 𝑛 ≥ 2
int fibonacci(int n) {
if (n <= 1)
return n;
else
return fibonacci(n-1) + fibonacci(n-2);
Donner sa complexité temporelle :
La complexité temporelle de la fonction fibonacci peut être calculée en examinant le nombre
d'appels récursifs effectués pour calculer les n premiers termes de la suite.
Lorsque la fonction fibonacci est appelée avec une valeur de n supérieure à 1, elle effectue deux
appels récursifs à elle-même pour calculer les termes F(n-1) et F(n-2). Chacun de ces appels récursifs
génère deux appels récursifs supplémentaires, pour un total de quatre appels récursifs. Ces quatre
appels récursifs génèrent huit appels récursifs supplémentaires, et ainsi de suite, jusqu'à ce que les
appels récursifs atteignent les cas de base n=0 et n=1.
Par conséquent, le nombre total d'appels récursifs nécessaires pour calculer la suite de Fibonacci
jusqu'à F(n) est exponentiel en n. Plus précisément, il est de l'ordre de 2^n. Cela signifie que la
complexité temporelle de la fonction fibonacci est exponentielle, c'est-à-dire O(2^n).
Il convient de noter que cette complexité est très élevée et peut rendre la fonction très lente pour
des valeurs relativement petites de n. C'est pourquoi, pour calculer la suite de Fibonacci pour des
valeurs plus grandes de n, il est préférable d'utiliser une méthode itérative ou une méthode qui
utilise la formule explicite pour F(n).
Exemple :
Pour calculer fibonacci(3) à l'aide d'un arbre d'appels récursifs, nous pouvons représenter chaque
appel de fonction par un nœud dans un arbre, avec les appels récursifs correspondants représentés
par les branches sortantes de chaque nœud. Les nœuds terminaux (les feuilles de l'arbre)
représentent les cas de base fibonacci(0) et fibonacci(1).
L'arbre d'appels récursifs pour fibonacci(3) serait le suivant :
fibonacci(3)
/ \
fibonacci(2) fibonacci(1)
/ \ |
fibonacci(1) fibonacci(0) return 1
| |
return 1 return 0
Le calcul de fibonacci(3) nécessite deux appels récursifs à fibonacci(2) et fibonacci(1), qui eux-mêmes
nécessitent chacun un appel récursif. Les appels récursifs à fibonacci(1) et fibonacci(0) sont des cas
de base, qui renvoient directement les valeurs 1 et 0. Les résultats des appels récursifs à fibonacci(2)
et fibonacci(1) sont ensuite additionnés pour donner le résultat final de fibonacci(3), qui est 2.
Ainsi, fibonacci(3) est évalué en effectuant 5 appels à la fonction fibonacci.
Exercice 2 :
void deplacerDisque(int disque, char source, char destination, char auxiliaire) {
cout << "Deplacement du " << disque << " de " << source << " a " << destination
<< std::endl;
void Hanoi(int n, char source, char destination, char auxiliaire) {
if (n == 1) {
deplacerDisque(n, source, destination, auxiliaire);
else {
Hanoi(n-1, source, auxiliaire, destination);
deplacerDisque(n, source, destination, auxiliaire);
Hanoi(n-1, auxiliaire, destination, source);
Donner sa complexité temporelle :
La fonction Hanoi implémente l'algorithme de la tour de Hanoi pour résoudre le problème de
déplacement de n disques d'un poteau source à un poteau destination, en utilisant un poteau
auxiliaire. La fonction utilise une approche récursive pour résoudre le problème.
La complexité temporelle de l'algorithme de la tour de Hanoi est de O(2^n), car chaque appel récursif
résout le problème pour n-1 disques, et donc la profondeur de l'appel récursif est de n. Chaque appel
récursif effectue également un déplacement de disque, ce qui coûte O(1). Le nombre total de
déplacements de disque est donc de 2^n - 1, qui est exponentiel en n.
Ainsi, la complexité temporelle de la fonction Hanoi est de O(2^n). Cela signifie que le temps
d'exécution de l'algorithme augmente de manière exponentielle avec la taille de l'entrée. Pour des
valeurs de n relativement petites, l'algorithme peut être exécuté en un temps raisonnable, mais pour
des valeurs plus grandes, l'algorithme peut prendre beaucoup de temps pour s'exécuter.
Poursuivons avec l'exemple Hanoi(4,'a','b','c'). Le nombre de déplacements requis pour résoudre ce
problème est de 2⁴ - 1 = 15. Voici la séquence de déplacements pour résoudre ce problème:
Déplacer le disque 1 de A à B
Déplacer le disque 2 de A à C
Déplacer le disque 1 de B à C
Déplacer le disque 3 de A à B
Déplacer le disque 1 de C à A
Déplacer le disque 2 de C à B
Déplacer le disque 1 de A à B
Déplacer le disque 4 de A à C
Déplacer le disque 1 de B à C
Déplacer le disque 2 de B à A
Déplacer le disque 1 de C à A
Déplacer le disque 3 de B à C
Déplacer le disque 1 de A à B
Déplacer le disque 2 de A à C
Déplacer le disque 1 de B à C
La complexité temporelle de l'algorithme de résolution de la tour de Hanoi est exponentielle en
fonction du nombre de disques. Plus précisément, sa complexité est de O(2ⁿ), où n est le nombre de
disques. Cela signifie que le temps d'exécution de l'algorithme double à chaque augmentation de 1
du nombre de disques. Par conséquent, l'algorithme est très inefficace pour résoudre des instances
de problèmes avec un grand nombre de disques.
Lien pour expliquer Tours Hanois :
[Link]
[Link]
Universit%C3%A9ClermontAuvergne