从根本理解汉诺塔问题

分析题意

对于汉诺塔问题，我们究其根底

约定：

1. 我们用ABCDE来命名塔的名字，
2. 默认初始的圆盘都在A塔上，最终要移动到最后一个塔上。
3. d 数组存放3个塔的结果，f 数组存放4个塔的结果， g 数组存放5个塔的结果

两个塔（AB）

如果只有两个塔，那么只有圆盘个数为一时，答案为1，其余答案为0

三个塔（ABC）

如果有三个塔，移动时我们需要借助二塔里的结论

如果要移动 n 个圆盘，我们需要在三塔的情况下，将上面 n - 1 个较小圆盘移动到B塔，在将一个大圆盘移动到C塔，最后在将 n - 1 个圆盘在三塔的情况下从B移动到C塔

结论：d(n) = d(n - 1) + 1 + d(n - 1)

四个塔（ABCD）

解决完三塔问题，四塔问题将于三塔类似

如果要移动n个圆盘从A到D的话，我们的解决方法是将一部分圆盘（i个圆盘）先移动到B（或者C），因为这前几个圆盘都是非常小的，后面剩下的大圆盘不能压在上面，所以放小圆盘这个塔暂时不能使用

那么问题将会变成，怎么在三塔情况下将n - i 个圆盘从A移动到D，这时可以用三塔的结论；

问题1：我们先移动的一部分圆盘到底是几个呢，我们需要枚举，最终答案取最小值。

结论：先把前 i 个盘子在四塔情况下移动到B，剩下的盘子在三塔情况下移动到D，最后在将那 i 个小的盘子在四塔情况下从B移动到D。

f(n) = min(f(n), f(i) + d(n - i) + f(i)) 0 <= i <= n;

代码奉上

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int d[15], f[15];

int main()
{
    for(int i = 1; i <= 12; i ++ ) d[i] = 2 * d[i - 1] + 1;        //三塔结果

    memset(f, 0x3f, sizeof f);

    f[0] = 0;

    for(int i = 1; i <= 12; i ++ )                //有几个盘子
        for(int j = 0; j <= i; j ++ )                   //先取几个放到B
            f[i] = min(f[i], 2 * f[j] + d[i - j]);

    for(int i = 1; i <= 12; i ++ )  cout << f[i] << endl;
    return 0;
}

五个塔（ABCDE）

解决完四塔，相信很多人可以类比出五个塔甚至 n 个塔了吧

没错五个塔的思路和四个塔的思路一样，

盘子在A到E的过程中，我们先取出 j 个盘子放到B上（五塔情况下进行）、在取出 k 个盘子放到C上（因为B塔不能在用，所以为四塔情况下进行）、最后的一点直接移动到 E 盘（三塔情况下）

结论：g[i] = min(g[i], 2 * g[j] + 2 * f[k] + d[i - j - k]);

代码奉上

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int d[15], f[15], g[15];

int main()
{
    for(int i = 1; i <= 12; i ++ ) d[i] = 2 * d[i - 1] + 1;        //三塔结果
    
    memset(f, 0x3f, sizeof f);
    memset(g, 0x3f, sizeof g);
    
    f[0] = 0;
    g[0] = 0;
    
    for(int i = 1; i <= 12; i ++ )
        for(int j = 0; j <= i; j ++ )
            f[i] = min(f[i], 2 * f[j] + d[i - j]);        //四塔结果
    
    for(int i = 1; i <= 12; i ++ )
    {
        for(int j = 0; j <= i; j ++ )                //枚举第一部分
            for(int k = 0; k <= 12 - j; k ++ )        //枚举第二部分
            {
                g[i] = min(g[i], 2 * g[j] + 2 * f[k] + d[i - j - k]);
            }
        cout << g[i] << endl;
    }
    return 0;
}

执行结果

1
3
5
7
11
15
19
23
27
31
39
47