Problem Solving
Travaux dirigés n°2
Complexité & Récursivité
Suite de Fibonacci
La suite de Fibonacci est définie comme suit :
Fn=0 si n=0
Fn=1 si n=1 ou -1
Fn=F(n-1)+F(n-2) sinon
1. Ecrivez un algorithme récursif calculant Fn
fonction Fibonacci(n: entier): entier
si n = 0:
renvoyer 0
sinon si n = 1:
renvoyer 1
sinon:
renvoyer Fibonacci(n - 1) + Fibonacci(n - 2)
Il est important de noter que ce code récursif peut être assez lent pour des valeurs de n élevées,
car il recalcule plusieurs fois les mêmes valeurs de Fibonacci. Il existe des méthodes plus rapides
pour calculer la suite de Fibonacci, comme l'utilisation de la formule de Binet ou l'utilisation de
la récursion bottom-up avec la mémorisation de valeurs intermédiaires.
2. Montrez que la complexité (en nombre d'additions) de cet
algorithme est en .
La complexité du code récursif pour calculer la valeur de Fn dans la suite de Fibonacci
n'est pas O((φ)^n), où φ est le nombre d'or (1,6180339887...).
La complexité de ce code est en réalité de O(2^n), ce qui signifie que pour chaque
augmentation de 1 de la taille de l'input (c'est-à-dire pour chaque augmentation de 1
de n), le temps et l'espace nécessaires pour exécuter l'algorithme vont augmenter de
manière exponentielle.
Le nombre d'or (φ) est un nombre irrationnel qui apparaît dans diverses situations en
mathématiques et en physique, mais il n'a aucun lien avec la complexité de ce code
récursif pour calculer la suite de Fibonacci.
Il est important de noter que la complexité d'un algorithme décrit la quantité de temps
et d'espace (mémoire) nécessaire pour exécuter l'algorithme, généralement en fonction
de la taille de l'input. Il est donc important de connaître la complexité d'un algorithme
pour savoir à quoi s'attendre en termes de performance lors de son utilisation.
3. Ecrire un algorithme récursif qui calcule, pour n > 0, le
couple (Fn , Fn-1).
fonction Fibonacci(n: entier): couple[entier, entier]
si n = 0:
renvoyer (0, 0)
sinon si n = 1:
renvoyer (1, 0)
sinon:
couple = Fibonacci(n - 1)
renvoyer (couple[0] + couple[1], couple[0])
4. Quelle est la complexité (en nombre d'additions) de cet
algorithme ?
La complexité de ce code récursif pour calculer le couple (Fn , Fn-1) dans la suite de Fibonacci
est de O(n).
5. Ecrire un algorithme itératif calculant Fn. Quelle est sa
complexité (meilleur/pire/moyenne) ?
fonction Fibonacci(n: entier): entier
si n = 0:
renvoyer 0
sinon si n = 1:
renvoyer 1
sinon:
f0 = 0
f1 = 1
pour i de 2 à n:
fi = f0 + f1
f0 = f1
f1 = fi
renvoyer fi
Opérations ensemblistes
Dans cette partie on considère des ensembles représentés par
des tableaux, certains ensembles seront triés et d'autres pas.
Toutes les solutions proposées doivent être récursives.
1. Nous voulons un algorithme Appartenance(A, x) qui
recherche si un élément x appartient à l'ensemble A. Si x
appartient effectivement à A, l'algorithme renverra true, et
false sinon.
(a) Cas des ensembles non triés :
i. Écrivez un tel algorithme.
#include <stdbool.h>
bool Appartenance(int A[], int taille, int x) {
// Cas de base : si le tableau est vide, x n'appartient pas à A
if (taille == 0) return false;
// Si x est égal à l'élément courant du tableau, il appartient à A
if (A[0] == x) return true;
// Sinon, on vérifie l'appartenance de x dans le sous-tableau A[1..taille-1]
return Appartenance(A+1, taille-1, x);
}
Cette solution fonctionne en parcourant le tableau de manière récursive, en vérifiant à
chaque étape si l'élément courant est égal à x. Si c'est le cas, la fonction renvoie true.
Sinon, elle appelle récursivement la fonction sur le sous-tableau A[1..taille-1] et renvoie
le résultat de cet appel.
Pour utiliser cette fonction, vous pouvez simplement l'appeler en lui passant un tableau
A, sa taille et l'élément x que vous souhaitez rechercher :
int A[] = {1, 3, 5, 7, 9};
int x = 5;
if (Appartenance(A, 5, x)) {
printf("%d appartient à l'ensemble A\n", x);
} else {
printf("%d n'appartient pas à l'ensemble A\n", x);
}
Cette fonction ne fonctionnera correctement que si l'ensemble A est non trié. Si vous avez
besoin de rechercher un élément dans un tableau trié, vous devrez utiliser une approche
différente, comme la recherche binaire.
ii. Quelle est sa complexité en nombre de comparaisons ? (
b) Cas des ensembles triés (dans l'ordre croissant) :
i. Ecrivez un tel algorithme.
Pour rechercher un élément x dans un tableau trié A de manière récursive, vous pouvez utiliser
l'algorithme de recherche binaire. Voici comment cela pourrait être mis en œuvre en C :
#include <stdbool.h>
bool RechercheBinaire(int A[], int debut, int fin, int x) {
// Cas de base : si le sous-tableau est vide, x n'appartient pas à
A
if (debut > fin) return false;
// On calcule l'indice du milieu du tableau
int milieu = (debut + fin) / 2;
// Si x est égal à l'élément du milieu, il appartient à A
if (A[milieu] == x) return true;
// Si x est inférieur à l'élément du milieu, on recherche x dans
le sous-tableau gauche A[debut..milieu-1]
if (x < A[milieu]) return RechercheBinaire(A, debut, milieu-1,
x);
// Sinon, x est supérieur à l'élément du milieu, on recherche x
dans le sous-tableau droit A[milieu+1..fin]
return RechercheBinaire(A, milieu+1, fin, x);
}
Pour utiliser cette fonction, vous pouvez l'appeler en lui passant un tableau A trié, ses indices de
début et de fin, et l'élément x que vous souhaitez rechercher :
int A[] = {1, 3, 5, 7, 9};
int x = 5;
if (RechercheBinaire(A, 0, 4, x)) {
printf("%d appartient à l'ensemble A\n", x);
} else {
printf("%d n'appartient pas à l'ensemble A\n", x);
}
Cette fonction fonctionnera efficacement même pour des tableaux de grande taille, car elle ne
parcourt qu'une partie du tableau à chaque appel récursif. Elle est donc en temps logarithmique
en la taille du tableau.
ii. Quelle est sa complexité en nombre de comparaisons ?
La complexité de l'algorithme de recherche binaire est en temps logarithmique en la
taille du tableau, c'est-à-dire qu'elle s'exécute en un temps proportionnel à la
logarithme de la taille du tableau. Plus précisément, la complexité est en O(log n), où n
est la taille du tableau.
La raison pour laquelle l'algorithme a une complexité logarithmique est qu'à chaque
étape, il divise le sous-tableau de recherche en deux parties égales. Ainsi, à chaque
appel récursif, la taille du sous-tableau de recherche est divisée par deux, ce qui réduit
considérablement le nombre d'opérations nécessaires pour trouver l'élément x.
En comparaison, la complexité de l'algorithme d'appartenance récursif que j'ai proposé
précédemment est en temps linéaire en la taille du tableau. Cela signifie qu'elle
s'exécute en un temps proportionnel à la taille du tableau. Sa complexité est en O(n), où
n est la taille du tableau. Cette complexité est moins bonne que celle de la recherche
binaire, car elle nécessite de parcourir tous les éléments du tableau pour déterminer si x
appartient à A.
iii. Utilisez une recherche dichotomique pour améliorer votre
algorithme.
#include <stdbool.h>
bool AppartenanceDichotomique(int A[], int debut, int fin, int x) {
// Cas de base : si le sous-tableau est vide, x n'appartient pas à A
if (debut > fin) return false;
// On calcule l'indice du milieu du tableau
int milieu = (debut + fin) / 2;
// Si x est égal à l'élément du milieu, il appartient à A
if (A[milieu] == x) return true;
// Si x est inférieur à l'élément du milieu, on recherche x dans le sous-tableau
gauche A[debut..milieu-1]
if (x < A[milieu]) return AppartenanceDichotomique(A, debut, milieu-1, x);
// Sinon, x est supérieur à l'élément du milieu, on recherche x dans le sous-
tableau droit A[milieu+1..fin]
return AppartenanceDichotomique(A, milieu+1, fin, x);
}
iv. Quelle est la complexité de votre nouvel algorithme ?
La complexité de l'algorithme d'appartenance récursif utilisant une recherche dichotomique est
en temps logarithmique en la taille du tableau, c'est-à-dire qu'elle s'exécute en un temps
proportionnel à la logarithme de la taille du tableau. Plus précisément, sa complexité est en
O(log n), où n est la taille du tableau.
2. Nous voulons maintenant un algorithme Union(A, B) qui nous
renvoie l'union des deux ensembles qui lui sont passés en
argument.
(a) Cas des ensembles non triés :
i. Écrivez un tel algorithme.
#include <stdio.h>
const int MAX_TAILLE = 100;
void Union(int A[], int tailleA, int B[], int tailleB, int C[], int *tailleC) {
// Cas de base : si l'un des tableaux est vide, on ajoute simplement les éléments
de l'autre tableau à C
if (tailleA == 0) {
for (int i = 0; i < tailleB; i++) {
C[(*tailleC)++] = B[i];
}
return;
}
if (tailleB == 0) {
for (int i = 0; i < tailleA; i++) {
C[(*tailleC)++] = A[i];
}
return;
}
// Si les deux tableaux sont non vides, on ajoute le premier élément de l'un
d'entre eux à C
if (A[0] < B[0]) {
C[(*tailleC)++] = A[0];
} else {
C[(*tailleC)++] = B[0];
}
// On continue l'union en comparant les deux sous-tableaux restants
Union(A+1, tailleA-1, B+1, tailleB-1, C, tailleC);
}
ii. Quelle est sa complexité ?
(b) Cas des ensembles triés (dans l'ordre croissant) :
Si vous souhaitez une solution plus efficace pour l'union de deux ensembles non triés, vous
pouvez utiliser un algorithme de tri en place pour trier les deux tableaux avant de les fusionner.
Cela vous permettra d'obtenir une complexité en O(n log n + m log m) pour le tri, suivie d'une
complexité en O(n + m) pour la fusion des tableaux triés. Cette approche est généralement plus
rapide que l'algorithme récursif que j'ai proposé si les tailles des tableaux sont relativement
grandes.
i. Écrivez un tel algorithme.
#include <stdio.h>
const int MAX_TAILLE = 100;
void Union(int A[], int tailleA, int B[], int tailleB, int C[], int *tailleC) {
// Cas de base : si l'un des tableaux est vide, on ajoute simplement les éléments
de l'autre tableau à C
if (tailleA == 0) {
for (int i = 0; i < tailleB; i++) {
C[(*tailleC)++] = B[i];
}
return;
}
if (tailleB == 0) {
for (int i = 0; i < tailleA; i++) {
C[(*tailleC)++] = A[i];
}
return;
}
// Si les deux tableaux sont non vides, on compare leurs premiers éléments
if (A[0] < B[0]) {
// Si l'élément de A est plus petit, on l'ajoute à C et on continue l'union avec le
sous-tableau A[1..tailleA-1] et B
C[(*tailleC)++] = A[0];
Union(A+1, tailleA-1, B, tailleB, C, tailleC);
} else if (A[0] > B[0]) {
// Si l'élément de B est plus petit, on l'ajoute à C et on continue l'union avec A
et le sous-tableau B[1..tailleB-1]
C[(*tailleC)++] = B[0];
Union(A, tailleA, B+1, tailleB-1, C, tailleC);
} else {
// Si les deux éléments sont égaux, on ajoute l'un d'entre eux à C et on continue
l'union avec le sous-tableau A[1..tailleA-1] et B[1..tailleB-1]
C[(*tailleC)++] = A[0];
Union(A+1, tailleA-1, B+1, tailleB-1, C, tailleC);
}
}
int main() {
int A[] = {1, 3, 5, 7};
int tailleA = sizeof(A) / sizeof(int);
int B[] = {2, 3, 4, 5};
int tailleB = sizeof(B) / sizeof(int);
int C[MAX_TAILLE];
int tailleC = 0;
Union(A, tailleA, B, tailleB, C, &tailleC);
printf("L'union des ensembles A et B est : ");
for (int i = 0; i < tailleC; i++) {
printf("%d ", C[i]);
}
printf("\n");
return 0;
}
ii. Quelle est sa complexité ?
Pour l'union de deux ensembles non triés, la complexité de l'algorithme récursif que j'ai
proposé reste en O(n + m), où n et m sont les tailles des tableaux A et B respectivement.
Cette complexité est due au fait que l'algorithme parcourt tous les éléments des deux
tableaux pour construire l'union.
Il est important de noter que cet algorithme ne trie pas les éléments de l'union. Si vous
souhaitez obtenir un tableau trié en sortie, vous devrez trier le tableau C une fois l'union
terminée. La complexité de tri d'un tableau dépend de l'algorithme de tri utilisé, mais en
général, elle est en O(n log n) pour des algorithmes de tri efficaces comme le tri rapide
ou le tri par fusion.
3. Nous voulons maintenant un algorithme Intersection(A, B)
qui nous renvoie l'intersection des deux ensembles qui lui sont
passés en argument.
(a) Cas des ensembles non triés :
i. Écrivez un tel algorithme.
#include <stdio.h>
const int MAX_TAILLE = 100;
void Intersection(int A[], int tailleA, int B[], int tailleB, int C[], int *tailleC) {
// Cas de base : si l'un des tableaux est vide, l'intersection est vide
if (tailleA == 0 || tailleB == 0) return;
// Si les deux tableaux sont non vides, on compare leurs premiers éléments
if (A[0] == B[0]) {
// Si les deux éléments sont égaux, on ajoute l'un d'entre eux à C et on continue
l'intersection avec le sous-tableau A[1..tailleA-1] et B[1..tailleB-1]
C[(*tailleC)++] = A[0];
Intersection(A+1, tailleA-1, B+1, tailleB-1, C, tailleC);
} else if (A[0] < B[0]) {
// Si l'élément de A est inférieur à celui de B, on continue l'intersection avec le
sous-tableau A[1..tailleA-1] et B
Intersection(A+1, tailleA-1, B, tailleB, C, tailleC);
} else {
// Si l'élément de B est inférieur à celui de A, on continue l'intersection avec A
et le sous-tableau B[1..tailleB-1]
Intersection(A, tailleA, B+1, tailleB-1, C, tailleC);
}
}
int main() {
int A[] = {3, 5, 2, 7, 1};
int tailleA = sizeof(A) / sizeof(int);
int B[] = {4, 5, 2, 3};
int tailleB = sizeof(B) / sizeof(int);
int C[MAX_TAILLE];
int tailleC = 0;
Intersection(A, tailleA, B, tailleB, C, &tailleC);
ii. Quelle est sa complexité ?
La complexité de l'algorithme d'intersection récursif que j'ai proposé est en temps
linéaire en la taille des deux tableaux A et B, c'est-à-dire qu'elle s'exécute en un temps
proportionnel à la somme des tailles des deux tableaux. Plus précisément, sa complexité
est en O(n + m), où n et m sont les tailles des tableaux A et B respectivement.
Cette complexité est due au fait que l'algorithme parcourt tous les éléments des deux
tableaux pour construire l'intersection. À chaque étape, il compare le premier élément
de chaque tableau et ajoute celui qui est présent dans les deux tableaux à l'intersection,
puis il continue l'intersection avec les sous-tableaux restants. Comme il y a n + m
éléments au total dans les deux tableaux, l'algorithme effectue au maximum n + m
comparaisons et ajouts à l'intersection.
(b) Cas des ensembles triés (dans l'ordre croissant) :
i. Écrivez un tel algorithme.
#include <stdio.h>
const int MAX_TAILLE = 100;
void Intersection(int A[], int tailla, int B[], int tailleB, int C[], int *tailleC) {
// Cas de base : si l'un des tableaux est vide, l'intersection est vide
if (tailleA == 0 || tailleB == 0) return;
// Si les deux tableaux sont non vides, on compare leurs premiers éléments
if (A[0] == B[0]) {
// Si les deux éléments sont égaux, on ajoute l'un d'entre eux à C et on continue
l'intersection avec le sous-tableau A[1..tailleA-1] et B[1..tailleB-1]
C[(*tailleC)++] = A[0];
Intersection(A+1, tailleA-1, B+1, tailleB-1, C, tailleC);
} else if (A[0] < B[0]) {
// Si l'élément de A est inférieur à celui de B, on continue l'intersection avec le
sous-tableau A[1..tailleA-1] et B
Intersection(A+1, tailleA-1, B, tailleB, C, tailleC);
} else {
// Si l'élément de B est inférieur à celui de A, on continue l'intersection avec A
et le sous-tableau B[1..tailleB-1]
Intersection(A, tailleA, B+1, tailleB-1, C, tailleC);
}
}
int main() {
int A[] = {1, 3, 5, 7};
int tailleA = sizeof(A) / sizeof(int);
int B[] = {2, 3, 4, 5};
int tailleB = sizeof(B) / sizeof(int);
int C[MAX_TAILLE];
int tailleC = 0;
Intersection(A, tailleA, B, tailleB, C, &tailleC);
ii. Quelle est sa complexité ?
Cette complexité est due au fait que l'algorithme parcourt tous les éléments des deux tableaux
pour construire l'intersection. À chaque étape, il compare le premier élément de chaque tableau
et ajoute celui qui est présent dans les deux tableaux à l'intersection, puis il continue
l'intersection avec les sous-tableaux restants. Comme il y a n + m éléments au total dans les
deux tableaux, l'algorithme effectue au maximum n + m comparaisons et ajouts à l'intersection
4. Nous voulons maintenant un algorithme Différence(A, B) qui
nous renvoie la différence des deux ensembles qui lui sont
passées en argument (La différence de A et de B, notée A \ B
est l'ensemble des éléments de A n'appartenant pas à B).
(a) Cas des ensembles non triés :
i. Écrivez un tel algorithme.
#include <stdio.h>
const int MAX_TAILLE = 100;
void Difference(int A[], int tailleA, int B[], int tailleB, int C[], int *tailleC) {
// Cas de base : si l'un des tableaux est vide, la différence est le contenu de
l'autre tableau
if (tailleA == 0) return;
if (tailleB == 0) {
for (int i = 0; i < tailleA; i++) {
C[(*tailleC)++] = A[i];
}
return;
}
// Si les deux tableaux sont non vides, on compare leurs premiers éléments
if (A[0] == B[0]) {
// Si les deux éléments sont égaux, on continue la différence avec le sous-
tableau A[1..tailleA-1] et B[1..tailleB-1]
Difference(A+1, tailleA-1, B+1, tailleB-1, C, tailleC);
} else if (A[0] < B[0]) {
// Si l'élément de A est inférieur à celui de B, on ajoute l'élément de A à C et on
continue la différence avec le sous-tableau A[1..tailleA-1] et B
C[(*tailleC)++] = A[0];
Difference(A+1, tailleA-1, B, tailleB, C, tailleC);
} else {
// Si l'élément de B est inférieur à celui de A, on continue la différence avec A et
le sous-tableau B[1..tailleB-1]
Difference(A, tailleA, B+1, tailleB-1, C, tailleC);
}
}
int main() {
int A[] = {3, 5, 2, 7, 1};
int tailleA = sizeof(A) / sizeof(int);
int B[] = {4, 5, 2, 3};
int tailleB = sizeof(B) / sizeof(int);
int C[MAX_TAILLE];
int tailleC = 0;
Difference(A, tailleA, B, tailleB, C, &tailleC);
printf("La différence de A et de B est : ");
for (int i = 0; i < tailleC; i++) {
printf("%d ", C[i]);
ii. Quelle est sa complexité ?
(b) Cas des ensembles triés (dans l'ordre croissant) :
i. Écrivez un tel algorithme.
#include <stdio.h>
const int MAX_TAILLE = 100;
void Difference(int A[], int tailleA, int B[], int tailleB, int C[], int *tailleC) {
// Cas de base : si l'un des tableaux est vide, la différence est le contenu de
l'autre tableau
if (tailleA == 0) return;
if (tailleB == 0) {
for (int i = 0; i < tailleA; i++) {
C[(*tailleC)++] = A[i];
}
return;
}
// Si les deux tableaux sont non vides, on compare leurs premiers éléments
if (A[0] == B[0]) {
// Si les deux éléments sont égaux, on continue la différence avec le sous-
tableau A[1..tailleA-1] et B[1..tailleB-1]
Difference(A+1, tailleA-1, B+1, tailleB-1, C, tailleC);
} else if (A[0] < B[0]) {
// Si l'élément de A est inférieur à celui de B, on ajoute l'élément de A
ii. Quelle est sa complexité ?
