Le labyrinthe
Tu es dans un labyrinthe. Tu n'as pas de plan. Que fais-tu ?
Tu avances dans un couloir jusqu'au bout. Si c'est une impasse, tu reviens au dernier croisement, et tu prends un autre couloir. Tu ne repasses jamais deux fois par la même salle.
C'est le parcours en profondeur. Il va loin d'abord, avant de regarder à côté.
Mots-clés
| Mot | Ce que ça veut dire | Exemple |
|---|---|---|
| Parcours en profondeur | On va le plus loin possible dans un couloir avant de revenir en arrière. | Explorer un labyrinthe |
| Pile | Une liste où le dernier arrivé est le premier sorti. | Une pile d'assiettes |
| Cycle | Un trajet qui revient à son point de départ, sans repasser par la même arête. | Salle1, Salle3, Salle4, Salle2, Entree |
| Parent | Le sommet d'où l'on vient, quand on explore. | Entree est le parent de Salle1 |
| Impasse | Une salle dont tous les voisins sont déjà vus : on ne peut qu'en revenir. | Salle3, dans le premier plan |
| Retour en arrière | Revenir au dernier croisement pour essayer un autre couloir. | Quitter Salle3 pour Salle1 |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
À toi : que faire en cul-de-sac ?
À toi de jouer
À toi : que faire en cul-de-sac ?
3 questionsTes réponses sont corrigées ici et ne sont pas conservées. Un compte garde tes résultats.
Une fonction qui s'appelle
Explorer une salle, c'est : la noter comme vue, puis explorer chaque voisine pas encore vue. Quand toutes sont faites, la fonction se termine et on revient à la salle d'avant.
Le retour en arrière se fait tout seul, grâce à la récursivité. Tu l'as vue dans la leçon « Une fonction qui s'appelle ».
Exemple travaillé : l'exploration depuis Entree
| Étape | On est dans | Ce qui se passe | Salles vues |
|---|---|---|---|
| 1 | Entree | Première voisine : Salle1, nouvelle | Entree |
| 2 | Salle1 | Entree est vue. Salle3 est nouvelle | Entree, Salle1 |
| 3 | Salle3 | Salle1 est vue : impasse, on revient | Entree, Salle1, Salle3 |
| 4 | Entree | Salle1 est finie. Salle2 est nouvelle | Entree, Salle1, Salle3 |
| 5 | Salle2 | Entree est vue. Salle4 est nouvelle | Entree, Salle1, Salle3, Salle2 |
| 6 | Salle4 | Salle2 est vue. Tresor est nouveau | Entree, Salle1, Salle3, Salle2, Salle4 |
| 7 | Tresor | Impasse : on revient jusqu'à l'Entree. Fini | Les six salles |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
À toi : explorer le labyrinthe
labyrinthe = {
"Entree": ["Salle1", "Salle2"],
"Salle1": ["Entree", "Salle3"],
"Salle2": ["Entree", "Salle4"],
"Salle3": ["Salle1"],
"Salle4": ["Salle2", "Tresor"],
"Tresor": ["Salle4"],
}
def explorer(graphe, salle, vues):
vues.append(salle)
print("Je suis dans", salle)
for voisine in graphe[salle]:
if voisine not in vues:
explorer(graphe, voisine, vues)
print("Cul-de-sac ou fini : je reviens de", salle)
vues = []
explorer(labyrinthe, "Entree", vues)
print("Ordre de visite :", vues)
# Mets "Salle2" avant "Salle1" dans la liste de l'entrée. Que change l'ordre ?
À toi : l'ordre de visite
À toi de jouer
À toi : l'ordre de visite
3 questionsTes réponses sont corrigées ici et ne sont pas conservées. Un compte garde tes résultats.