home home accès étudiants up

 

Tri de crêpes

Nous avons une pile de crêpes de diamètres différents que nous désirons trier de façon que la plus petite crêpe soit au sommet de la pile et la plus grande crêpe soit au bout de la pile. Nous avons à notre disposition une spatule et nous pouvons effectuer une seule opération appelée inversion.

On effectue une inversion de la manière suivante. On prend la spatule avec la main droite et on l'insère entre deux crêpes dans la pile (ou sous la dernière crêpe de la pile). Ensuite on met la main gauche au sommet de la pile et on inverse la partie de la pile entre la spatule et la main gauche d'un coup sec. Enfin on retire les mains.

Voici un exemple de tri d'une pile de 5 crêpes par 5 inversions.

crepes

Le but de ce TP est d'estimer par simulation le nombre moyen d'inversions nécessaires pour trier n crêpes.

Nous allons représenter une pile par un tableau d'entiers, chaque élément étant le diamètre d'une crêpe. pile[0] est le sommet de la pile et pile[n-1] est le bout de la pile.

Exercice 1.

Ecrire une fonction qui initialise une pile de n crêpes. D'abord on remplie la pile de crêpes de diamètres 1...n. Ensuite on fait n2 inversions aléatoires pour bien mêler les crêpes.

Exercice 2.

Ecrire une fonction qui trie une pile de crêpes par inversions. Essayez de minimiser le nombre d'inversions effectuées. La fonction doit renvoyer ce nombre. Elle fonctionne en deux modes. En mode de débougage la fonction affiche la pile avant chaque inversion et après la dernière inversion, par exemple 

  3   2   5|  1   4
  5   2   3   1   4|
  4   1   3   2|  5
  2   3|  1   4   5
  3   2   1|  4   5
  1   2   3   4   5
En mode normal, la fonction n'affiche rien. Implémenter les deux modes en utilisant des directives #ifdef.


Mettre les fonctions d'initialisation et de tri, ainsi que leurs fonctions auxiliaires, dans un fichier crepes.c. Créer un fichier crepes.h contenant les prototypes des deux fonctions.


Exercice 3.

Ecrire un programme de test qui initialise et trie une pile de 10 crêpes. Mettre le programme dans un fichier différent. Compiler en mode de débougage. Exécuter et s'assurer que tout marche bien.

Exercice 4.

Ecrire un programme qui demande à l'utilisateur un nombre de crêpes n et un nombre de tentatives m. Ensuite le programme initialise et trie m fois une pile de n crêpes et calcule le nombre moyen d'inversions effectuées sur les m tentatives.

Après avoir effectué plusieurs simulations, faire une hypothèse sur le lien entre le nombre de crêpes et le nombre d'inversions effectuées.