Livre_silo 30 août 2013 16:32 Page 312
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
312
Informatique pour tous
Enfin, on écrit la fonction de construction du labyrinthe, labyrinthe. Elle utilise une pile
nommée pile contenant les emplacements à partir desquels on est susceptible de se déplacer. Initialement, on y place la case (0, 0) et on la marque comme visitée :
def labyrinthe():
pile = creer_pile(n*n)
empiler(pile, (0,0))
visiter((0,0))
Tant que cette pile n’ est pas vide, on en extrait le sommet, cellule :
while not est_vide(pile):
cellule = depiler(pile)
On examine alors les déplacements encore possibles à partir de cellule, donnés par la fonction choix. S’il en existe au moins un, on en choisit un au hasard avec tirage :
c = choix(cellule)
if len(c) > 0:
suivante = tirage(c)
On relie alors les cases cellule et suivante, par exemple en effectuant un tracé dans une
fenêtre graphique. Puis on marque la case suivante comme étant atteinte, avec la fonction
visiter :
# c'est ici qu'on relie les cases cellule et suivante
visiter(suivante)
Enfin, on remet cellule dans la pile, puis on ajoute suivante. Ainsi, le parcours reprendra à
partir de suivante dès l’itération suivante de la boucle :
empiler(pile, cellule)
empiler(pile, suivante)
Une très légère optimisation consisterait à ne pas remettre cellule dans la pile si elle n’avait
maintenant plus de voisins c’est-à-dire si c ne contenait qu’un seul élément. Toutefois, c’est
inutilement compliqué : la prochaine fois que cellule sortira de la pile, on se contentera de
ne rien faire.
Le code complet est donné programme 15 ci-contre.
Exercice 12.10 * Compléter le programme 15 pour effectivement créer l’image du labyrinthe (voir annexe B.2 pour la création d’une image dans un fichier).
Exercice 12.11 ** Compléter le programme 15 pour construire à la volée le chemin qui mène de l’entrée
(0, 0) à la sortie (49, 49). Puisqu’il existe un unique chemin entre toute paire de points, il suffit pour cela
de mémoriser quelle case a permis d’arriver à chaque endroit à partir de l’entrée, puis de remonter le long
de ces cases à partir de la sortie.
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
312
Informatique pour tous
Enfin, on écrit la fonction de construction du labyrinthe, labyrinthe. Elle utilise une pile
nommée pile contenant les emplacements à partir desquels on est susceptible de se déplacer. Initialement, on y place la case (0, 0) et on la marque comme visitée :
def labyrinthe():
pile = creer_pile(n*n)
empiler(pile, (0,0))
visiter((0,0))
Tant que cette pile n’ est pas vide, on en extrait le sommet, cellule :
while not est_vide(pile):
cellule = depiler(pile)
On examine alors les déplacements encore possibles à partir de cellule, donnés par la fonction choix. S’il en existe au moins un, on en choisit un au hasard avec tirage :
c = choix(cellule)
if len(c) > 0:
suivante = tirage(c)
On relie alors les cases cellule et suivante, par exemple en effectuant un tracé dans une
fenêtre graphique. Puis on marque la case suivante comme étant atteinte, avec la fonction
visiter :
# c'est ici qu'on relie les cases cellule et suivante
visiter(suivante)
Enfin, on remet cellule dans la pile, puis on ajoute suivante. Ainsi, le parcours reprendra à
partir de suivante dès l’itération suivante de la boucle :
empiler(pile, cellule)
empiler(pile, suivante)
Une très légère optimisation consisterait à ne pas remettre cellule dans la pile si elle n’avait
maintenant plus de voisins c’est-à-dire si c ne contenait qu’un seul élément. Toutefois, c’est
inutilement compliqué : la prochaine fois que cellule sortira de la pile, on se contentera de
ne rien faire.
Le code complet est donné programme 15 ci-contre.
Exercice 12.10 * Compléter le programme 15 pour effectivement créer l’image du labyrinthe (voir annexe B.2 pour la création d’une image dans un fichier).
Exercice 12.11 ** Compléter le programme 15 pour construire à la volée le chemin qui mène de l’entrée
(0, 0) à la sortie (49, 49). Puisqu’il existe un unique chemin entre toute paire de points, il suffit pour cela
de mémoriser quelle case a permis d’arriver à chaque endroit à partir de l’entrée, puis de remonter le long
de ces cases à partir de la sortie.