首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
一个台阶总共有n级,如果一次可以跳1级,也可以跳2级。求总共有多少总跳法,并分析算法的时间复杂度。
一个台阶总共有n级,如果一次可以跳1级,也可以跳2级。求总共有多少总跳法,并分析算法的时间复杂度。
admin
2019-03-29
160
问题
一个台阶总共有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
程序员面试
相关试题推荐
[A]Thatkindofdominancecreatesatensionbetweenpropertyrightsandantitrust(opposingorintendedtorestraintrusts,monop
TheGreeksassumedthatthestructureoflanguagehadsomeconnectionwiththeprocessofthought,whichtookrootinEuropelon
输入一个整形数组,数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。例如输入的数组为1,-2,3,10,-4,7,2,-5,和最大的子数组为3,10,
删除串中指定的字符
下面是一个数组类的声明与实现。请分析这个类有什么问题,并针对存在的问题提出几种解决方案。templateclassArray{public:Array(unsignedarraySize):data(0),size(arraySize)
在金山毒霸的反垃圾邮件设置中,将禁止的地址“ABC@abe.com”更改为“abe@abe.COrn”。
如果要将页面上的某个图形设计成页面下载后显示在页面上,当鼠标放在它的上面时,该图形变为另一图形,那么可以通过______方法来设置。A.使用时间线B.“RolloverImage”命令C.将图形插入到表格中D.使用层与行为
关于PPoint97启动对话框的描述,()是错误的。A.使用“内容提示向导”,能在系统提示下创建新演示文稿B.使用“模板”可生成具有一定布局和色彩的幻灯片C.“打开已有的演示文稿”选项没有任何作用D.使用“空演示文稿”创建一张空白幻灯片
将文件从FTP服务器传输到本地计算机的过程称为()。
IEEE1394是一种并行接口标准。
随机试题
软件科学和______的发展,为公文管理自动化提供了理论依据和丰富的软件开发工具。
牡丹皮在大黄牡丹汤中的配伍意义是
患者,女,37岁,3年来腰部时常酸痛,腰部肌肉僵硬,久坐加重,舌质淡暗,边有瘀点。针灸治疗除主穴外,应加取
基金年度报告中的投资组合报告应披露的信息不包括()。
某企业打算在B市兴建一座跨江大桥,但这个项目的不确定性因素很多,该企业决定将新建项目总投资、银行贷款利率、过桥费收入这三个因素作为分析对象,分析每一个因素的变化对本大桥内部收益率的影响,该企业所采用的分析方法是()。
根据资料,回答以下问题。2012年,某省规模以上工业增加值10875亿元,比上年增长7.1%,月度增速从1~2月的2.9%回升到10~12月的10%以上。大型、中型和小微型企业增加值分别为3074、3217和4584亿元,比上年分别增长8.2%、6.8%
互动治疗(社科院2011年研)
先履行抗辩权行使的主体是双务合同中的()。
A=,r(A)=2,则()是A*X=0的基础解系.
MargaretSangerandBirthControlMargaretSanger,anAmericannurse,wasthefirsttostartthemodernbirthcontrolmoveme
最新回复
(
0
)