一个台阶总共有n级，如果一次可以跳1级，也可以跳2级。求总共有多少总跳法，并分析算法的时间复杂度。

admin2019-03-29 92

问题一个台阶总共有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)

一个台阶总共有n级，如果一次可以跳1级，也可以跳2级。求总共有多少总跳法，并分析算法的时间复杂度。

程序员面试

输入一个整数数组，判断该数组是不是某二元查找树的后序遍历的结果。如果是返回true，否则返回false。例如输入5、7、6、9、11、10、8，由于这一整数序列是如下树的后序遍历结果：8/\610

求1+2+…+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字以及条件判断语句（A?B:C）。

组合问题（从M个不同字符中任取N个字符的所有组合）

将一整数逆序后放入一数组中（要求递归实现）

大整数数相乘的问题。

类CMyString的声明如下：classCMyString{public:CMyString(char*pData=NULL);CMyString(constCMyString&str);~CMyString(void);

更改计算机管理员用户John名称为lusi的类型为受限用户。

在金山毒霸的反垃圾邮件设置中，将禁止的地址“ABC@abe．com”更改为“abe@abe．COrn”。

在Excel97中，要使B5单元格中的数据为A2和A3单元格中数据之和，而且B5单元格中的公式被复制到其他位置时不改变这一结果，可在B5单元格中输入公式()。A．=$A$2+$A$3B．=A2+A3C．=A:2+A:3D．=SUM(A2:A3

密码学中，把原始信息变成看似无意义的信息称为()。

古人创制的“二十四节气”最早全部出现在西汉初年的《淮南子》中。()

Mary______herbagatthefirstsightbyseeingitscolor.

脑出血最常见的出血部位是

平均指标属于()。

混凝土搅拌时间的确定与下列哪几项有关?()[2009年真题]①混凝土的和易性；②搅拌机的型号；③用水量的多少；④骨料的品种。

在地下管线测量中使用大功率电器设备时，工作电压超过()时，供电作业人员应使用绝缘防护用品，接地电极附近应设置明显警告标志，并设专人看管。

引起税收法律关系消灭的原因包括(　　)。

人的大脑在不同的年龄阶段的发展速度不同，存在发展加速期和发展相对缓慢期。这表明人的发展具有阶段性。(淄博)()

紧急避险对于第三者合法权益所造成的损害只能（）。

金蝉脱壳：漏网之鱼

一个台阶总共有n级，如果一次可以跳1级，也可以跳2级。求总共有多少总跳法，并分析算法的时间复杂度。

程序员面试

输入一个整数数组，判断该数组是不是某二元查找树的后序遍历的结果。如果是返回true，否则返回false。例如输入5、7、6、9、11、10、8，由于这一整数序列是如下树的后序遍历结果：8/\610

求1+2+…+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字以及条件判断语句（A?B:C）。

组合问题（从M个不同字符中任取N个字符的所有组合）

将一整数逆序后放入一数组中（要求递归实现）

大整数数相乘的问题。

类CMyString的声明如下：classCMyString{public:CMyString(char*pData=NULL);CMyString(constCMyString&str);~CMyString(void);

更改计算机管理员用户John名称为lusi的类型为受限用户。

在金山毒霸的反垃圾邮件设置中，将禁止的地址“ABC@abe．com”更改为“abe@abe．COrn”。

在Excel97中，要使B5单元格中的数据为A2和A3单元格中数据之和，而且B5单元格中的公式被复制到其他位置时不改变这一结果，可在B5单元格中输入公式()。A．=$A$2+$A$3B．=A2+A3C．=A:2+A:3D．=SUM(A2:A3

密码学中，把原始信息变成看似无意义的信息称为()。

古人创制的“二十四节气”最早全部出现在西汉初年的《淮南子》中。()

Mary______herbagatthefirstsightbyseeingitscolor.

脑出血最常见的出血部位是

平均指标属于()。

混凝土搅拌时间的确定与下列哪几项有关?()[2009年真题]①混凝土的和易性；②搅拌机的型号；③用水量的多少；④骨料的品种。

在地下管线测量中使用大功率电器设备时，工作电压超过()时，供电作业人员应使用绝缘防护用品，接地电极附近应设置明显警告标志，并设专人看管。

引起税收法律关系消灭的原因包括( )。

人的大脑在不同的年龄阶段的发展速度不同，存在发展加速期和发展相对缓慢期。这表明人的发展具有阶段性。(淄博)()

紧急避险对于第三者合法权益所造成的损害只能（）。

金蝉脱壳：漏网之鱼

引起税收法律关系消灭的原因包括(　　)。