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;a = 2;a = 8;for(Int i = 3; i <= 35; i += 1)a = 3 * a + 2;int n;while(scanf("%d", &n) != EOF)printf("%I64d\n", a);return 0;}
通过递推公式可得: f(n) = 3^n - 1;
所以直接输出即可
while(scanf("%d", &n) != EOF) {printf("%I64d\n", (long long)(pow(3, n) - 1));}
页:
[1]