GoupillWiki

Cette page est en lecture seule. Vous pouvez afficher le texte source, mais ne pourrez pas le modifier. Contactez votre administrateur si vous pensez qu'il s'agit d'une erreur.
====== Glouton : Chemin dans une grille ======

===== Présentation =====

On se donne une grille de nombre. Par exemple :

| 17|7|21|71|40|77|58|42|67|48 |
| 1|40|70|54|43|60|19|49|32|6 |
| 58|91|69|75|1|27|89|50|74|77 |
| 96|28|89|18|9|67|30|32|14|52 |
| 24|77|44|83|2|51|20|16|50|69 |
| 53|75|52|3|21|46|59|68|86|24 |
| 52|45|80|82|19|47|18|68|16|92 |
| 14|65|43|16|4|79|61|43|72|88 |

  * On veut suivre un chemin dans cette grille allant de la case en haut à gauche à la case en bas à droite,
  * on ne peut se déplacer que d'une case, vers la droite ou vers le bas,
  * pour chaque case, on cumule le chiffre écrit dans la case.

Le but est d'obtenir le plus grand score.

=== Réprésentation Python de la grille ===

<code python>
grid = [
  [17, 7, 21, 71, 40, 77, 58, 42, 67, 48],
  [1, 40, 70, 54, 43, 60, 19, 49, 32, 6],
  [58, 91, 69, 75, 1, 27, 89, 50, 74, 77],
  [96, 28, 89, 18, 9, 67, 30, 32, 14, 52],
  [24, 77, 44, 83, 2, 51, 20, 16, 50, 69],
  [53, 75, 52, 3, 21, 46, 59, 68, 86, 24],
  [52, 45, 80, 82, 19, 47, 18, 68, 16, 92],
  [14, 65, 43, 16, 4, 79, 61, 43, 72, 88]
]
LIGNES = len(grid)      # nombre de lignes
COLONNES = len(grid[0]) # nombre de colonnes
</code>

=== Exemple ===

| **17** | **7** | **21** | **71** | 40    |77|58|42|67|48 |
| 1      | 40    | 70     | **54** | 43    |60|19|49|32|6 |
| 58     | 91    | 69     | **75** | **1** |27|89|50|74|77 |
| 96     | 28    | 89     | 18     | **9** | 67|30|32|14|52 |
| 24     | 77    | 44     | 83     | **2** | **51** | **20** | **16** | 50 | 69 |
| 53     | 75    | 52     | 3      | 21    | 46     | 59     | **68** | **86** | **24** |
| 52|45|80|82|19|47|18|68|16|**92** |
| 14|65|43|16|4|79|61|43|72|**88** |

Le parcours marqué en gras totalise un score de :
$$17 + 7 + 21 + \cdots + 92 + 88 = 702$$

===== Approche gloutonne =====

À chaque pas, on se dirige vers la case (à droite ou en bas) contenant le score maximal.

===== Avec un fichier =====

On pourrait aussi stocker le contenu de la grille dans un fichier csv comme celui-ci : {{ :nsi:tds:algorithmes:glouton:grid.csv |}}

Il faudrait alors charger le fichier pour lire la grille avant de pouvoir chercher le parcours.

===== À faire =====

Un module

<code python>
# glouton.py

def glouton(grid) -> str:
    """
    grid: tableau 2D contenant des entiers
    renvoie le parcours fait de mouvements H, B, G, D
    donnant le parcours glouton de coin supérieur gauche
    au coin inférieur droit
    """
 
def load_grid(filename:str):
    """
    filename: nom de fichier
    renvoie la grille contenu dans le fichier
    """
</code>

Une première démo :

<code python>
# demo1.py

from glouton import glouton

grid = [
  [17, 7, 21, 71, 40, 77, 58, 42, 67, 48],
  [1, 40, 70, 54, 43, 60, 19, 49, 32, 6],
  [58, 91, 69, 75, 1, 27, 89, 50, 74, 77],
  [96, 28, 89, 18, 9, 67, 30, 32, 14, 52],
  [24, 77, 44, 83, 2, 51, 20, 16, 50, 69],
  [53, 75, 52, 3, 21, 46, 59, 68, 86, 24],
  [52, 45, 80, 82, 19, 47, 18, 68, 16, 92],
  [14, 65, 43, 16, 4, 79, 61, 43, 72, 88]
]
LIGNES = len(grid)      # nombre de lignes
COLONNES = len(grid[0]) # nombre de colonnes

# utilisation de la fonction et affichage de la réponse
</code>

et une deuxième démonstration

<code python>
#demo2.py

import glouton

glouton.load_grid("grid.csv")

# utilisation de la fonction et affichage de la réponse
</code>