2019独角兽企业重金招聘Python工程师标准>>>
题目描述:
-
一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
输入:
-
输入可能包含多个测试样例,对于每个测试案例,
输入包括一个整数n(1<=n<=50)。
输出:
-
对应每个测试案例,
输出该青蛙跳上一个n级的台阶总共有多少种跳法。
样例输入:
6
样例输出:
32
解题思路:
这道题目跟之前的跳台阶大同小异,只是跳台阶的阶数从1变到了n,也就是说,不再是跳一下或者跳两下的问题,而是跳n下的问题。那么解题的思路显然还得逆向分析,我们发现:
每个最终台阶都可以一步跳上去,也可以从他的前一个台阶跳一下上去,也可以从他的前两个台阶跳两个台阶上去。那么总结发现:
最后剩下的台阶数,加上之前的跳台阶的方法,即可。即:
最后剩下零个台阶,暂且定为0,直接跳n个台阶上来,显然只有一种方法,我们每次循环首先自加1就行了。
最后剩下1个台阶,那么共有(第n-1个台阶的方法数)种;
最后剩下2个台阶,共有(第n-2个台阶的方法数)种;
....
最后剩下n-1个台阶,只有一种方法。
把上面的方法累加起来,既是跳到第n阶台阶的数目。
代码:
#include <stdio.h>
long long int arr[51] = {0,1};
void createArr(void);
int main(void){int n;createArr();while(scanf("%d",&n)!=EOF && n>=1 && n<=50){printf("%lld\n",arr[n]);}return 0;
}
void createArr(void){int i,j;for(i=2;i<51;i++){j=i-1;arr[i]++;//直接跳跃到本身的while(j){arr[i] += arr[j];j--;}}
}