Description
爬楼梯的时候，设每次可以上一级台阶或者两级台阶，计算上 n 级台阶的方案数。
Input
输入包含多组测试数据，对于每组测试数据： 输入只有一行为一个正整数 n(1 ≤ n ≤ 50)。
Output
对于每组测试数据，输出符合条件的方案数。 注意：64-bit 整型请使用 long long 来定义，并且使用 %lld 或 cin、cout 来输入输出，请不要使用 __int64 和 %I64d。
Sample Input
2
4
Sample Output
2
5
参考程序
#include <stdio.h>
#define LEN 50
int main()
{
int n;
while(scanf("%lld",&n)!=EOF)
{
int i;
long long a[LEN+5];
a[1]=1,a[2]=2;
for(i=3;i<=n;i++)
{
a[i]=a[i-1]+a[i-2];
}
printf("%lld\n",a[n]);
}
return 0;
}
分析
本题本质是斐波那契数列问题。思考过程：①如果只有一级台阶：那么只能跨一级，即仅1种方案；②如果有两级台阶：可以跨一级、再跨一级，或一次性跨两级，所以共2种方案；③有n级台阶：首先，可以先跨一级，后面n-1级利用之前计算的方案数得出；也可以先跨两级，后面n-2级利用之前计算的方案数得出。根据分类加法原理，这两种方法下的两种方案数加总就是n级台阶的方案总数。可见利用了递归思路。基于递归思路，给出基于递归的参考程序：
#include <stdio.h>
long long OutputStep(int n)
{
if(n==1)
{
return 1;
}
else if(n==2)
{
return 2;
}
else
{
return OutputStep(n-1)+OutputStep(n-2);
}
}
int main()
{
int n;
while(scanf("%lld",&n)!=EOF)
{
printf("%lld\n",OutputStep(n));
}
return 0;
}
遗憾的是，将上面基于递归的程序在线提交时，会出现“Time Limit Exceeded”的提示，表示部分样例在测试时，运算时间超出限制。而基于循环的（递推）的程序可以提交通过。查阅相关资料可以得出，有时当代码量或规模基本相同的两个程序（例如上面两个），基于递归的程序的时间开销比基于循环的程序大，涉及较多的栈操作和函数调用，所以时间不仅仅是花在了数值的计算上。但是在思路理解上，递归思路有时更容易理解，而且代码书写上比较简洁，程序可读性强。
关于递归和循环的比较大家可以参考博客《递归与循环的效率迷思》https://blog.csdn.net/tkokof1/article/details/93877058
版权声明：本文不是「本站」原创文章，版权归原作者所有 | 原文地址: