河内的线性塔

我对河内的线性塔有疑问。河内的线性塔

我在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; 
} 
}

我在做什么错？

来源

2009-10-20 user181266

这功课吗？ – jprete 2009-10-20 17:49:32

即使不是，这是某人的作业;标记为这样。 – 2009-10-20 17:50:42

nope我应该写一篇研究论文。比较递归和尾递归 – user181266 2009-10-20 17:52:37

维基百科：

简单的解决方案：下面的解决方案是为玩具拼图一个简单的解决方案。

在最小片和非最小片之间交替移动。移动最小的部分时，请始终将其沿同一方向移动（如果起始数量为偶数，则向右移动，如果起始数量为奇数，则向左移动）。如果在所选方向上没有塔，请将该部分移动到另一端，但继续沿正确的方向移动。例如，如果您从三部分开始，则会将最小的部分移动到另一端，然后在此之后继续向左移动。当轮到移动非最小的棋子时，只有一个合法的举动。这样做应该用最少的动作来完成这个难题。

来源

2009-10-20 21:35:59

thanx老兄，我想我现在可以工作了 – user181266 2009-10-20 22:13:38

您可以将代码转换为continuation-passing-style。然后一切都是尾递归的...

来源

2009-11-27 20:50:39

河内的线性塔

回答

相关问题