tours linéaires de Hanoi

Question

J'ai une question sur les tours linéaires de Hanoi. Je l'ai implémenté en C++ mais j'essaie de faire la même chose en utilisant la méthode récursive de queue ou itérative. J'ai des problèmes avec mon algorithme.

Cet extrait de code montre le transfert de blocs de la tour centrale à la tour d'extrémité.

#include <stdlib.h> 
#include <stdio.h> 
using namespace std; 

//int a[5]={2,3,1,2,1}; 
int from,spare,to; 

int main() 
{ 
//int n; 

//void hanoi(int,int,int,int); 
void linear_hanoi(int,int,int,int); 
void mid_to_end(int,int,int,int); 
void end_to_mid(int,int,int,int); 
//mid_to_end(3,2,3,1); 
end_to_mid(4,3,2,1); 
getchar(); 
return 0; 
} 

void linear_hanoi(int n, int from, int to, int spare) 
{ 
    if(n>0) 
     { 
      linear_hanoi(n-1,from,to,spare); 
      cout<<"move ring "<<n<<" from tower "<<from<<" to tower "<<spare<<endl; 
      linear_hanoi(n-1,to,from,spare); 
      cout<<"move ring "<<n<<" from tower "<<spare<<" to tower "<<to<<endl; 
      linear_hanoi(n-1,from,to,spare); 
     } 
} 
void mid_to_end(int n, int from, int to, int spare) 
{ 
    if(n>0) 
    { 
    mid_to_end(n-1,from,spare,to); 
    cout<<"move ring "<<n<<" from tower "<<from<<" to tower "<<to<<endl; 
    // mid_to_end(n-1,spare,from,to); 
    // mid_to_end(n-1,from,to,spare); 
    //cout<<"move ring "<<n<<" from tower "<<spare<<" to tower "<<from<<endl; 
    // mid_to_end(n-1,from,to,spare); 
    //cout<<"move ring "<<n<<" from tower "<<spare<<" to tower "<<from<<endl; 
} 
} 

Qu'est-ce que je fais mal?

Answer 1

De wikipedia:

solution simple: La solution suivante est une solution simple pour le puzzle de jouet.

Alterne entre la plus petite pièce et une pièce non-plus petite. Lorsque vous déplacez la plus petite pièce, déplacez-la toujours dans la même direction (vers la droite si le nombre de pièces est pair, vers la gauche si le nombre de pièces est impair). S'il n'y a pas de tour dans la direction choisie, déplacez la pièce vers l'extrémité opposée, mais continuez ensuite à vous déplacer dans la bonne direction. Par exemple, si vous avez commencé avec trois pièces, vous déplacer le plus petit morceau à l'extrémité opposée, puis continuer dans la direction de gauche après cela. Lorsque le tour consiste à déplacer la pièce non-la plus petite, il n'y a qu'un seul mouvement légal. Faire cela devrait compléter le puzzle en utilisant le moins de mouvements pour le faire.

Answer 2

Vous pouvez transformer le code en style continuation-passing. Alors tout est récursif à la queue ...