本文共 1385 字，大约阅读时间需要 4 分钟。

奇怪汉诺塔

题目链接：

题目大意

汉诺塔问题，条件如下：

• 这里有 A、B、C 和 D 四座塔。
• 这里有 个圆盘， 的数量是恒定的。
• 每个圆盘的尺寸都不相同。
• 所有的圆盘在开始时都堆叠在塔 A 上，且圆盘尺寸从塔顶到塔底逐渐增大。
• 我们需要将所有的圆盘都从塔 A 转移到塔 D 上。
• 每次可以移动一个圆盘，当塔为空塔或者塔顶圆盘尺寸大于被移动圆盘时，可将圆盘移至这座塔上。

请你求出将所有圆盘从塔 A 移动到塔 D，所需的最小移动次数是多少

解题思路

显而易见，这是一道四塔的汉诺塔问题。

首先我们考虑三塔的汉诺塔问题。

众所皆知三塔是设 $d(n)$ 为 $n$ 个盘子的最优解，将 $A$ 的 $n-1$ 个盘子放置到 $B$ ，最优步数为 $d(n-1)$ ；再将剩下的 $1$ 个盘子放到 $C$ ，最后将 $B$ 上的 $n-1$ 个盘子放到 $C$ ，最优步数也为 $d(n-1)$ ，故有递推式 $d(n)=2\ast d(n-1)+1$。

现在我们再考虑四塔的汉诺塔问题。

我们也设 $f(n)$ 表示有 $n$ 个盘时四塔汉诺塔的最优解。
我们把 $B$ 看做一个中转，将 $j$ 个盘移到 $B$ 上，最优步数为 $f(j)$。
那么还剩下 $n-j$ 个盘子，由于 $B$ 上已经有了盘子，剩下的 $A$，$C$，$D$ 就构成了一个三塔的汉诺塔问题，最优步数为 $d(n-j)$ 。
最后将 $B$ 上的 $j$ 个盘子移动到 $D$ 上，最优步数也是 $f(j)$ 。
则递推式为：
f ( n ) = m i n { 2 ∗ f ( j ) + d ( n − j ) }                    0 ≤ 1 ≤ n \begin{array}{l}f(n)=min\{2\ast f\left(j\right)+d\left(n-j\right)\}\\\;\;\;\;\;\;\;\;\;0\leq1\leq n\end{array} f(n)=min{ 2∗f(j)+d(n−j)}0≤1≤n​
我们最后枚举 $j$ ，对答案取 $\min$ 即可。

code

#include<iostream>#include<cstdio>using namespace std;int d[20];int f[20];int main(){   	for(int i=1;i<=12;i++)		d[i]=2*d[i-1]+1;	f[1]=1;	cout<<1<<endl;	for(int i=2;i<=12;i++)	{   		f[i]=0x3f3f3f3f;		for(int j=1;j<=i;j++)			f[i]=min(f[i],2*f[j]+d[i-j]);		cout<<f[i]<<endl;	}}