河内的塔

Question

我正在书中练习,要求我们使用递归方法解决河内塔问题.我已经找到了解决方案,但是在完成浏览互联网后我收集的内容是我的解决方案可能不正确.有谁知道更好/不同的方法来解决问题？有没有人有任何改进的建议.(顺便说一句,输出是正确的.它只能告诉从哪个塔到另一个桩正在移动,而不是具体是哪个钉子​​)

这是代码:

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

此方法是否合格为递归？

Answer 1

回答你的问题:是的,这是合格的递归.只要函数调用自身,它就是递归.

话虽如此,您的代码可以大幅减少:

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