C++ 河内塔

Towers of Hanoi

提问by E.O.

I am working on an exercise in a book which asks us to solve the Towers of Hanoi problem using recursive methods. I have come to a solution, but from what I gather after browsing the Internet when done is that my solution may not be correct. Does anyone know a better/different way to solve the problem? And does anyone have nay suggestions for improvements. (Btw, the out put is correct. It is only supposed to tell from which tower to another pegs are moving, not specifically which pegs)

我正在做一本书的练习，要求我们使用递归方法解决河内塔问题。我已经找到了一个解决方案，但是从我完成后浏览 Internet 后收集到的信息来看，我的解决方案可能不正确。有谁知道解决问题的更好/不同的方法？有没有人有任何改进建议。（顺便说一句，输出是正确的。它只应该告诉从哪个塔到另一个钉子正在移动，而不是具体哪个钉子）

Here is the code:

这是代码：

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

Is this method qualified as recursion?

这种方法是否符合递归条件？

回答by riwalk

To answer your question: yes, that is qualified as recursion. Any time a function calls itself, it is recursion.

回答你的问题：是的，这被称为递归。任何时候函数调用自身，都是递归。

With that being said, your code can be trimmed down substantially:

话虽如此，您的代码可以大幅减少：

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

回答by Jerry Coffin

It's easiest if you look at the problem recursively:

如果您递归地查看问题，这是最简单的：

To move N discs from A to B (using C):

将 N 个光盘从 A 移动到 B（使用 C）：

1. if (N > 1) move N-1 discs from A to C (using B)
2. move one disc from A to B
3. if (N > 1) move N-1 discs from C to B (using A)

1. if (N > 1) 将 N-1 个圆盘从 A 移到 C（使用 B）
2. 将一张光盘从 A 移到 B
3. if (N > 1) 将 N-1 个圆盘从 C 移到 B（使用 A）

For any given call, whichever peg is notthe source or the destination is the ancillary.

对于任何给定的调用，不是源或目标的挂钩是辅助。

To answer your actual question: yes, your solution appears to be recursive, though a bit more complex than really necessary.

回答您的实际问题：是的，您的解决方案似乎是递归的，尽管比实际需要的要复杂一些。

回答by Nick

Every recursion method has 3 steps

每个递归方法都有 3 个步骤

1) A check condition 2) Return value when check condition is satisfied. 3) A call to method itself

1) 检查条件 2) 满足检查条件时返回值。3) 对方法本身的调用

@Stargazer712 solution is perfect.

@ Stargazer712 解决方案是完美的。

回答by Umair A R Mughal

#include <iostream>

using namespace std;

void towers(int, char, char, char);

void towers(int num, char frompeg, char topeg, char auxpeg)
{
    if (num == 1)
    {

        cout<<"\n Move disk 1 from peg "<<frompeg<<" to peg "<<topeg<<endl;

        return;
    }

    towers(num - 1, frompeg, auxpeg, topeg);

    cout<<"\n Move disk "<<num<<" from peg "<<frompeg<<" to peg "   <<topeg<<endl;

    towers(num - 1, auxpeg, topeg, frompeg);
}

int main()
{
    int num;

    cout<<"Enter the number of disks : ";

    cin>>num;

    cout<<"The sequence of moves involved in the Tower of Hanoi are :\n"<<endl;

    towers(num, 'A', 'C', 'B');

    return 0;
}

回答by isaac kargar

Here is a recursive solution for tower of hanoi.

这是河内塔的递归解决方案。

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

void move(vector<int>& frompeg, vector<int>& topeg) {
    topeg.push_back(frompeg.back());
    frompeg.pop_back();
}

void hanoi(vector<int>& frompeg, vector<int>& topeg, vector<int>& auxpeg, 
int num_disks) {
    if (num_disks == 1) {
        move(frompeg, topeg);
    }
    else {
        hanoi(frompeg, auxpeg, topeg, num_disks - 1);
        move(frompeg, topeg);
        hanoi(auxpeg, topeg, frompeg, num_disks - 1);
    }
}

void printpeg(vector<int> a, vector<int> b, vector<int> c) {
    cout << "a: ";
    for (int i = 0; i < a.size(); i++) {
        cout << a[i] << " ";
    }
    cout << "\n";
    cout << "b: ";
    for (int i = 0; i < b.size(); i++) {
        cout << b[i] << " ";
    }
    cout << "\n";
    cout << "c: ";
    for (int i = 0; i < c.size(); i++) {
        cout << c[i] << " ";
    }

}

int main() {

    int n;
    cin >> n;
    vector<int> a,b,c;
    for (int i = 0; i < n; i++) {
        a.push_back(n - i);
    }
    cout << "befor: " << endl;
    printpeg(a, b, c);
    hanoi(a, b, c, n);
    cout << "after: " << endl;
    printpeg(a, b, c);
    cin.get();
    cin.get();
    return 0;
    }