汉诺塔问题--迭代版本

接着讨论之前的问题汉诺塔问题–递归版，也可以用迭代实现，考虑用三个栈代表三根柱子，出栈入栈代表了碟子的离开柱子和到达柱子的过程。
考虑碟子移动的过程：

1. 由于要最小化移动次数，因此不会出现两次相临的移动都发生在同一对柱子间。因此当左中柱子间发生碟子移动时，下一次移动必发生在中间和右边；
2. 对于一对柱子（左中，中右），要判断哪个出栈哪个入栈很简单，若其中一个为空，则此栈将另一个出栈的元素入栈。若都不为空，则栈顶元素小的出栈，入栈到栈顶元素大的那边。

可以用一个标志量记录哪对柱子该发生移动。

#include<iostream>
#include<string>
#include<stack>
#include<vector>
using std::string;
using std::cin;
using std::cout;
using std::stack;
using std::vector;
using std::endl;
//移动过程打印函数
void print(int num, string from, string to) {
    cout << "Move " << num << " from " << from << " to " << to << endl;
}

int main()
{
    //左中右三个栈
    stack<int> l, m, r;
    int num;
    输入碟子数量
    cin >> num;
    //初始化，将所有碟子依次放入左边的栈
    for (int i = 0; i < num; i++)
        l.push(num - i);
    //flag为false表示左边和中间之间有过移动，中间和右边之间没有过移动
    //第一次移动定发生在左边和中间，故flag初始化为true
    bool flag = true;
    //记录移动次数
    int sum = 0;
    while (r.size() < num) {
    //若左边和中间该发生碟子移动
        if (flag)
        {
        //中间栈为空，或左边栈顶小于中间栈顶时，左边出栈
            if (m.empty() || (!l.empty() && l.top() < m.top())) {
                m.push(l.top());
                l.pop();
                print(m.top(), "L", "M");
            }
            else {
                l.push(m.top());
                m.pop();
                print(l.top(), "M", "L");
            }
            flag = false;
        }
        else {
            if (r.empty() || (!r.empty() && m.top() < r.top())) {
                r.push(m.top());
                m.pop();
                print(r.top(), "M", "R");
            }
            else {
                m.push(r.top());
                r.pop();
                print(m.top(), "R", "M");
            }
            flag = true;
        }
        sum++;
    }
    cout << "total number of movement is " << sum << endl;
    return 0;
}

运行结果

相比递归版本，迭代版本更简洁，也更容易理解