我正在做一本书中的练习,要求我们使用递归方法解决汉诺塔问题。我已经找到了解决方案,但从我浏览互联网后收集到的信息来看,我的解决方案可能不正确。有谁知道更好/不同的方法来解决问题?是否有人有任何改进建议。 (顺便说一句,输出是正确的。它只是应该告诉从哪个塔到另一个钉子正在移动,而不是具体告诉哪些钉子)
这是代码:
#include <iostream>
#include <cmath>
using namespace std;
static int counter = 0;
void ToH(int dskToMv, int cLocation, int tmpLocation, int fLocation)
{
if (dskToMv == 0);
else
{
if (dskToMv%2!=0)
{
cout << cLocation << "->" << tmpLocation << endl;
cout << cLocation << "->" << fLocation << endl;
cout << tmpLocation << "->" << fLocation << endl;
ToH(dskToMv-1, cLocation, fLocation, tmpLocation);
}
else if (dskToMv%2==0)
{
counter++;
if (counter%2==0)
cout << fLocation << "->" << cLocation << endl;
else
cout << cLocation << "->" << fLocation << endl;
ToH(dskToMv-1, tmpLocation, cLocation, fLocation);
}
}
}
int main()
{
int x, j;
cout << "Enter number of disks: ";
cin >> x;
j = pow(2.0, x-1)-1;
if (x%2==0)
ToH(j, 1, 2, 3);
else
ToH(j, 1, 3, 2);
return 0;
}
这个方法是否符合递归的条件?
最佳答案
回答你的问题:是的,这符合递归的条件。任何时候函数调用自身都是递归。
话虽这么说,您的代码可以大大减少:
#include <iostream>
using namespace std;
void ToH(int dskToMv, int cLocation, int tmpLocation, int fLocation)
{
if( dskToMv != 0 )
{
ToH( dskToMv-1, cLocation, fLocation, tmpLocation );
cout << cLocation << "->" << fLocation << endl;
ToH( dskToMv-1, tmpLocation, cLocation, fLocation );
}
}
int main()
{
int x;
cout << "Enter number of disks: ";
cin >> x;
ToH(x, 1, 2, 3);
return 0;
}
关于c++ - 汉诺塔,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/6739362/