在一无限大的二维平面中，我们做如下假设：
1、 每次只能移动一格；
2、 不能向后走（假设你的目的地是“向上”，那么你可以向左走，可以向右走，也可以向上走，但是不可以向下走）；
3、 走过的格子立即塌陷无法再走第二次；
求走n步不同的方案数（2种走法只要有一步不一样，即被认为是不同的方案）。
http://acm.hdu.edu.cn/showproblem.php?pid=2563
1 /*设a[n]是向上走n步的方法数，b[n]是向左或向右走的方法数，
2 则a[n]=a[n-1]+b[n-1], b[n]=２*a[n-1]+b[n-1]
3 因为f[n]=a[n]+b[n]
4 化简得f[n]=3*a[n-1]+2*b[n-2]=2*f[n-1]+a[n-1]=2*f[n-1]+f[n-2]
5 */
6 #include<stdio.h>
7 int main()
8 {
9 int i,t,n,f[22];
10 f[1]=3; f[2]=7;
11 for(i=3;i<=20;i++)
12 f[i]=2*f[i-1]+f[i-2];
13 scanf("%d",&t);
14 while(t--)
15 {
16 scanf("%d",&n);
17 printf("%d\n",f[n]);
18 }
19 return 0;
20 }
posted on 2010-10-05 11:54
孟起 阅读(624)
评论(0) 编辑 收藏 引用 所属分类:
递推 递归