在一無限大的二維平面中，我們做如下假設：
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
孟起 閱讀(642)
評論(0) 編輯 收藏 引用 所屬分類:
遞推 遞歸