使用递归求解河内拼图

我目前正在创建一个程序，显示解决河内拼图的一举一动。（A，A，A），我需要显示每张光盘从开始位置开始的每次移动的位置。 A =第一个挂钩，B =第二个挂钩，C =第三个挂钩。我有程序输出的动作，但不是位置。我如何在程序中实施职位？这里是我的代码到目前为止我的输出和一个图表显示每次移动后的位置。盘数是一个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; 
}

来源

2017-08-02 Quinton Thompson

我怀疑这可以做到没有重要的代码添加。递归解决方案是，在解决方案的每个级别，该功能都认为自己正在解决一个完整的问题。因此，递归调用表示的子问题不能意识到整体问题，也无法按照所描述的方式跟踪光盘。 – shians

请看看我的解决方案 –

下面是一个跟踪每次移动的解决方案，每个钉位置我使用STL ::地图PEG A有3,2,1挂钩B，空的，挂钩C，空的（要移动的地方必须完成）

现在的解决方案是基于约束条件可以基于约束条件更新来更新

#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甲见（1 :: 3 => 2 => 1）被移动到栓C（3 :: 3 => 2 => 1）

来源

2017-08-02 03:22:39

使用递归求解河内拼图

回答

相关问题