Линейные башни Ханоя

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

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