Alors j'ai fait le hanoï classique celui avec les 3 colonnes et alors je me suis dit que je vais essayer de le faire avec plus de colonnes mais c'est pas évident du tout c'est plus compliqué que ce que je croyais au départ. Alors du coup je me suis dit que je vais déjà commencer avec 1 colonne de plus ce qui fait 4 au lieu de 3 et déjà la ça se complique parce que je sais pas du tout comment commencer. Si j'essaye de faire pareil que 3, je fais quoi ? un choix avec les 2 qui me restent ? alors comment je fais ce choix ?
Tout ça manque de précision... J'ai compris tour de Hanoï et 4 positions. Pour le reste, ce n'est pas clair. Tu fais quoi exactement, un jeu auquel tu proposes de jouer ? Un programme qui résout ce problème ?
Selon moi, rendre le jeu plus difficile consiste à ajouter des disques, pas des positions. Disons que 3 disques et 3 positions est un problème à résoudre, 3 disques et 4 positions, plus vraiment.
Montre nous au moins le code que tu as jusque là et précise nous tes intentions.
j'ai pas de code car je sais pas par où commencer. le hanoï classique se joue avec n disques et C=3 colonnes. Mois j'ai C=4 colonnes. Je cherche à aller d'une colonne de départ à une colonne d'arrivée fixées en utilisant 2 colonnes vides au lieu de 1 seul. Alors j'essaye de le faire mais avec le moins de coup possible. J'arrive pas à savoir comment faire. Alors je sais que je peux faire comme si y avait que 3 colonnes en oubliant 1, mais on doit pouvoir faire moins de coup si on a plus de colonnes non ? genre si tu as n disques et n+1 colonnes c'est tout simple tu mets un disque par colonne et tu remets tout sur l'arrivé.
bon, comme je le dis toujours, google est ton ami, chercher un peu sur le net n'a jamais nuit, etc. Ça c'est vraiment l'idée de base : je tâtonne un peu, je vais chercher sur le net, je retâtonne, … au bout d'un moment si je ne comprends pas alors je vais sur un forum pour poser une question précise, quoique un forum c'est ptêt pas la meilleure des solutions mais passons.
Donc si tu te donnes un peu de mal tu tombes assez rapidement sur une tonne de données bibliographiques (évidemment il faut non seulement chercher mais lire et comprendre aussi), d'autant plus que Hanoï est un sujet hyper classique (et encore hyper c'est peu dire).
Bon tu te restreins au cas des 4 tours. Et c'est en cherchant sur le net que j'ai appris avec étonnement que ce problème n'avait été résolu qu'il y a très peu de temps (2014, T. Bousch). Que pour le cas général n>4 on a bien quelques pistes, un algorithme qui fonctionne pas trop mal : l'algorithme de Frame-Stewart, mais que pour l'instant on n'a rien prouvé quant à l'optimalité des solutions trouvées.
Tu t'attaques donc là à un problème pas piqué des hannetons !
Un très bonne source est une vidéo de Mathologer → The ultimate algorithm. Tu trouveras dans la description de la vidéo toute une bibliographie complète …
Bon courage et surtout : n'oublie pas que tu as le net à ta disposition.
je sais manipuler les disques je me casse la tête dessus. tu me montre une solution en 10 coups alors qu'il y en a en moins et j'ai toujours pas d'idées pour commencer un algo avec ça. alors tu veux que je te montre quoi ?
> tu me montre une solution en 10 coups alors qu'il y en a en moins
> j'ai toujours pas d'idées pour commencer un algo
1. Montre nous ta solution en moins de 10 coups.
2. Essaie d'expliquer comment tu l'as trouvée,
3. et comment tu pourrais la généraliser à 5, à 6 etc.
Raisonnement pour compter le nombre minimum de coups :
- pour déplacer les 4 disques, il y a un moment où il a fallu bouger le disque 4. - a ce moment là, le 4 etait tout seul sur sa pile d'origine, et la destination était vide
- donc les disques 1,2,3 étaient regroupé sur les deux autres piles.
- donc il a fallu déplacer le 3, et pour ça poser ailleurs le 1 et le 2
- il y a donc forcément eu un moment où on a eu une pile vide, une pile avec 1 et 2, une pile avec 3, une pile avec 4.
- la pile avec 1 et 2, il a fallu trois coups, forcément
-etc.
Donc 3 coups pour faire la petite pile avec 1et2,
2 coups pour dégager le 3 et amener le 4 à destination,
un coup pour amener le 3 sur le 4,
et 3 coups pour amener le 1 et le 2
Ca fait neuf (en fait j'ai une situation en double sur le dessin)
Raisonnement pour compter le nombre minimum de coups :
- pour déplacer les 4, il y a un moment où il a fallu bouger le disque 4. - a ce moment là, le 4 etait tout seul sur sa pile d'origine, et la destination était vide
- donc les disques 1,2,3 étaient regroupé sur les deux autres piles.
- donc il a fallu deplacer le 3, et pour ça poser ailleurs le 1 et le 2
- il y a donc forcément eu un moment où on a eu une pile vide, une pile avec 1 et 2, une pile avec 3, une pile avec 4.
-etc.
- Edité par michelbillaud il y a 2 minutes
Je pense que tu vas un peu vite en besogne Michel. Apparemment personne n'a prouvé que ce raisonnement donne le minimum de coups pour n>4, et la démo pour n=4 est pour le moins compliquée. C'est surtout ta partie «donc les disques 1,2,3 étaient regroupé sur les deux autres piles.» qui, très simple pour le cas n=3 puisque tous les disques sont sur une tour, qui complexifie la chose dès qu'on a n>3. Mais l'idée est là pour l'algo Frame-Stewart.
non non j'ai pas dit que c'était une solution minimum.
Et j'ai exagéré en disant qu'il y avait forcément un passage avec une pile qui contient 1 et 2.
En fait je réexploitais l'idée de base de l'algo classique de la tour de hanoi (l'idée que personne ne voit puisque tout le monde part de l'idée récursive déjà trouvé dans wikipedia, comme pour le tri à bulles) : A un moment, il faut bouger le gros disque, et pour ça il faut avoir dégagé ce qui est au dessus de lui, et la destination. Plus : une fois que c'est fait, on peut faire de même pour le 2ieme disque en taille, etc.
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
Bonhomme !! | Jeu de plateforme : Prototype.