剑指offer 9-10:青蛙跳台阶与Fibonacii数列
2024-09-03 12:14:40
题目描述
一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。
问题分析
我们将跳法个数y与台阶数n视为一个函数关系,即y=f(n)。首先从第一级开始,当n=1时,只有一种跳法,即f(1)=1。当有两级台阶时,有两种跳法,跳两个一阶,或直接跳两阶,共有两种解法,即f(n)=2。
当n>2时,对于n级台阶而言,每次只能选跳一阶或者二阶中的一种,无论是哪一种,都只有唯一的选择。故当跳一阶的时候,跳法和f(n-1)的跳法个数相同,当跳二阶的时候,跳法个数和f(n-2)的个数相同。从
而对于跳n阶台阶的解法满足f(n)=f(n-1)+f(n-2)。
对于这个计算公式,大家有没有很熟悉。没错这就是斐波那契数列的计算公式,跳台阶问题就是斐波那契数列问题的一个变种,只不过起始条件稍有变化,通常推荐使用循环来实现fibonacci数列。
下面给出该问题的C++实现:
class Solution {
public:
int jumpFloor(int number) {
//斐波那契数列问题的扩展
if(number<=0){ //非法输入检测
return 0;
}else if(number<=2){ //起始一级和两级台阶
return number;
}
int pre_2=1,pre_1=2,curr=0;
for(int i= 3;i<=number;i++){ //使用循环求解斐波那契数列
curr=pre_2+pre_1;
pre_2=pre_1;
pre_1=curr;
}
return curr;
}
};
刷题,只为了不给自己留遗憾!------haozi
最新文章
- 移动测试会Ebay沙龙PPT
- AWVS漏洞测试-02节-添加一个简单的新闻系统
- 2015年百度之星初赛(1) --- C 序列变换
- Linux 环境下如何使 Chrome 浏览器字体更漂亮
- JAVA基础知识之多线程——控制线程
- git参考书籍
- C#调用cmd程序,读取结果
- js第四章作用域
- 【MySQL 读书笔记】SQL 刷脏页可能造成数据库抖动
- SQLServer删除重复行
- GIT-Bonobo.Git.Server的使用
- iOS---------Xcode中添加预编译pch文件
- pycharm 报错:pycharm please specify a different SDK name
- c#之有参和无参构造函数,扩展方法
- python学习之老男孩python全栈第九期_数据库day001 -- 作业
- Python 使用正则表达式匹配电子邮箱
- SQL 查询某时间段的数据 datadiff 计算时间差
- 主从复制时报:ERROR 1794 (HY000): Slave is not configured or failed to initialize properly. You must at least set --server-id to enable either a master or a slave. Additional error messages can be found in t
- 解读:计数器Counter
- C语言和C++中的字符串(string)