剑指OFFER之跳台阶（九度OJ1388）
剑指OFFER之跳台阶（九度OJ1388）
用户1154259
发布于 2018-01-17 19:20:40
发布于 2018-01-17 19:20:40
文章被收录于专栏：xingoo, 一个梦想做发明家的程序员
题目描述：
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
输入：
输入可能包含多个测试样例，对于每个测试案例，
输入包括一个整数n(1<=n<=70)。
输出：
对应每个测试案例，
输出该青蛙跳上一个n级的台阶总共有多少种跳法。
样例输入：
5
样例输出：
8
题目分析：
这道题很明显正向分析是不行的，也就是说，最后面的一个台阶，要依赖于前面台阶的。所以，最后一个台阶的方法数目可以由前面计算出来。那么，仔细想一下，一个青蛙只能跳1-2步，也就是说，最后一个台阶肯定是由它的前一个台阶或者前两个台阶上去的（假设这个时候台阶数目很长）。那么很显然，到达最后一个台阶的方法数目等于前一个台阶的方法数目加上前两个台阶的方法数目，到这里我们发现这是一个很典型的斐波那契数列。问题就好解决了，从前一道题的思路上看，要接的两个问题： 1 不要超时 2 注意数据的格式，long long 输出时使用%lld
代码
#include <stdio.h>
long long stair[71];
void getStair(void);
int main(){
int n;
getStair();
while(scanf("%d",&n) != EOF && n>=1 && n <= 70){
printf("%lld\n",stair[n]);
}
return 0;
}
void getStair(void){
int i;
stair[0] = 1;
stair[1] = 1;
for(i=2;i<71;i++){
stair[i] = stair[i-1]+stair[i-2];
}
}
/**************************************************************
Problem: 1388
User: xhalo
Language: C
Result: Accepted
Time:0 ms
Memory:916 kb
****************************************************************/本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2014-05-22 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
