河内塔问题

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

考虑一下你的原始代码：

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 的元素并不完全简单::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所要求的内容，即如何有效地显示堆栈。

干杯&呵呵，

Answer 2

通过引用传递堆栈，并更改在最后一步中传递堆栈的顺序，以便使用 source 作为中间，从 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

传递对堆栈的引用：

stack<int>&

还可以考虑使用向量而不是堆栈，以便您可以迭代它以查看塔的当前内容。

PigBen 的答案还正确地识别了代码中的一个错误，即您没有将磁盘从中间塔移动到目标塔。