c++ - 使用递归解决河内难题

Question

我目前正在创建一个程序，显示解决河内难题的每一步。我需要显示每个圆盘的位置，从开始位置开始(A，A，A)。 A = 第一个 Hook ，B = 第二个 Hook ，C = 第三个 Hook 。我有程序输出 Action 而不是位置。我如何将职位落实到计划中？到目前为止，这是我的代码以及我的输出和显示每次移动后位置应该是什么的图表。圆盘数是 const 3。

#include <iostream>
using namespace std;

void moveDiscs(int num,int fromPeg,int toPeg, int tempPeg){;
char position;
    if(num > 0){
        moveDiscs(num-1,fromPeg,tempPeg,toPeg);
        cout << "Move a disc from peg "<<fromPeg<<" to peg "<<toPeg<<endl;
        moveDiscs(num-1,tempPeg,toPeg,fromPeg);
    }
}
int main() {
    const int from_peg = 1;
    const int to_peg = 3;
    const int temp_peg = 2;

    moveDiscs(3,from_peg,to_peg,temp_peg);
    return 0;
}

Answer 1

下面是跟踪每个移动和每个钉子位置的解决方案我正在使用 STL::map peg A 有 3,2,1 peg B，empty，peg C，empty(移动必须完成的地方。

目前的解决方案是基于约束的，可以根据约束的变化进行更新

#include <iostream>
#include <map>
#include <deque>
using namespace std;

map<int,deque<int>> bucket;
deque<int> A{3,2,1};
deque<int> B;
deque<int> C;



void moveDiscs(int num,int fromPeg,int toPeg, int tempPeg){;
    if(num > 0){
        moveDiscs(num-1,fromPeg,tempPeg,toPeg);
        cout << "Move a disc from peg "<<fromPeg<<" to peg "<<toPeg<<endl;
        auto val = bucket[fromPeg].front();
        bucket[fromPeg].pop_front();
        bucket[toPeg].push_front(val);
        for (auto it:bucket)
        {
            cout << it.first << "::";
            for (auto di = it.second.begin(); di != it.second.end(); di++)
            {
                cout << "=>" << *di;
            }
            cout << endl;
        }

        moveDiscs(num-1,tempPeg,toPeg,fromPeg);
    }
}
int main() {

    bucket[1] = A;
    bucket [2] =B;
    bucket[3] = C;
    const int from_peg = 1;
    const int to_peg = 3;
    const int temp_peg = 2;

    moveDiscs(3,from_peg,to_peg,temp_peg);
    return 0;
}

输出

Move a disc from peg 1 to peg 3
1::=>2=>1
2::
3::=>3
Move a disc from peg 1 to peg 2
1::=>1
2::=>2
3::=>3
Move a disc from peg 3 to peg 2
1::=>1
2::=>3=>2
3::
Move a disc from peg 1 to peg 3
1::
2::=>3=>2
3::=>1
Move a disc from peg 2 to peg 1
1::=>3
2::=>2
3::=>1
Move a disc from peg 2 to peg 3
1::=>3
2::
3::=>2=>1
Move a disc from peg 1 to peg 3
1::
2::
3::=>3=>2=>1
Program ended with exit code: 0

所以你可以看到 Peg A (1::3=>2=>1) 被移动到 Peg C(3::3=>2=>1)