HDU-2077 汉诺塔IV
代码
#include <iostream>
#include <cstring>
using namespace std;
typedef long long LL;
const int MAX = 21;
int main() {
LL a[MAX];
memset(a, 0, sizeof(a));
for(int i=1; i<MAX; i++){
a[i] = 3*a[i-1]+2;
}
int T;
cin>>T;
for(int i=0; i<T; i++) {
int n;
cin>>n;
LL ans = a[n-1]+2;
cout<<ans<<endl;
}
return 0;
}
注解
1、本题是2064题的升级版。设2064题n个盘子的移动数目为F(n)
2、移动的过程如下:
(1)把n-2个盘子从A经过B移动到C -> F(n-2);
(2)把第n-1个盘子从A移动到B -> 1;
(3)把第n个盘子从A移动到B -> 1;
(4)把n-2个盘子从C经过B移动到A ->F(n-2);
(5)把第n个盘子从B移动到C -> 1;
(6)把第n-1个盘子从B移动到C -> 1;
(7)把n-2个盘子从A移动到C -> F(n-2)。
3、综上,本题n个盘子的移动数目f(n)=F(n-2)+4,又因为F(n-1)=3*F(n-2)+2,所以f(n)=F(n-1)+2