题目描述: k一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
时间限制:1秒 空间限制:32768k
斐波那契数列指的是这样一个数列: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368。
可以观察到,从第3个数开始,每个数的值都等于前连个数之和。
同时,定义f(0)=0, f(1)=1.
则 f(2)=f(1)+f(0)=1;
f(3)=f(2)+f(1)=2;
... 依次类推,
f(n)=f(n-1)+f(n-2)
该问题实质是斐波那契数列求和,递推公式为 f(n)=f(n-1)+f(n-2);
可以考虑,小青蛙每一步跳跃只有两种选择:一是再跳一级阶梯到达第 i 级阶梯,此时小青蛙处于第 i-1 级阶梯;或者再跳两级阶梯到达第 i 级阶梯,此时小青蛙处于第 i-2 级阶梯。
于是,i 级阶梯的跳法总和依赖于前 i-1 级阶梯的跳法总数f(i-1)和前 i-2 级阶梯的跳法总数f(i-2)。因为只有两种可能性,所以,f(i)=f(i-1)+f(i-2);
依次类推,可以递归求出n级阶梯跳法之和。
递归算法实现:
public int JumpFloor(int target){
if(target<0)
return 0;
int[] fib={0,1,2};
if(target<3)
return fib[target];
return JumpFloor(target-1)+JumpFloor(target-2);
}
备注:此方法不满足空间要求(递归空间)。
非递归算法:
public int JumpFloor(int target){
if(target<0)
return 0;
int[] fib={0,1,2};
if(target<3)
return fib[target];
int total=0;
int firstElem=1;
int secondElem=2;
for(int i=3;i<=target;i++){
total=firstElem+secondElem;
firstElem=secondElem;
secondElem=total; //迭代
}
return total;
}
转自:http://www.nowcoder.com/questionTerminal/f4d47027d49a48b28274f6d4e0b6ff79?pos=12&tagId=0&orderByHotValue=1
最新文章
- 使用 MimeKit 和 MailKit 发送邮件
- JavaScript简单的tabel切换2
- Linux内核分析第一周学习总结:计算机是如何工作的?
- MySQL忘记密码怎么办
- BZOJ 3223 文艺平衡树 [codevs3303翻转区间]
- Java程序员可能犯的3个常见SQL错误
- c vs c++ in strcut and class
- [HNOI2009]无归岛
- Java8 中的 default
- 2014年GDG西安 -- DevFest Season1
- [日常工作]Oracle新增数据文件的小知识点
- js 获取DOM的style属性
- 求大神帮解答calendar日期插件的问题
- dblink连接操作远程数据库
- vue给元素动态添加class
- webpack config
- golang语言中os/exec包的学习与使用
- boost bind使用指南
- 使用 Azure CLI 在 Azure China Cloud 云平台上手动部署一套 Cloud Foundry
- 构造字典:DictionaryBase类和SortedList类
热门文章
- yii2使用相关记录
- 数据库访问CRUD;__SELF__和__ACTION__的区别;自动收集表单:$n->;create();
- 转:HAR(HTTP Archive)规范
- MySQL的几个概念:主键,外键,索引,唯一索引
- [SharePoint 2010] 自定义字段类型开发(二)
- JSPatch打补丁
- onload事件-----addLoadEvent函数
- 基于C#和Asp.NET MVC开发GPS部标监控平台
- Design and Analysis of Algorithms_Fundamentals of the Analysis of Algorithm Efficiency
- 点餐系统3个sprint的团队贡献分