6. Exercices et corrigés

6. Exercices et corrigés

6.1 Modélisation

La feuille d’exercices demande de formaliser les cinq billes et les douze maillons. Le but pédagogique est de produire une structure exploitable par un programme, pas seulement une suite intuitive de mouvements. Pour chaque problème, vérifier systématiquement : domaine des variables, état initial, but, opérations, préconditions, effets et invariants.

Les corrigés montrent deux styles valides : des substitutions locales sur une séquence pour les billes, et des transformations d’un ensemble de couples pour les chaînes.

6.2 Parcours du graphe de A à X

Sans revisiter les états et en respectant l’ordre numéroté des arcs, le corrigé donne :

• profondeur : A, C, H, Q, R, P, I, G, D, J, S, T, U, K, E, M, L, X;
• largeur : A, C, D, E, B, H, I, G, J, K, M, L, F, Q, R, P, S, T, U, X.

Ces séquences représentent l’ordre complet des états examinés jusqu’à X, non le seul chemin de A à X. Une coquille figurait dans une version initiale du solutionnaire; la copie locale correspond à la version corrigée.

6.3 Jeu du taquin

La configuration finale est LF=[1,2,3,8,*,4,7,6,5]. Il faut déterminer si chaque trace pourrait provenir de la largeur, de la profondeur, des deux ou d’aucune, en raisonnant sur l’ordre de développement :

• L1, déplacement gauche : largeur et profondeur;
• L2, haut puis droite : largeur seulement;
• L3, gauche, droite, bas : largeur seulement.

Une trace courte peut être compatible avec plusieurs stratégies. Ce n’est pas uniquement l’atteinte du but qui les distingue, mais l’ordre imposé aux successeurs dans la file ou la pile.