河内问题的塔 [英] Towers of Hanoi question

问题描述

我阅读了关于河内问题的几个讨论。我理解递归解决方案使用以下代码：

I read through a few of the discussions about the Towers of Hanoi problem. I understand the recursive solution using the following code:

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

我真正需要做的是输出一些类型插图的塔在每一步。我有很多麻烦完成这个。我们的教师建议使用堆栈跟踪什么磁盘在什么塔上，但我有麻烦输出，因为查找和输出堆栈中的值需要弹出顶部条目并删除它们。他们失去了，如果我理解它正确。

What I actually need to do is output some type of "illustration" of the towers at each step. I'm having a lot of trouble accomplishing this. Our instructor suggested using stacks to keep track of what disk is on what tower, but I'm having trouble outputting this as finding and outputting the values in the stacks requires popping off the top entries and deleting them. They become lost, if I understand it correctly.

无论如何，它让我得到一些解决方案，从这样开始：

Either way, it led me to some solution that starts off like this:

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

我知道这是错误的。我不知道在哪里一个好地方将用磁盘号填充源。我每次传递相同大小的源栈。如果有人可以给我一些方向或任何东西，这将是真的很酷。谢谢。

I'm well aware that this is wrong. I'm not sure where a good place would be to populate source with the disk numbers. And I'm passing down the same size source stack each time. If someone could give me some direction or anything, that would be really cool. Thank you.

推荐答案

传递对堆栈的引用：

stack<int>&

还要考虑使用向量而不是堆栈，所以你可以迭代它来查看当前的内容

Also consider using a vector rather than a stack so you can iterate it to see the current content of the towers.

PigBen的回答也正确地识别了您的代码中的一个错误，您不会将磁盘从中间塔移动到目标塔。

PigBen's answer also correctly identifies a bug in your code where you're not moving the disks from the intermediate tower to the destination tower.

这篇关于河内问题的塔的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！