94 lines
3.3 KiB
Markdown
94 lines
3.3 KiB
Markdown
# 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
|
|
|
|
```
|
|
Ligne 0 : 1
|
|
Ligne 1 : 1 1
|
|
Ligne 2 : 1 2 1
|
|
Ligne 3 : 1 3 3 1
|
|
Ligne 4 : 1 4 6 4 1
|
|
```
|
|
|
|
**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
|
|
|
|
<a rel="license" href="http://creativecommons.org/licenses/by-nc-sa/4.0/"><img alt="Licence Creative Commons" style="border-width:0" src="https://i.creativecommons.org/l/by-nc-sa/4.0/88x31.png" /></a> <br />Ce cours est mis à disposition selon les termes de la <a rel="license" href="http://creativecommons.org/licenses/by-nc-sa/4.0/">Licence Creative Commons Attribution - Pas d'Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International</a>.
|