Manœuvres et cabotage

[Aldayo]

Désolé, j'ai complètement zappé hier soir : j'y avais pourtant pensé le midi mais je voulais publier que le soir


Deux solutions différentes en 10 coups : Jojo37 le lundi même et 6 jours plus tard, piko30

Jojo :

Celle de piko :

Pour cette semaine, merci donc d'envoyer vos résultat à Jojo37

[Jojo37]

Bonjour à tous.
Bravo à Piko30.
Ma boite est prete pour vos solutions au nouveau problème.
Bonne semaine

[bogie-wogie]

Un petit aux deux participants !

Pourquoi "petit" ? Ben, parce qu'on pouvait faire mieux : en 8 coups. La preuve :

Sont-ils devenus trop difficiles ces problèmes ?
Je ne le pense pas... D'un autre côté... C'est peut-être la raison pour laquelle il n'y a pas de nouveaux participants. Je vais essayer de faire une sorte de bilan et de réorienter mes problèmes (celui de cette semaine est du genre facile et à la portée de tous, malgré les apparences [trompeuses ].

Je vais d'autre part faire un petit rappel des "trucs et astuces" de base pour déjouer certains pièges et se faciliter la tâche. Certaines techniques peuvent paraître évidentes quand on pratique régulièrement ce sport cérébral (comme dans mon cas) et elles ne le sont pas toujours.

Je vais donc essayer de pondre quelque chose dans les jours (ou les semaines) qui viennent.

bw

[Jojo37]

Rebonjour à tous.
Non,B.W,les problèmes ne sont pas trop durs,tout simplement ;pour ma part;quand je tiens une solution à 8,9,10 voire 11 coups,je pense avoir la meilleure et à l'arrivée,je m'aperçois qu'il y avait mieux.
Encore merci d'avoir relancé le jeu.

[bogie-wogie]

Comme promis, voici un premier épisode de mon nouveau feuilleton sur les "Trucs et Astuces du Triage de Jeuvret". Pour certains participants assidus j'enfonce ici sans doute une porte ouverte, pour d'autres ce sera peut-être une découverte. A chacun d'y trouver son bonheur...

Préambule
Sauf mention contraire les astuces et raisonnements présentés dans cette série concernent essentiellement le tri de rames dans lesquelles tous les wagons sont différents (ou plus exactement : ont des destinations différentes). Le cas des wagons multiples sera examiné dans l’une des dernières astuces. D’autre part, après bien des hésitations, j’ai tout de même consacré une astuce (la n° 5, à moins que cela change d’ici là) à la notation par « wagons déplacés ». Elle est très compacte, complète, et permet à la fois de mieux expliquer et de mieux comprendre certains raisonnements pour faciliter la recherche de solutions.

Astuce 1 : minimum absolu.

Il est toujours intéressant et utile, en abordant un problème de triage, de connaître la limite qu’on ne pourra pas franchir, c’est-à-dire le nombre minimum absolu de coups nécessaires pour trier une rame donnée. Ce minimum absolu, malgré les apparences, est une valeur facile à calculer. C’est : µ = 2g+1 (avec g positif, non nul).

« g » est le nombre de « glisses » dans la rame, c’est-à-dire le nombre de paires de wagons consécutifs dans lesquelles le deuxième doit venir se placer devant le premier. Un peu abstrait tout ça, alors quelques exemples simples :

Prenons la rame CAEDBF. Les wagons en rouge (A, D et B) devront être déplacés pour venir devant celui qui les précède et répondent au critère. Il y en a g = 3, donc pour cette rame il ne sera pas possible de descendre en dessous de µ = 2x3+1 = 7 coups. Et vous pouvez vérifier que la meilleure solution est effectivement en 7 coups.

Mais c’est un minimum absolu, de principe, et dans certains cas il ne sera pas possible de l’atteindre. Par exemple la rame CBFEAD est aussi caractérisée par g=3 et un minimum absolu de 7, mais sa meilleure solution nécessite 9 coups, pas un de moins. Une autre astuce, plus complexe, permet de le comprendre.

Il en va de même pour la rame CBAEDF qui a un minimum absolu de 7 mais qui se résout en 8 coups, pas un de moins. L’astuce 3 expliquera pourquoi.

Ce minimum absolu ne garantit donc pas le nombre de coups nécessaire pour trier une rame donnée mais dans de nombreux cas il donne tout de même le nombre de coups effectif, et dans bien d’autres cas il permet de déterminer ce nombre de coups effectif quand il est différent. C’est donc un élément fort utile à connaître avant même de commencer à trier une rame.

Le cas le plus simple est celui de la rame BA où g=1 et le minimum vaut 3 (et 3 coups sont effectivement nécessaires pour la trier). Par contre une rame telle que ABC, pour laquelle g=0, ne satisfait pas le critère d’application de notre formule : g ne doit en effet pas être nul. Le minimum absolu pour ABC et toutes les rames de ce type vaut 0 puisqu’il n’y a aucun tri à faire…

Petit exercice pour terminer : combien vaut le minimum absolu pour la rame FEDCBA ? C’est aussi le nombre de coups suffisant pour la trier.

Existe-t-il une formule donnant un minimum µ plus exact (ou plus proche de la solution minimale réelle lorsque la formule présentée ici est trop optimiste) ? C’est probable, mais je n’ai pour l’instant rien trouvé de mieux.

bw

[Jojo37]

Bonsoir à tous.
A quelques heures de la fin du dernier défi,toujours aucune solutions reçue.
Enfin,il est encore temps,un message parvient plus vite à son destinataire que par la poste.

[Aldayo]

La mienne compte pour du beurre ? (fondu vu que tu l'as depuis une semaine )

[Jojo37]

Bonsoir à tous.
Excuses moi,Aldayo,je n'avais pas réouvert ma boite de réception,j'aurai du le mettre en non lu,comme ça,je ne l'aurais pas oublié.
Pour reprendre tout à zéro;l'heure fatidique des résultats arrive et je n'ai toujours qu'une seule réponse,celle d'Aldayo.
Je vais attendre 21heures.
A tout à l'heure .

[dania]

aaargh ... trop tard pour s'y mettre.
mais a priori, 10coups c'est faisable ...

[Jojo37]

Bonsoir à tous.Comme je le marquais tout à l'heure,une seule réponse,celle de Aldayo,qui par la mème occasion est donc désigné vainqueur.
Résultats obtenus en 9 coups.
Pour ma part,j'arrivais à 10 coups de 3 façons différentes.
Voici donc le'exercice de Aldayo,et bravo à lui.

Les prochains résultats seront donc à lui faire parvenir .
Bonne semaine à tous et bon "ptitrain".