使用遞歸求解河內拼圖

我目前正在創建一個程序，顯示解決河內拼圖的一舉一動。（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

使用遞歸求解河內拼圖

回答

相關問題