汉诺塔问题合集之汉诺塔4

http://acm.hdu.edu.cn/showproblem.php?pid=2077

汉诺塔4：

首先自己思考问题的方式是对的，但是表达是错的

问题分析：

1.先把上面的（n-1）个圆盘，从a移到b上；

2.由于此时最大的圆盘可以放在最上面，那么第二步就可以把最后一个圆盘从a，一到b上；

3.把最大的圆盘从b移到c上；

4.把b上的（n-1）个圆盘从b移到c上；

于是自己就不动脑子，以为是很简单题，写出了错误的代码：

 1 /* */
 2 # include <bits/stdc++.h>
 3 # include <iostream>
 4 # include <cstdio>
 5 # include <cmath>
 6 using namespace std;
 7 
 8 int main()
 9 {
10     long long int f[30];
11     int i;
12     memset(f, 0, sizeof(f));
13     f[1] = 2;
14     for( i=2; i<=20; i++ )
15     {
16         f[i] = 2 * ( f[i-1] + 1 );
17     }
18     int T, n;
19     scanf("%d", &T);
20     while( T-- )
21     {
22         scanf("%d", &n);
23         printf("%lld
", f[n]);
24     }
25     return 0;
26 }

后来看了人的代码，才发现了问题，自己上面的写法，子问题没有完全找对。

注意：题目要求只有最大的可以放在可以放在最上面，（其他的必须小的在大的上面）

而自己上面的写法，每一个子问题的最大的都可以在最上面，就相当于不是每个问题只有一个最大的放在最上面；

所以问题的子问题，应该是汉诺塔3，把上面的（n-1）个圆盘从a移到c；只不过此时这（n-1）个圆盘是直接从a到b到c的，没有来来回回（汉诺塔3来回了3次），只来了一次；

再加上最圆盘从a到b到c的2步；f[i] = F[i-1]+2（F[i]为汉诺塔3的方案，f[i]为本题的方案）

所以正确的代码如下：

 1 /* */
 2 # include <bits/stdc++.h>
 3 # include <iostream>
 4 # include <cstdio>
 5 using namespace std;
 6 
 7 int main()
 8 {
 9     int n, T, i;
10     long long int f[30], F[30];
11     memset(f, 0, sizeof(f));
12     cin>>T;
13     f[1] = 2;
14     F[1] = 2;
15     for( i=2; i<=25; i++ )
16     {
17         F[i] = 3 * F[i-1] + 2;
18     }
19     for( i=2; i<=25; i++ )
20     {
21         f[i] = F[i-1] + 2;
22     }
23     while( T-- )
24     {
25         cin>>n;
26         cout<<f[n]<<endl;
27     }
28     return 0;
29 }