随笔-19  评论-1  文章-0  trackbacks-0

在一无限大的二维平面中,我们做如下假设:
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]=2*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 孟起 阅读(601) 评论(0)  编辑 收藏 引用 所属分类: 递推 递归

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理