In The End

个人博客

0%

Acwing96题：奇怪的汉诺塔

发表于 更新于 分类于

三塔问题

我们先来推三塔问题

假设$d[n]$表示在三个塔的情况下将n个盘子从一个塔转移到另一个塔的步数

注意：这时候到底从哪个塔到哪个塔不重要，只要知道有一个塔可以辅助操作就可以了

这种问题只需要找到$d[n]$与$d[n-1]$即可，其实我们并不需要太清楚其中的细节，想多了会把自己绕进去。因为我们知道$d[1]=1$,所以只要能找到递推关系，其中到底发生了什么我们就直接忽略

假设我们知道$d[n-1]$,我们该如何解决问题，我们首先把$n-1$个盘子放到B塔，然后搬一个盘子去C塔，然后再把$n-1$​个盘子搬到C塔，所以递推式如下

$d[n] = d[n-1] + 1 + d[n-1]$

整理一下就是

$d[n] = 2*d[n-1] + 1$

四塔问题

继续使用我们的并不知道原理但是xjb推递推公式的神奇思路

四塔问题在解决过程中是一定会碰到三塔问题的，所以解决四塔问题时可以先把三塔问题的$d$数组先求出来

首先我们要知道$f[1]=1$，所以我们的递归有了起点（放心了）

四塔问题因为多了一个塔，所以本来我们放$n-1$个去一个塔的思路需要升级一下，我们要枚举放多少个盘子去B，然后将AB两塔转移到D

那么我们假设A->B是四塔，那么B->D是三塔，然后A->D又变成了四塔

所以递推式为

$f[n] = min\{2 * f[i] + d[n-i]\}~(1\le i < n)$

所以代码就很简单了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
using namespace std;
const int maxn=20,inf=0x3f3f3f3f;

int d[maxn],f[maxn];

int main(){
    for(int i=1;i<=12;i++){
        if(i==1)
            d[1]=1,f[1]=1;
        else{
            f[i]=inf,d[i]=2*d[i-1]+1;
            for(int j=0;j<=i;j++)
                f[i]=min(f[i],2*f[j]+d[i-j]);
        }
        printf("%d\n",f[i]);
    }
    return 0;
}