informatique (MP2I/MPI) · Chapitre 7 · Application directe du cours
Problème — Le même parcours, deux structures
Structures séquentielles : listes, piles, files · niveau 3 (difficile)
Énoncé
Le chapitre annonce que « le seul remplacement d'une pile par une file transforme un parcours en profondeur en parcours en largeur ». On va le vérifier sur une grille.
- Écrire un parcours générique, où la structure de réserve n'apparaît que par ses trois opérations.
- L'exécuter avec une pile, puis avec une file, sur la grille ci-dessous, et comparer les ordres de visite.
- L'un des deux donne les distances les plus courtes. Lequel, et pourquoi l'autre ne le fait pas ?
....# la case (0,0) est en haut a gauche
.##.# # est un mur
.#...
...#.Corrigé de la question 1
1. Le parcours générique.
/* Explore la composante de la case de depart. La reserve n'est employee
que par : deposer, retirer, est_vide. AUCUNE autre hypothese.
dist[c] est la distance de c au depart DANS L'ARBRE DE PARCOURS. */
void parcourir(reserve* r) {
marquer(depart); dist[depart] = 0; deposer(r, depart);
while (!est_vide(r)) {
case p = retirer(r);
visiter(p);
for (chaque voisin v de p) {
if (praticable(v) && !marque(v)) {
marquer(v); /* on marque en DEPOSANT, */
dist[v] = dist[p] + 1; /* pas en retirant */
deposer(r, v);
}
}
}
}Un détail qui n'en est pas un : on marque au moment de déposer, non au moment de retirer. Sans cela, une case atteignable par deux chemins serait déposée deux fois, et la réserve pourrait contenir doublons. Le marquage précoce garantit que chaque case est déposée exactement une fois, donc que le parcours est en .
Question 2 : comment l'IA t'aide
2. L'exécuter avec une pile, puis avec une file, sur la grille ci-dessous, et comparer les ordres de visite.
Élève
J'ai déroulé les deux exécutions et les ordres diffèrent, mais je ne sais pas quoi « comparer » au-delà de ce constat : le code est identique.
IA
Regarde, dans chaque cas, la distance des cases dans l'ordre où elles sont visitées. Avec la file, cette suite a-t-elle une propriété particulière ? Et avec la pile ?
Élève
Avec la file, les distances arrivent par paliers croissants. Avec la pile, elles montent longtemps, puis on revient sur une case proche du départ.
IA
Comment décrirais-tu alors géométriquement chacun des deux mouvements sur la grille, et à quoi tient la différence, puisque seule la discipline de la réserve change ?
L'IA ne donne pas la réponse : elle pose la question qui fait avancer. À toi de continuer.
Continue cet exercice avec l'IA
Reprends la question 2 là où le dialogue s'arrête, puis la suite de l'exercice.
Continuer avec l'IA — gratuit, sans inscriptionGratuit, sans inscription. L'IA te guide pas à pas, sans te donner la réponse.