算法题每日一练 --- 第 11 天:第 39 级台阶
![算法题每日一练---第11天:第39级台阶](https://static001.geekbang.org/infoq/97/97f382c42ffa6e2fe4e6537ddb22d140.png)
一、问题描述
小明刚刚看完电影《第 39 级台阶》,离开电影院的时候,他数了数礼堂前的台阶数,恰好是 39 级!
站在台阶前,他突然又想着一个问题:
如果我每一步只能迈上 1 个或 2 个台阶。先迈左脚,然后左右交替,最后一步是迈右脚,也就是说一共要走偶数步。那么,上完 39 级台阶,那么总共有多少种不同的上法呢?
面对庞大的计算量人力计算肯定不行,请你利用计算机的优势,帮助小明寻找这个答案。
二、题目要求
考察
复制代码
运行限制
最大运行时间:1s
最大运行内存: 128M
三、问题分析
题目告诉我们的已知信息是总共有 39 个台阶,每一次只能跨越一个或者两个,而且要求跨越的总步数必须是偶数。
假如将上述题目中的步数要求为偶数给去掉,那么通过普通的斐波那契数列就可以解决这个问题。
复制代码
加上这一个条件,我们也只需要加上一个步数判断就行了。走一步跨越 1 个台阶,调用函数,步数加一。走一步跨越 2 个台阶,调用函数,步数加一。假如台阶数已经走完了,只需要判断步数是否为偶数。
判断条件为:if(n==0&&step%2==0)
四、编码实现
复制代码
五、输出结果
输出结果为:51167078 运行截图:
![](https://static001.geekbang.org/infoq/ca/cab6b6b513633f81dc02d3194f2b77bc.png)
版权声明: 本文为 InfoQ 作者【知心宝贝】的原创文章。
原文链接:【http://xie.infoq.cn/article/3c38df36a2482679590b6b54a】。文章转载请联系作者。
评论