Ceci est une ancienne révision du document !

Warning: Undefined array key 1 in /home/goupillf/wiki.goupill.fr/lib/plugins/codeprettify/syntax/code.php on line 172

Warning: Undefined array key 2 in /home/goupillf/wiki.goupill.fr/lib/plugins/codeprettify/syntax/code.php on line 214

Warning: Undefined array key 2 in /home/goupillf/wiki.goupill.fr/lib/plugins/codeprettify/syntax/code.php on line 214

Table des matières

Glouton : Chemin dans une grille

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

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

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 : grid.csv

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

À faire

Écrire la fonction glouton(grid) qui reçoit la grille et qui renvoie :

le score obtenu
le parcours sous la forme, par exemple "DDDBBDBBDDDBDDBB" où D représente un pas vers la droite et B un pas vers le bas.

Écrire la fonction load_grid(filename) chargeant une grille depuis un fichier.

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

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

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

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

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

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