河內問題塔

Question

我通讀了一些關於河內塔問題的討論。我使用下面的代碼瞭解遞歸解決方案：

void Hanoi3(int nDisks, char source, char intermed, char dest) 
{ 
    if(nDisks == 1){ 
     cout << "Move the plate from " << source << " to " << dest << endl; 
    } 
    else{ 
     Hanoi3(nDisks - 1, source, dest, intermed); 
     cout << "Move the plate from " << source << " to " << dest << endl; 
     Hanoi3(nDisks - 1, dest, intermed, source); 
    } 
} 

我真正需要做的是輸出某種類型的每一步塔的「插圖」的。完成這件事我有很多麻煩。我們的教師建議使用堆棧來跟蹤磁盤在哪個塔上，但是我無法輸出，因爲查找並輸出堆棧中的值需要彈出頂部條目並將其刪除。如果我理解正確，他們會迷失方向。

無論哪種方式，它使我的一些解決方案，開始了這樣的：

void Hanoi(int nDisks, stack<int> source, stack<int> intermed, stack<int> dest){ 
    if(nDisks == 1){ 
     dest.push(source.top()); 
     source.pop(); 
    } 
    else{ 
     Hanoi(nDisks - 1, source, dest, intermed); 
     dest.push(source.top()); 
     source.pop(); 
     Hanoi(nDisks - 1, dest, intermed, source); 
    } 
} 

int main() 
{ 

    int nDisks; 
    cout << "Enter the number of disks: "; 
    cin >> nDisks; 

    stack<int> source, intermed, dest; 

    for(int i = nDisks; i >= 1; i--){ 
     source.push(i); 
    } 

    Hanoi(nDisks, source, intermed, dest); 

    return 0; 
} 

我很清楚地知道，這是錯誤的。我不確定一個好的地方是用磁盤編號填充源代碼的地方。而且我每次都會傳遞相同大小的源代碼堆棧。如果有人可以給我一些方向或任何東西，這將是非常酷的。謝謝。

Answer 1

傳遞一個參考堆棧：

stack<int>& 

也可以考慮使用載體，而不是堆棧，所以你可以遍歷它看到塔的當前內容。

PigBen的回答也正確地識別了您的代碼中的一個錯誤，您沒有將磁盤從中間塔移動到目標塔。

Answer 2

通過引用傳遞堆棧，並在最後一個步驟中更改您傳遞它們的順序，以便將源代碼作爲中間源從intermed移動到dest。

void Hanoi(int nDisks, stack<int> &source, stack<int> &intermed, stack<int> &dest){ 
    if(nDisks == 1){ 
     dest.push(source.top()); 
     source.pop(); 
    } 
    else{ 
     Hanoi(nDisks - 1, source, dest, intermed); 
     dest.push(source.top()); 
     source.pop(); 
     Hanoi(nDisks - 1, intermed, source, dest); 
    } 
} 

要顯示堆棧，只需複製它並從副本中彈出即可。

Answer 3

考慮您的原始代碼：

void Hanoi3(int nDisks, char source, char intermed, char dest) 
{ 
    if(nDisks == 1){ 
     cout << "Move the plate from " << source << " to " << dest << endl; 
    } 
    else{ 
     Hanoi3(nDisks - 1, source, dest, intermed); 
     cout << "Move the plate from " << source << " to " << dest << endl; 
     Hanoi3(nDisks - 1, dest, intermed, source); 
    } 
} 

這是不正確的，所以這就是爲什麼有可能你的老師建議提出塔。

正如您所看到的，std::stack是一個很好的容器，可用來表示塔的當前磁盤，但正如您還注意到，在不彈出它們的情況下獲取std::stack的元素並不是完全簡單。你可以彈出它們並將它們壓在另一個堆棧上，然後將它們移回去，但這是複雜而愚蠢的，更不用說一般情況下效率低下了。這就是爲什麼std::stack有一個protected成員c，它是基礎容器，可以通過派生類訪問。

std::stack中沒有虛擬成員，因此擁有protected成員的唯一目的是使其稍微難以理解。我認爲這是一個糟糕的設計決定。但它是你所擁有的，所以，

#include <iostream> 
#include <string> 
#include <stack> 
#include <stddef.h> 
using namespace std; 

typedef ptrdiff_t Size; 
typedef Size  Index; 

class IntStack 
    : public stack<int> 
{ 
public: 
    Size count() const { return size(); } 
    int at(Index i) const { return c[i]; } 
}; 

class Hanoi 
{ 
private: 
    IntStack towers_[3]; 
    int   nDisks_; 

public: 
    Hanoi(int nDisks) 
     : nDisks_(nDisks) 
    { 
     for(int disk = nDisks; disk >= 1; --disk) 
     { 
      towers_[0].push(disk); 
     } 
    } 

    IntStack const& towers(Index i) const { return towers_[i]; } 
}; 

int main() 
{ 
    int const nDisksTotal = 2; 

    Hanoi puzzle(nDisksTotal); 

    for(Index i = 0; i < 3; ++i) 
    { 
     IntStack const& tower = puzzle.towers(i); 
     Size const  nDisks = tower.count(); 

     cout << "Tower " << i << ": ";   
     for(Index diskPos = 0; diskPos < nDisks; ++diskPos) 
     { 
      if(diskPos > 0) { cout << ", "; } 
      cout << tower.at(diskPos); 
     } 
     cout << endl; 
    } 
} 

請注意，此代碼只說明如何訪問這些堆棧的元素。

該顯示器可以做得更漂亮，例如，圖形。

我建議你讓你的解算器功能成爲Hanoi的成員。並添加一個成員函數來顯示拼圖狀態。稍後，您可能希望將其轉換爲回調，以支持圖形用戶界面。

編輯：嗯，我看到另一個答案顯示了「解決方案」的錯誤。這消除了OP的學習經歷和展示塔的全部原因。這個答案故意只確認這個錯誤是真實的，並且顯示出OP所要求的內容，即如何有效地顯示堆棧。

乾杯&心連心，