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); 
    }
}

我真正需要做的是在每一步输出某种类型的塔的“插图”。我很难做到这一点。我们的讲师建议使用堆栈来跟踪哪个磁盘在哪个塔上，但是我在输出这个时遇到了麻烦，因为在堆栈中查找和输出值需要弹出顶部条目并删除它们。如果我理解正确，他们会迷路。

无论哪种方式，它都让我找到了一些这样开始的解决方案：

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;
}

我很清楚这是错误的。我不确定用磁盘号填充源的好地方在哪里。而且我每次都传递相同大小的源堆栈。如果有人能给我一些方向或任何东西，那就太酷了。谢谢你。

4

3 回答 3

3

传递对堆栈的引用：

stack<int>&

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

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

于 2010-12-19T02:24:38.777 回答
1

通过引用传递堆栈，并更改您在最后一步中传递它们的顺序，以便您从 intermed 移动到 dest，使用 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, intermed, source, dest); 
    }
}

要显示堆栈，只需复制它并从副本中弹出。

于 2010-12-19T02:35:18.547 回答
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); 
    }
}

这是不正确的，所以这可能是你的老师建议展示塔的原因。

正如您所注意到的，astd::stack是一个很好的容器，可用于表示塔的当前磁盘，但您也注意到，在std::stack不弹出它们的情况下获取 a 的元素并不完全简单。您可以将它们弹出并将它们向下推到另一个堆栈上，然后将它们移回，但这既复杂又愚蠢，更不用说对于一般情况而言效率低下。这就是为什么std::stack有一个protectedmember 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;
    }
}

请注意，此代码仅说明了如何访问这些堆栈的元素。

显示可以做得更花哨，例如图形。

我建议你让你的求解器函数成为 class 的成员Hanoi。并添加成员函数来显示拼图状态。稍后您可能希望将其转换为回调，以支持图形用户界面。

编辑：嗯，我看到另一个答案显示了该错误的“解决方案”。这消除了 OP 的学习经验和展示塔的全部原因。这个答案故意只是确认了这个错误是真实的，而是显示了 OP 的要求，即如何有效地显示堆栈。

干杯&hth.，

于 2010-12-19T03:08:21.950 回答