c++ - 汉诺塔问题

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>&

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

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