Trier une pile de feuille de papier numéroté, un algorithme???

Question

Bonjour.

Je fabrique présentement un robot qui doit trier une pile de feuille de papier numéroté.

Il y a une pile de 500 feuilles devant le robot, chaque feuille étant numéroté de 1 à 500. Ces feuilles ne sont pas dans l'ordre.

Le robot peut lire les chiffres sur les feuilles. Il peut créer jusqu'à environ 3 piles de papier cote à cote près de lui (maximum 5 faute d'espace sur la table), pour se donner des espaces temporaire afin d'effectuer son tri. Le robot ne peut insérer une feuille entre deux autres, il peut uniquement la placer sur le dessus d'une des pile. Un peu sur le principe des tours de Hanoi.

voir:    http://javaboy.free.fr/tourdehanoi/index.htm

Au contraire des tours de Hanoi, un chiffre plus grand peut être placer sur un plus petit si besoin durant le tri.

La pile de feuilles finale doit-être trier de 1 à 500.

J'essais de trouver un algorithme de tri efficace pour automatiser mon robot.
Je peux utiliser des listes en mémoires pour m'aider dans mon travail, des variables, etc, la seule restriction est la porter du bras du robot qui peut s'étendre jusqu'à un maximum de 5 piles (moin de piles est encore mieux car moin de long déplacement). Bien entendu le bras du robot doit se promène d'une pile de feuilles à l'autre et c'est surtout à ce niveau que je suis pénalisé. Si le robot prend par exemple 2 ou 3 secondes pour prendre, déplacer et déposer la feuille sur une autre feuille, et qu'il doit effectuer 100 000 déplacements, 4 jours et il aura à peine terminé.

Avez-vous des suggestions sur quel algorythm ou quel facon je devrais procédé pour faire le tri?

Merci beaucoup.
Michel

JulioDelphi · Answer

Salut,
Je te propose 3 piles :
pile 1 : les 500 feuilles
pile 2 : pile de passage
pile 3 : pile finale dan l'ordre

X:=1;
index:=Nombre de pages à trier.

0) le robot est devant la pile 1.
1) le robot regarde la premiere feuille de cette pile, si c'est la n°index, il la pose dans la pile 3 et décrémente index de 1 sinon il la pose en pile 2.
2) le robot vérifie si il y a encore des feuilles dans la pile 1, si oui, voir (1), si non il se tourne vers la pile 2 puis voir (3)
3) le robot vérifie si il y a encore des feuilles dans la pile 2, si oui, voir (1), si non il se tourne vers la pile 1 puis voir (1)
4) si index = 0 alors la pile 3 est en ordre.

Tu auras de 500 à 125250 mouvements maximum pour 500 pages il me semble.

cs_Kenavo · Answer

Salut,

On doit pouvoir améliorer en mémorisant l'ordre des feuilles au fur et à mesure, ce qui permet, à chaque feuille trouvée de savoir si la suivante est dans la pile 1 ou la pile 2.
 
Sachant que dans le pire des cas, ça n'améliorera pas la vitesse .....
Le pire des cas : les feuilles sont dans l'ordre suivant : 499,497,495,493,..........494,496,498,500

... et 125250 mouvements, à 1 mouvement par seconde, ça fait presque 35 heures 

Ken@vo




<hr size="2" width="100%" />



Code, Code, Codec !

Trier une pile de feuille de papier numéroté, un algorithme???

2 réponses

Votre réponse

Discussions similaires