递归方法

思路

1. 终止条件

当只剩最上层塔需要移动时，需要考虑两种情况：

• 从中间塔来，或者去中间塔，这时只需一步;
• 从左到右或者从右到左,分两步;

2. 多层塔情况

不止一层塔需要移动，通过递归实现上面塔先移开，也是需要考虑上述两种情况。

• 当起点或终点为mid。需要先把上面塔从from移动到另一边another。待最后一层塔从from到to后，再把上面塔从another移动到to。
• 起点或终点不为mid。需要经过mid。

代码

#include<iostream>
using namespace std;
void moveTo(int n, string& from, string& to) {
    cout << "Move " << n << " from " << from << " to " << to << endl;
}

// 返回所需的步数
int process(int n, string& left, string& mid, string& right, string& from,
            string& to) {
    // 最上层塔需要移动时
    if (n == 1) {
        // 从中间塔来，或者去中间塔
        if (from == mid || to == mid) {
            moveTo(n, from, to);
            //这一步步数为1
            return 1;
        } else {
            // 从左到右或者从右到左,分两步
            // 这两步也保证了下面的递归函数可以直接写from到to,而无需先from到mid,再到to.
            moveTo(n, from, mid);
            moveTo(n, mid, to);
            return 2;
        }
    } else {
        // 不止一层塔需要移动，通过递归实现上面塔先移开
        // 起点或终点为mid
        if (from == mid || to == mid) {
            //先把上面塔从from移动到另一边another
            string another = (from == left || to == left) ? right : left;
            int part1 = process(n - 1, left, mid, right, from, another);

            // 由于是移动到中间塔或者从中间塔移动到两边，所以步数为1
            int part2 = 1;
            moveTo(n, from, to);

            // 再把上面塔从another移动到to
            int part3 = process(n - 1, left, mid, right, another, to);

            // 返回上面三步的总步数
            return part1 + part2 + part3;
        } else {
            // 起点或终点不为mid

            // 1. 将上面塔从from移动到to
            int part1 = process(n - 1, left, mid, right, from, to);

            // 2. 将第n层塔从from移动到mid
            moveTo(n, from, mid);
            int part2 = 1;

            // 3. 将上面塔从to移动到from
            int part3 = process(n - 1, left, mid, right, to, from);

            // 4. 将第n层塔从mid移动到to
            moveTo(n, mid, to);
            int part4 = 1;

            // 5. 将上面塔从from移动到to
            int part5 = process(n - 1, left, mid, right, from, to);

            return part1 + part2 + part3 + part4 + part5;
        }
    }
}

// 返回最优总步数
int hanoi(int n, string& left, string& mid, string& right) {
    if (n < 1) {
        return 0;
    }
    return process(n, left, mid, right, left, right);
}

int main() {
    int N;
    cin >> N;
    string left = "left", mid = "mid", right = "right";
    int allStep = hanoi(N, left, mid, right);
    cout << "It will move " << allStep << " steps." << endl;
}