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) |