Tours de Hanoi mais avec configuration initiale et finale arbitraire

11

Récemment, je suis tombé sur ce problème , une variante des tours de hanoi .

Énoncé du problème:

Considérez la variation suivante du problème bien connu des tours de Hanoi:

On nous donne tours et m disques de tailles 1 , 2 , 3 , , m empilés sur certaines tours. Votre objectif est de transférer tous les disques vers la k ème tour en aussi peu de mouvements que vous pouvez gérer, mais en tenant compte des règles suivantes:n1,2,3,,mkth

  • déplacer un seul disque à la fois,
  • ne jamais déplacer un disque plus gros sur un plus petit,
  • se déplaçant uniquement entre les tours à distance au plus .d

(Limites dans le problème d'origine: et m 100. Nombre de cas de test 1000. Vous pouvez supposer que tous les problèmes peuvent être résolus en pas plus de 20000 mouvements.)3n1000m100100020000

C'est intéressant. Le problème des tours classiques de hanoi a une source, une destination et une tour temporaire qui sont utilisées pour déplacer les disques de la source à la destination. Le problème posé sur ce site a essentiellement une configuration initiale et finale.

Comment aborder ce problème?

Nul
la source
4
Pourriez-vous écrire le problème dans la question, de sorte que la question soit indépendante du lien?
Luke Mathieson
2
Et qu'avez-vous essayé? Connaissez-vous les solutions aux problèmes d'origine et avez-vous essayé de les adapter?
Raphael
3
>5001000
Si vous oubliez la restriction de la distance au plus d, alors cela me semble identique au casse-tête de Reve qui a la solution d'algorithme Frame-Stewart non prouvée décrite dans cette page wiki . Intuitivement, l'ajout de cette restriction rend les choses encore plus compliquées.
Ciro Santilli 冠状 病毒 审查 六四 事件 法轮功

Réponses: