Exercices — Programmation Dynamique
Exercice 1 — L'escalier
Vous souhaitez monter un escalier de n marches. À chaque étape, vous pouvez monter 1 marche ou 2 marches. Combien existe-t-il de façons différentes d'atteindre la n-ième marche ?
Exemples :
- n = 1 : 1 façon (1)
- n = 2 : 2 façons (1+1, 2)
- n = 3 : 3 façons (1+1+1, 1+2, 2+1)
- n = 4 : 5 façons
1. Calculez à la main le nombre de façons pour n = 5.
2. Quelle ressemblance observez-vous avec une suite mathématique vue dans le cours Récursivité ?
3. Écrivez la relation de récurrence pour escalier(n).
4. Implémentez escalier_memo(n) en utilisant la mémoïsation.
5. Implémentez escalier_bottom_up(n) en utilisant un tableau.
6. Vérifiez que vos deux fonctions donnent les mêmes résultats pour n allant de 1 à 10.
Exercice 2 — Rendu de monnaie revisité
On dispose de pièces de valeurs [2, 5, 10] (en centimes).
1. L'algorithme glouton peut-il rendre 6 centimes avec ce système ? Justifiez.
2. La programmation dynamique peut-elle rendre 6 centimes ? Justifiez.
3. Écrivez la fonction rendu_bottom_up(pieces, somme) (version bottom-up vue en cours) et testez-la avec :
- pieces = [2, 5, 10], somme = 6
- pieces = [1, 3, 4], somme = 6
- pieces = [1, 5, 6, 9], somme = 11
4. Modifiez la fonction pour qu'elle retourne non seulement le nombre de pièces, mais aussi la liste des pièces utilisées (comme la reconstruction dans le sac à dos).
Exercice 3 — Sac à dos : à la main et en code
On dispose des objets suivants, avec un sac de capacité 6 kg :
| Objet | Poids | Valeur |
|---|---|---|
| A | 1 kg | 2 |
| B | 2 kg | 5 |
| C | 3 kg | 8 |
| D | 4 kg | 9 |
1. Remplissez à la main le tableau tableau[i][w] pour i de 0 à 4 et w de 0 à 6.
2. Quelle est la valeur maximale atteignable ?
3. En remontant le tableau, déterminez quels objets sont dans la solution optimale.
4. Vérifiez vos réponses en exécutant sac_reconstruction(objets, 6).
Exercice 4 — Triangle de Pascal ★
Le triangle de Pascal est construit selon la règle suivante : - Les bords valent toujours 1 - Chaque case intérieure est la somme des deux cases au-dessus d'elle
1. Écrivez la relation de récurrence : pascal(ligne, col) = ?
2. Implémentez triangle_pascal(n) par programmation dynamique bottom-up, qui retourne les n premières lignes du triangle sous forme de liste de listes.
3. Vérifiez que triangle_pascal(5) donne [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]].
4. (Bonus) La somme des éléments de la ligne n est-elle liée à une valeur vue dans ce chapitre ?
Auteur : Florian Mathieu
Licence CC BY NC
Ce cours est mis à disposition selon les termes de la Licence Creative Commons Attribution - Pas d'Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International.