【解题报告】 POJ1958 奇怪的汉诺塔

在这样热浪滚滚的暑假，外面晴空高照，在家里刷刷题不妨是最好的选择

——来自wweiyi语录

题目链接（翻译过的）：

https://www.acwing.com/problem/content/98/

题意简述：输出四个塔的汉诺塔分别从1个盘子到12个盘子的最少步数

河内塔.jpg

我们看了题之后，可以知道这道题跟三个塔的汉诺塔一样，用递归，但是我们设先移走i个盘子到第二个塔或第三个塔，然后就转化成三个塔的问题了。

但是问题在于不知道i等于多少，而且直接输出12个值要用递归也会有些慢，所以我们做一下优化，记忆化一下，我们就可以很快的输出了

设三个塔n个盘子的步数为d[n],设四个塔n个盘子的步数为f[n]

动态转移方程如下

fn=min(fn,2fi+dn−i)f_n=min(f_n,2f_i+d_{n-i})

其中

1≤n,i≤121\leq n,i \leq 12

所以我们就解决了这道题目

代码如下

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
#include <iostream>
#include <cstring>
using namespace std;
int d[15];
int f[15];
int min(int a,int b)//最小值函数
{
	return a<b? a:b;
}
int main()
{
	d[1]=1;//汉诺三塔边界
	for(int i=2;i<=12;i++)//计算汉诺三塔的数值
	d[i]=2*d[i-1]+1;
	memset(f,0x3f,sizeof f);//因为要求最小值，所以初始一个极大值
	f[1]=1;//汉诺四塔边界
	for(int i=2;i<=12;i++)//动态规划
	{
		for(int j=1;j<i;j++)
		{
			f[i]=min(f[i],2*f[j]+d[i-j]);//状态转移方程
		}
	}
	for(int i=1;i<=12;i++)
	cout<<f[i]<<endl;//输出
	return 0;
}