127 lines
4.3 KiB
Markdown
127 lines
4.3 KiB
Markdown
# TP — Le Donjon du Dragon
|
||
|
||
## Contexte
|
||
|
||
Vous jouez à un RPG en vue du dessus. Vous venez d'entrer dans un donjon représenté par une **grille de n lignes et m colonnes**.
|
||
|
||
Chaque case de la grille contient une quantité d'or :
|
||
- Une valeur **positive** : de l'or à ramasser 🪙
|
||
- Une valeur **négative** : un piège qui vous coûte de l'or 💀
|
||
|
||
**Règles du jeu :**
|
||
- Vous commencez en haut à gauche : case `(0, 0)`
|
||
- Vous devez atteindre la sortie en bas à droite : case `(n-1, m-1)`
|
||
- Vous ne pouvez vous déplacer **que vers la droite ou vers le bas**
|
||
- Vous souhaitez **maximiser l'or total ramassé**
|
||
|
||
**Exemple de grille 3×4 :**
|
||
|
||
```
|
||
[ 3, -1, 4, 1 ]
|
||
[ 5, 9, -2, 6 ]
|
||
[ -3, 2, 8, -5 ]
|
||
```
|
||
|
||
Un chemin possible : (0,0)→(1,0)→(1,1)→(1,2)→(2,2)→(2,3) → or = 3+5+9-2+8-5 = **18**
|
||
|
||
Est-ce le meilleur chemin ? C'est ce que vous allez découvrir.
|
||
|
||
## Partie 1 — Comprendre le problème
|
||
|
||
**Question 1.** Sur la grille ci-dessus, listez tous les chemins possibles de `(0,0)` à `(2,3)` en ne se déplaçant que vers la droite ou vers le bas. Combien y en a-t-il ?
|
||
|
||
**Question 2.** Pour chaque chemin, calculez l'or total ramassé. Quel est le chemin optimal ?
|
||
|
||
**Question 3.** Pour une grille de dimensions `n × m`, combien y a-t-il de chemins possibles en tout ? *(Indice : c'est une formule combinatoire.)*
|
||
|
||
## Partie 2 — Formulation récursive
|
||
|
||
Notons `donjon(i, j)` l'or maximum qu'on peut ramasser depuis `(0, 0)` jusqu'à `(i, j)`.
|
||
|
||
**Question 4.** Quels sont les cas de base de cette fonction récursive ? *(Pensez aux bords de la grille.)*
|
||
|
||
**Question 5.** Écrivez la relation de récurrence générale pour `donjon(i, j)` quand `i > 0` et `j > 0`.
|
||
|
||
**Question 6.** Implémentez la version naïve `donjon_naif(grille, i, j)` :
|
||
|
||
```python
|
||
def donjon_naif(grille, i, j):
|
||
# À compléter
|
||
pass
|
||
|
||
# Test
|
||
grille = [
|
||
[ 3, -1, 4, 1],
|
||
[ 5, 9, -2, 6],
|
||
[-3, 2, 8, -5]
|
||
]
|
||
n, m = len(grille), len(grille[0])
|
||
print(donjon_naif(grille, n-1, m-1)) # doit afficher 22
|
||
```
|
||
|
||
## Partie 3 — Version Top-Down (mémoïsation)
|
||
|
||
**Question 7.** La version naïve recalcule-t-elle des sous-problèmes plusieurs fois ? Pour répondre, ajoutez un compteur d'appels et testez sur la grille ci-dessus.
|
||
|
||
**Question 8.** Implémentez `donjon_memo(grille)` avec mémoïsation :
|
||
|
||
```python
|
||
def donjon_memo(grille):
|
||
n = len(grille)
|
||
m = len(grille[0])
|
||
memo = {}
|
||
|
||
def donjon(i, j):
|
||
# À compléter
|
||
pass
|
||
|
||
return donjon(n - 1, m - 1)
|
||
```
|
||
|
||
**Question 9.** Vérifiez que vous obtenez le même résultat que la version naïve.
|
||
|
||
## Partie 4 — Version Bottom-Up (tableau)
|
||
|
||
**Question 10.** Remplissez à la main le tableau `t[i][j]` représentant l'or maximum qu'on peut ramasser **depuis `(0,0)` jusqu'à `(i,j)`** pour la grille de l'exemple.
|
||
|
||
**Question 11.** Implémentez `donjon_bottom_up(grille)` :
|
||
|
||
```python
|
||
def donjon_bottom_up(grille):
|
||
n = len(grille)
|
||
m = len(grille[0])
|
||
tableau = [[0] * m for _ in range(n)]
|
||
|
||
# Initialiser tableau[0][0]
|
||
# Initialiser la première ligne (on ne peut aller que vers la droite)
|
||
# Initialiser la première colonne (on ne peut aller que vers le bas)
|
||
# Remplir le reste du tableau
|
||
# À compléter
|
||
|
||
return tableau[n - 1][m - 1]
|
||
```
|
||
|
||
**Question 12.** Vérifiez que vous obtenez le même résultat que les versions précédentes.
|
||
|
||
## Partie 5 — Bonus : retrouver le chemin optimal
|
||
|
||
**Question 13.** *(Bonus)* Modifiez `donjon_bottom_up` pour qu'elle retourne non seulement la valeur optimale, mais aussi **la liste des cases du chemin optimal**.
|
||
|
||
*(Indice : une fois le tableau rempli, remontez depuis `(n-1, m-1)` vers `(0,0)` en choisissant à chaque étape la case voisine (gauche ou haut) qui a la plus grande valeur.)*
|
||
|
||
```python
|
||
def donjon_chemin(grille):
|
||
# À compléter
|
||
# Retourne (valeur_max, chemin)
|
||
# chemin = liste de tuples (i, j) de (0,0) à (n-1, m-1)
|
||
pass
|
||
```
|
||
|
||
---
|
||
|
||
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>.
|