Le crêpier psychorigide

info

📈 Objectifs pédagogique

• Résoudre un problème simple
• Se questionner sur les étapes de résolution
• Traduire un problème en un algorithme

Le problème

Bienvenue dans la crêperie la plus célèbre du monde : Chez Maître Crêpier. À la fin de sa journée, le crêpier dispose d'une pile désordonnée de crêpes. Or, Maître Crêpier est très pointilleux : il exige que les crêpes soient rangées par ordre de taille, de la plus petite en haut à la plus grande en bas.

Mais attention ! Dans sa crêperie, on ne déplace pas les crêpes n'importe comment, on n'a qu'une seule opération possible :

Glisser sa spatule entre deux crêpes et retourner le haut de la pile.

Votre mission

Exercice 1

Manipuler la pile de crêpes pour les ranger dans l'ordre demandé.

Exercice 2 (en binôme)

L'un des élèves du groupe sera l'ordinateur et un autre sera le programmeur. Le programmeur dicte à l'ordinateur une série d'instructions qui vont permettre de trier la pile de crêpe. L'ordinateur exécute mécaniquement les instructions proposées par l'ordinateur. Si les instructions ne sont pas claires, l'ordinateur demande une reformulation.

Exercice 3

En vous inspirant de l'exercice 2, rédiger un algorithme en langage naturel qui permet de trier la pile de crêpes.

Aides à la résolution

🔎 Aide 1

Essayer d'abord de mettre la plus grande crêpe en bas de la pile.

🔎 Aide 2

Où doit se trouver la grande crêpe pour pouvoir l'amener en bas ?

🔎 Aide 3

Pour amener la grande crêpe en bas, il faut d'abord la mettre en haut.

Prolongements

Prolongement 1

Calculer la complexité de l'algorithme que vous avez rédigé.

Solution au prolongement 1

• Pour ranger une crêpe: il faut entre $0$ coup (si la crêpe est déjà rangée) et $2$ coups (la mettre en haut puis à sa place)
• Pour $n$ crêpes, il faut entre $0$ coups (si toutes les crêpes sont déjà rangées) et $2n$ coups (pire situation)

On a donc une complexité algorithmique de $O(2n)$.

Prolongement 2

Chaque crêpe a un coté brûlé et un coté non brûlé. Le crêpier exige que les crêpes soient rangées par ordre de taille, de la plus petite en haut à la plus grande en bas, et que le coté non brûlé soit toujours visible.

• Ecrire un algorithme qui permet de trier la pile de crêpes en respectant cette nouvelle contrainte.
• Calculer la complexité de cet algorithme.

Solution au prolongement 2

Voici un algorithme qui permet de trier la pile de crêpes en respectant cette nouvelle contrainte :

1. Amener la plus grande crêpe en haut de la pile
2. Mettre la face brûlée vers le haut
3. Retourner toute la pile - la crêpe est rangée
4. Recommencer en ignorant les crêpes rangées

On a donc une complexité algorithmique de $O(3n)$.