7-2 sdut-C语言实验-刘老师的要求之踩方格

7-2 sdut-C语言实验-刘老师的要求之踩方格

分数 12

全屏浏览

切换布局

作者 马新娟

单位 山东理工大学

由于淄博烧烤拉近了人与人之间的距离，来自全世界的朋友慕名前来淄博体验。某烧烤店人山人海，需要排队才能入场。淄博的刘老师愿意免费为远方的大学生排队，但需要远方的大学生解答出如下问题方可。题目如下：

有一个方格矩阵，矩阵边界在无穷远处。我们做如下假设：

a、每走一步时，只能从当前方格移动一格，走到某个相邻的方格上；

b、走过的格子立即塌陷无法再走第二次；

c、只能向下、左、右三个方向走；

请问：如果允许在方格矩阵上走n步，共有多少种不同的方案。2种走法只要有一步不一样，即被认为是不同的方案。

你能获得刘老师的免费排队吗？加油！

输入格式:

允许在方格上行走的步数n(n≤20)。

输出格式:

计算出的方案数量。

From:teacher Liu.

2

输出样例:

7

代码长度限制

16 KB

时间限制

400 ms

内存限制

64 MB

栈限制

8192 KB

#include<stdio.h>
int main()
{
    long long f[25];
    int n,i;
    f[1]=3;
    f[2]=7;
    scanf("%d",&n);
    for(i=2;i<=n;i++)
    {
        f[i]=2*f[i-1]+f[i-2];
    }
    printf("%lld\n",f[n]);//max
    return 0;
}