Article : Les crêpes - Lycée de La Mure (Isère)

Article
Résumé de la production
Comment avec une simple palette, remettre dans l'ordre les crêpes d'une pile ? Au départ, n crêpes (de tailles toutes différentes) sont empilées n'importe comment. On veut les ranger par ordre décroissant, de la plus grande en bas à la plus petite en haut, en effectuant le moins de manipulation possible. La seule opération permise est d'insérer une palette entre deux crêpes et de retourner en bloc le haut de la pile. En explorant l'arbre des possibilités, les auteurs de cet article obtiennent un minoration du nombre de mouvements nécessaires. Ils proposent une méthode qui, pour n≥5, n'utilise pas plus de 2n-5 mouvements.
Mots clés
tri
pile
permutation
retournement
ordre croissant
algorithme
minimum
arbre de possibilités