hdoj 2064 汉诺塔III 递推

题目描述: http://acm.hdu.edu.cn/showproblem.php?pid=2064(中文)

题目分析:
把n 个盘子从A 间接(不能把盘子直接从A 移到C )移到C 需要以下五步:
1. 把n - 1 个盘子间接从A 移到C,    f(n - 1)
2. 把最大的盘子从A 移到B,             1
3. 把n - 1 个盘子间接从C 移到A,    f(n - 1)
4. 把最大的盘子从B 移到C               1
5. 把n - 1 个盘子间接从A 移到C,    f(n - 1)

易得f(n) = 3 *　f(n - 1) + 2, f(1) = 2;

//编译器:vc6.0
#include <iostream>
using namespace std;

typedef __int64 Int;


int main() {
	Int a[36];
	a[1] = 2;
	a[2] = 8;
	for(Int i = 3; i <= 35; i += 1)
		a[i] = 3 * a[i - 1] + 2;
	

	int n;
	while(scanf("%d", &n) != EOF)
		printf("%I64d\n", a[n]);

	return 0;
}

通过递推公式可得: f(n) = 3^n - 1;
所以直接输出即可

while(scanf("%d", &n) != EOF) {
		printf("%I64d\n", (long long)(pow(3, n) - 1));
	}