首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
一个台阶总共有n级,如果一次可以跳1级,也可以跳2级。求总共有多少总跳法,并分析算法的时间复杂度。
一个台阶总共有n级,如果一次可以跳1级,也可以跳2级。求总共有多少总跳法,并分析算法的时间复杂度。
admin
2019-03-29
155
问题
一个台阶总共有n级,如果一次可以跳1级,也可以跳2级。求总共有多少总跳法,并分析算法的时间复杂度。
选项
答案
首先我们考虑最简单的情况。如果只有1级台阶,那显然只有一种跳法。如果有2级台阶,那就有两种跳的方法了:一种是分两次跳,每次跳1级;另外一种就是一次跳2级。 现在我们再来讨论一般情况。我们把n级台阶时的跳法看成是n的函数,记为f(n)。当n>2时,第一次跳的时候就有两种不同的选择:一是第一次只跳1级,此时跳法数目等于后面剩下的n-1级台阶的跳法数目,即为f(n-1);另外一种选择是第一次跳2级,此时跳法数目等于后面剩下的n-2级台阶的跳法数目,即为f(n-2)。因此n级台阶时的不同跳法的总数f(n)=f(n-1)+(f-2)。 我们把上面的分析用一个公式总结如下: [*]
解析
这道题最近经常出现,包括MicroStrategy等比较重视算法的公司都曾先后选用过个这道题作为面试题或者笔试题。
转载请注明原文地址:https://kaotiyun.com/show/pxmZ777K
0
程序员面试
相关试题推荐
WhenIseeclients,thisisthequestionthatI’maskedthemost.Ifyou’reinapublicplace,lookaround.【F1】Nearlyeveryone
Individualsandbusinesseshavelegalprotectionforintellectualpropertytheycreateandown.Intellectualproper【C1】______fro
输入一个整数和一棵二元树。从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。打印出和与输入整数相等的所有路径。例如输入整数22和如下二元树10
输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点,只调整指针的指向。 比如将二元查找树10
.asp.net如何实现MVC模式,举例说明!
请恢复金山反垃圾邮件过滤列表。
利用"开始"菜单的"运行"选项,启动"计算器"应用程序,计算器应用程序的标识为:c:\windows\system32\calc.exe(在"打开"中直接填写标识名)。
在Excel97的某单元格内输入了一个公式后,单元格的显示为"#######",这是由于()。A.所得结果没有意义B.所得结果长度超过了列宽C.公式输入有误D.所得结果被隐藏
关系型数据库只能描述()关系。A.网络型B.二维表格C.图D.层次型
论逻辑网络设计过程中财用户需求的把握对于网络规划设计工程师来说,在把某项工作系统化的时候,正确地理解该项工作的内容并设计出有效的系统,是一件最困难的事情。为了把用户的需求正确无误地反映到网络工程项目的逻辑设计文档中,常规的做法是将该工程项目的需求说
随机试题
封闭环公差等于增环公差。()
一初产妇,妊娠35周。近1周来感乏力、食欲不振、恶心等不适。检查肝功能SGPT明显升高,HBsAg阳性。其诊断为()
A.信息产业主管部门B.药品监督管理部门C.卫生行政部门D.工商行政管理部门E.电信管理机构根据《互联网药品信息服务管理办法》提供互联网药品信息服务的网站发布药品广告的审查批准部门是
甲向乙借款5000元,乙平时与甲关系甚好不便拒绝,便说现金不够,3天后再来取,3天以后,乙避而不见,下列表达中不正确的有:()
工程目标管理和控制进度支付的依据是()。
(操作员:李主管;账套:501账套;操作日期:2015年1月31日)在“管理人员工资表”中,录入以下员工的考勤数据。
2017年中央一号文件的关键词是()。
影响课堂管理的因素有()。
下列各句中,没有语病的一句是()。
—Ohdear.What’swrong?—Well,I’mmakingsomechangestotheproduct______,togivethecompanyawholenewimage.
最新回复
(
0
)