линейные башни из hanoi

Question

У меня вопрос о линейных башнях Ханоя.

Я реализовал его на C++, но стараюсь сделать то же самое с помощью рекурсивного или итеративного метода. У меня проблемы с моим алгоритмом.

Этот фрагмент кода показывает перенос блоков со средней башни на торцевую башню.

#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; 
} 
} 

Что я делаю неправильно?

Answer 1

Из википедии:

Простое решение: Следующее решение является простым решением для игрушек головоломки.

Альтернативные ходы между наименьшей частью и наименьшей частью. При перемещении самого маленького куска всегда перемещайте его в том же направлении (вправо, если начальное количество штук четное, влево, если начальное количество кусков нечетно). Если в выбранном направлении нет башни, переместите кусок на противоположный конец, а затем продолжайте движение в правильном направлении. Например, если вы начали с трех частей, вы переместили бы наименьшую часть на противоположный конец, а затем продолжите в левом направлении после этого. Когда поворот должен переместить не самую маленькую часть, есть только один законный ход. Для этого нужно завершить головоломку, используя меньшее количество шагов для этого.

Answer 2

Вы можете преобразовать код в режим продолжения прохождения. Тогда все хвост-рекурсивный ...