题目描述

一只青蛙一次可以跳上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

最新文章

  1. 移动测试会Ebay沙龙PPT
  2. AWVS漏洞测试-02节-添加一个简单的新闻系统
  3. 2015年百度之星初赛(1) --- C 序列变换
  4. Linux 环境下如何使 Chrome 浏览器字体更漂亮
  5. JAVA基础知识之多线程——控制线程
  6. git参考书籍
  7. C#调用cmd程序,读取结果
  8. js第四章作用域
  9. 【MySQL 读书笔记】SQL 刷脏页可能造成数据库抖动
  10. SQLServer删除重复行
  11. GIT-Bonobo.Git.Server的使用
  12. iOS---------Xcode中添加预编译pch文件
  13. pycharm 报错:pycharm please specify a different SDK name
  14. c#之有参和无参构造函数,扩展方法
  15. python学习之老男孩python全栈第九期_数据库day001 -- 作业
  16. Python 使用正则表达式匹配电子邮箱
  17. SQL 查询某时间段的数据 datadiff 计算时间差
  18. 主从复制时报: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
  19. 解读:计数器Counter
  20. C语言和C++中的字符串(string)

热门文章

  1. python爬虫(3)——用户和IP代理池、抓包分析、异步请求数据、腾讯视频评论爬虫
  2. jmeter beanshell断言接口自动化实例
  3. pycharm 远程连接
  4. 01_javaSE面试题:自增变量
  5. Educational Codeforces Round 78 (Rated for Div. 2) 题解
  6. SQL Server 迁移数据库 (三)使用SQL脚本
  7. java程序 cpu占用过高分析
  8. fiddler抓包-8-工作中get到的断点使用
  9. Go gRPC Hello World
  10. vue自定义事件---拖拽