一、汉诺塔问题

解法一:递归

汉诺塔问题的解决方案可以分为3步：
1、把n-1个盘子从left 借助 right，搬到mid柱子上；
2、把剩下最大的那一个盘子从left搬到right柱子上；
3、把n-1个盘子从mid 借助 left，搬到right柱子上。
至于如何把n-1个盘子搬到另一个柱子上，同样参照上面的3步，不过此时柱子扮演的left，mid，right角色已经改变；对于n-2，n-3等等以此类推。

class Solution {
public:
    vector<string> solution;

    void Hanoi(int n, string left, string mid, string right){
        if (n==0) return;
        Hanoi(n-1,left,right,mid);//把n-1个盘子从left借助right搬到mid上去。
        solution.push_back("move from " + left + " to " + right);//把第n个盘子从left搬到right上。
        Hanoi(n-1,mid,left,right);//把n-1个盘子从mid借助left搬到right上去。
    }

    vector<string> getSolution(int n) {
        Hanoi(n, "left", "mid", "right");
        return solution;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

时间复杂度：O(2^N)。假设把n个盘子搬动耗时T(n)，则有T(n)=2T(n-1)+1，从而[T(n)+1]/[T(n-1)+1]=2，对该等比数列求解即可。
空间复杂度：O(N)。递归栈的深度。

解法二:非递归

1、将当前柱子顶部的盘子1移动到顺时针的下一个柱子。
2、将当前柱子和剩余的另一根柱子比较，将其中的一根柱子的盘子移动到另一根柱子上（很显然，这种移动方式是固定的）
3、指针指向顺时针的下一根柱子。
4、遇到某一根柱子的盘子满了时，停止循环；否则回到步骤1。
注意点在于当n为奇数时，顺时针的柱子顺序为left,right,mid；当n为偶数时，顺时针的柱子顺序为left,mid,right。

class Solution {
public:
    vector<string> solution;
    typedef struct
    {
        string name;
        vector<int> stack;
    }stack;

    void initStack(stack &a, stack &b, stack &c, int n)
    {
        for (int i = n; i >= 1; -- i){
            a.stack.push_back(i);
        }
        a.name = "left";
        if (n % 2 == 1){
            b.name = "right";
            c.name = "mid";
        }
        else{
            b.name = "mid";
            c.name = "right";
        }
    }

    void move(stack &a, stack &b)        // 将a中的栈顶元素移入b中 
    {
        solution.push_back("move from " + a.name + " to "+b.name);
        b.stack.push_back(a.stack.back());
        a.stack.pop_back();
    }

    void moveOneToOne(stack &a, stack &b)    // 算法的第二步就是对于输入的两个栈，将其中一个栈的栈顶元素移到另一个栈中 
    {
        // 任意两个不全为空的柱子的单次盘子移动方法是固定的
        if (a.stack.empty()){    // a如果空的，自然只能把b的元素移到a中
            move(b, a);
        } 
        else if (b.stack.empty()){    // b如果空的，自然只能把a的元素移到b中
            move(a, b);
        }
        else if (a.stack.back() > b.stack.back()){ // a的栈顶元素如果大于b的，自然只能把b的元素移到a中
            move(b, a);
        }
        else{    // b的栈顶元素如果大于a的，自然只能把a的元素移到b中
            move(a, b);
        }
    }

    bool isEnd(stack &b, stack &c, int n)    // 若有一根柱子满了，则循环结束
    {
        if (b.stack.size() == n || c.stack.size() == n){
            return true;
        }
        else{
            return false;
        }
    }

    void hanoi(int n, stack &A, stack &B, stack &C)
    {
        for (int i = 0;!isEnd(B, C, n); ++ i){
            if (i % 3 == 0){
                move(A, B);
                if (isEnd(B, C, n)){
                    break;
                }
                moveOneToOne(A, C);
            }
            else if (i % 3 == 1)
            {
                move(B, C);
                if (isEnd(B, C, n)){
                    break;
                }
                moveOneToOne(B, A);
            }
            else{
                move(C, A);
                if (isEnd(B, C, n)){
                    break;
                }
                moveOneToOne(C, B);
            }
        }
    }


    vector<string> getSolution(int n) {
        stack A,B,C;
        initStack(A, B, C, n);
        hanoi(n, A, B, C);
        return solution;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95

时间复杂度：O(2^N)，因为总的移动次数没有减少，与方法一相比时间复杂度不会降低。
空间复杂度：O(N)，开辟了3个数组用来存放盘子编号。

二、循环汉诺塔

解法:动态规划

确定状态，记所有盘子移动从A移动到B状态为0，从A移动到C状态为1;

第n步的状态为dp[n][0]、dp[n][1]，dp[n][0] 表示为所有盘子移动到B所需要的次数，dp[n][1] 表示为所有盘子移动到C所需要的次数。

第n个盘子可以移动到B时只需要移动1次，前n−1个盘子一定全部都在C上, 并且接下来要将C上的所有盘子移动到B上，此时所需要移动次数等同于将前n−1个盘子A移动到C上，因此此时的状态转移为:
dp[n][0]=1+dp[n−1][1]∗2

由此类推，所有盘子移动到C时，一定是第n个盘子先移动到B之后，再移动到C,即需要2步,而第n个盘子移动到B时，前n−1个盘子一定全部都在C上,移动次数为dp[n−1][1],且第n个盘子要移动到C时，前n−1个盘子一定要移动到A上，此时移动步数等价于将n−1个盘子从A移动到B的步数，即dp[n−1][0],当第n个盘子移动到C之后，又要将前n−1个盘子从A移动到C上。 因此此时的状态转移为：
dp[n][1]=1+dp[n−1][1]+1+dp[n−1][0]+dp[n−1][1]
即:
dp[n][0]=1+dp[n−1][1]∗2
dp[n][1]=2+dp[n−1][1]∗2+dp[n−1][0]

#include
using namespace std;

typedef long long ll;
const ll mod = 1e9+7;

ll dp[10000005][2];
int n;
int main(){
    cin>>n;
    
    dp[1][0] = 1;dp[2][0] = 5;
    dp[1][1] = 2;dp[2][1] = 7;
    
    for(int i = 3; i <= n; ++i){
        dp[i][0] = (1 + dp[i-1][1] * 2) % mod;
        dp[i][1] = (2 + dp[i-1][1] * 2 + dp[i-1][0]) % mod;
    }
    cout<<dp[n][0]<<' '<<dp[n][1]<<endl;
    return 0;
    
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23