Exercice 1 : Suite de Fibonacci

Énoncé :

La suite de Fibonacci est définie de la manière suivante :

• F(0) = 0
• F(1) = 1
• F(n) = F(n - 1) + F(n - 2) pour n ≥ 2

Questions :

1. Écris une fonction récursive qui calcule F(n).
2. Donne deux appels récursifs redondants pour F(5).
3. Propose une version avec mémoïsation pour éviter les calculs redondants.

Exercice 2 : Somme des Chemins dans une Grille

Énoncé :

Tu es à l’origine d’une grille de n × n. Tu peux te déplacer uniquement vers le bas ou vers la droite. Combien de chemins différents permettent d’atteindre la case en bas à droite ?

Définition de la fonction :

• S(0, 0) = 1
• S(i, j) = S(i - 1, j) + S(i, j - 1) pour i, j ≥ 1

Questions :

1. Écris une fonction récursive qui calcule le nombre de chemins S(i, j).
2. Propose une solution avec un tableau pour éviter les calculs redondants.
3. Quelle est la complexité temporelle et spatiale de ton algorithme avec tableau ?

Exercice 3 : Multiplication Matricielle avec Récurrence

Énoncé :

On veut calculer la valeur de C(i, j) dans le produit de deux matrices A et B. La formule récurrente est donnée par :

Questions :

1. Écris un algorithme récursif pour calculer C(i, j).
2. Décris deux calculs redondants que cet algorithme récursif effectue.
3. Propose une solution avec programmation dynamique pour éviter ces redondances.
4. Quelle est la complexité en temps de ton algorithme optimisé ?

Énoncé

Le coefficient binomial C(n, k) donne le nombre de façons de choisir k éléments parmi n.

Il est défini par :

• C(n, k) = 1 si k = 0 ou k = n
• C(n, k) = C(n - 1, k - 1) + C(n - 1, k) sinon

Questions

• 1. Écris un algorithme récursif qui calcule le coefficient binomial C(n, k).
• 2. Identifie un exemple d’appel récursif redondant.
• 3. Implémente une version optimisée avec programmation dynamique (DP).
• 4. Calcule la complexité temporelle et spatiale de chaque version.
• 5. Propose une optimisation de l’espace avec un tableau unidimensionnel.

Exercice 5 : Nombre de Façons de Faire la Monnaie

Énoncé : Combien de façons différentes existe-t-il pour atteindre une somme donnée avec une liste de pièces ?

• 1. Implémente une fonction récursive qui calcule le nombre de façons.
• 2. Propose une version optimisée avec mémoïsation.
• 3. Calcule la complexité temporelle et spatiale.

Exercice 6 : Longest Common Subsequence (LCS)

Énoncé : Calculer la plus longue sous-séquence commune entre deux chaînes.

• 1. Implémente une fonction récursive pour calculer LCS.
• 2. Identifie les appels redondants et propose une version avec tableau.
• 3. Calcule la complexité temporelle et spatiale.

Exercice 7 : Problème du Sac à Dos

Énoncé : Trouver la valeur maximale transportable avec un sac à dos de capacité limitée.

• 1. Implémente une version récursive du problème.
• 2. Optimise avec un tableau pour éviter les recalculs.
• 3. Calcule la complexité temporelle et spatiale.