8.2 — Programmation dynamique - Exercices
Exercice 1 — Escalier ✏️
Un enfant monte un escalier de \(n\) marches. À chaque pas, il peut monter 1 ou 2 marches. On cherche le nombre de façons différentes d’atteindre la marche \(n\).
Par exemple, pour 3 marches : (1+1+1), (1+2), (2+1) → 3 façons.
1. Trouver à la main le nombre de façons pour \(n = 0, 1, 2, 3, 4, 5\). Que remarque-t-on ?
2. Expliquer, en s’appuyant sur les cas \(n=4\) et \(n=5\), comment le nombre de façons d’arriver à la marche \(n\) se déduit des résultats pour les marches précédentes. Ne pas écrire de formule : expliquer avec des mots.
3. Pourquoi une approche récursive naïve serait-elle inefficace ? Quel phénomène apparaît-il (nommer ce phénomène) ?
4. Remplir le tableau suivant en utilisant l’approche ascendante :
| \(n\) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| façons | 1 | 3 |
Exercice 2 — Le livreur de colis ✏️
Un livreur doit parcourir une rue avec \(n\) maisons numérotées de 1 à \(n\). Chaque maison \(i\) a un nombre de colis \(c_i\) à livrer. La contrainte est la suivante : il ne peut pas livrer deux maisons consécutives (il doit laisser une maison entre chaque livraison pour pouvoir garer son camion). Il cherche à maximiser le nombre total de colis livrés.
Exemple avec \(n = 6\) maisons et les colis : [2, 7, 9, 3, 1, 5].
1. L’algorithme glouton consiste à toujours choisir la maison avec le plus de colis parmi les maisons disponibles. Appliquer cette stratégie sur l’exemple. Obtient-on le maximum ?
2. On note \(M(i)\) le nombre maximal de colis qu’on peut livrer en ne considérant que les \(i\) premières maisons. Calculer \(M(1), M(2), M(3)\) à la main.
3. En réfléchissant à ce qui se passe pour la maison \(i\) : soit on la livre (et on ne peut pas livrer la maison \(i-1\)), soit on ne la livre pas (et on garde le meilleur résultat sur les \(i-1\) premières maisons). Expliquer avec des mots comment calculer \(M(i)\) à partir des valeurs précédentes.
4. Compléter le tableau :
| \(i\) | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| colis | — | 2 | 7 | 9 | 3 | 1 | 5 |
| \(M(i)\) | 0 |
5. Donner la valeur optimale et indiquer quelles maisons ont été sélectionnées.
Exercice 3 — Pavage d’un couloir ✏️
On veut paver un couloir de longueur \(n\) avec des dalles de longueur 1 ou 2. On cherche le nombre de façons différentes de paver ce couloir.
1. Trouver à la main le nombre de pavages pour \(n = 1, 2, 3, 4\).
2. Dessiner tous les pavages possibles pour \(n = 4\).
3. Expliquer avec des mots comment le nombre de pavages pour un couloir de longueur \(n\) se déduit des longueurs précédentes. (Indication : réfléchir à la première dalle posée.)
4. Un élève propose l’algorithme récursif suivant :
def pavages(n):
if n == 0 or n == 1:
return 1
return pavages(n - 1) + pavages(n - 2)Quel est le problème avec cet algorithme pour de grandes valeurs de \(n\) ? Comment y remédier ?
5. Calculer le nombre de pavages pour \(n = 10\) grâce à la méthode ascendante.
Exercice 4 — Synthèse : choisir la bonne méthode ✏️
Pour chacun des problèmes suivants, indiquer si on peut appliquer la programmation dynamique, un algorithme glouton, ou les deux (ou aucun), et justifier brièvement.
| Problème | Méthode applicable | Justification |
|---|---|---|
| Trouver le chemin le plus court dans un graphe sans poids négatifs (algorithme de Dijkstra) | ||
| Trouver la plus longue suite croissante dans une liste | ||
| Sélectionner des activités non chevauchantes pour remplir au mieux un agenda | ||
| Colorer une carte géographique avec le moins de couleurs possible | ||
| Calculer le nombre de chemins dans une grille de \(n \times m\) cases (en allant uniquement à droite ou en bas) |