ACW96
题目
汉诺塔问题，条件如下：
1、这里有A、B、C和D四座塔。
2、这里有n个圆盘，n的数量是恒定的。
3、每个圆盘的尺寸都不相同。
4、所有的圆盘在开始时都堆叠在塔A上，且圆盘尺寸从塔顶到塔底逐渐增大。
5、我们需要将所有的圆盘都从塔A转移到塔D上。
6、每次可以移动一个圆盘，当塔为空塔或者塔顶圆盘尺寸大于被移动圆盘时，可将圆盘移至这座塔上。
请你求出将所有圆盘从塔A移动到塔D，所需的最小移动次数是多少。
输入
无输入
输出
对于每一个整数n(1≤n≤121≤n≤12),输出一个满足条件的最小移动次数，每个结果占一行
思路
三个塔的汉诺塔问题的答案非常直观,可以用递归或者dp方法求解
比如dp方法:
1
2
3
4
dp[1]=1;
for(int i=2;i<=n;++i){
dp[i] = 2*dp[i-1] + 1; // 先把前i-1个挪到B上,把最后一个挪到C上,把前i-1个挪到C上
}
但是四个柱子就没这么直观了,我们可以仿照之前的思路,先挪一部分,化成子问题.
我们先挪K个放到B柱上,然后我们发现在挪走这K个之前,B柱是不能放东西的,所以问题瞬间化成了将n-k个盘子从A柱借助C柱挪到D柱上,就又化回了三个柱子的问题,最后再把K个盘子从B柱挪到Ｄ柱即可(四个柱子的子问题)
状态转移函数
1
2
3
4
5
6
dp[1]=1;
for(int i = 2;i <= n;++i){
for(int k=0;k<i;++k){
dp[i] = min(2*dp[k] + Three[n-k],dp[i]); // Three[]即三个柱子时的状态转移函数最终的结果
}
}
代码
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
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <string>
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
int d[50];
int f[50];
int main() {
int n;
d[0] = 0;
d[1] = 1;
f[0] = 0;
f[1] = 1;
for (int i = 2; i <= 20; ++i) {
d[i] = 2 * d[i - 1] + 1;
}
for (int i = 2; i <= 20; ++i) {
f[i] = d[i];
for (int k = 0; k < i; ++k) {
f[i] = min(f[i], 2 * f[k] + d[i - k]);
}
}
for (int i = 1; i <= 12; ++i) {
cout << f[i] << endl;
}
return 0;
}
