第1章 面试的流程
第2章 面试需要的基础知识
第3章 高质量的代码
第4章 解决面试题的思路
第5章 优化时间和空间效率
第6章 面试中的各项能力
第7章 两个面试案例
面试题9:斐波那契数列
题目一:写一个函数,输入n,求斐波那契(Fibonacci)数列的第n项。斐波那契数列的定义如下:
效率很低的解法,挑剔的面试官不会喜欢
很多C语言教科书在讲述递归函数的时候,都会用Fibonacci作为例子,因此很多应聘者对这道题的递归解法都很熟悉。他们看到这道题的时候心中会忍不住一阵窃喜,因为他们能很快写出如下代码:
我们的教科书上反复用这个问题来讲解递归函数,并不能说明递归的解法最适合这道题目。面试官会提示我们上述递归的解法有很严重的效率问题并要求我们分析原因。
我们以求解f(10)为例来分析递归的求解过程。想求得f(10),需要先求得f(9)和f(8)。同样,想求得f(9),需要先求得f(8)和f(7)……我们可以用树形结构来表示这种依赖关系,如图2.12所示。
图2.12 基于递归求斐波那契数列的第10项的调用过程
我们不难发现在这棵树中有很多结点是重复的,而且重复的结点数会随着n的增大而急剧增加,这意味计算量会随着n的增大而急剧增大。事实上,用递归方法计算的时间复杂度是以n的指数的方式递增的。读者不妨求Fibonacci的第100项试试,感受一下这样递归会慢到什么程度。
面试官期待的实用解法
其实改进的方法并不复杂。上述递归代码之所以慢是因为重复的计算太多,我们只要想办法避免重复计算就行了。比如我们可以把已经得到的数列中间项保存起来,如果下次需要计算的时候我们先查找一下,如果前面已经计算过就不用再重复计算了。
更简单的办法是从下往上计算,首先根据f(0)和f(1)算出f(2),再根据f(1)和f(2)算出f(3)……依此类推就可以算出第n项了。很容易理解,这种思路的时间复杂度是O(n)。实现代码如下:
时间复杂度O(logn)但不够实用的解法
通常面试到这里也就差不多了,尽管我们还有比这更快的O(logn)算法。由于这种算法需要用到一个很生僻的数学公式,因此很少有面试官会要求我们掌握。不过以防不时之需,我们还是简要介绍一下这种算法。
在介绍这种方法之前,我们先介绍一个数学公式:
这个公式用数学归纳法不难证明,感兴趣的读者不妨自己证明一下。有了这个公式,我们只需要求得矩阵即可得到f(n)。现在的问题转为如何求矩阵的乘方。如果只是简单地从0开始循环,n次方需要n次运算,那其时间复杂度仍然是O(n),并不比前面的方法快。但我们可以考虑乘方的如下性质:
从上面的公式我们可以看出,我们想求得n次方,就要先求得n/2次方,再把n/2次方的结果平方一下即可。这可以用递归的思路实现。
由于很少有面试官要求编程实现这种思路,本书中不再列出完整的代码,感兴趣的读者请参考附带的源代码。不过这种基于递归用O(logn)的时间求得n次方的算法却值得我们重视。我们在面试题11数值的整数次方中再详细讨论这种算法。
解法比较
用不同的方法求解斐波那契数列的时间效率大不相同。第一种基于递归的解法虽然直观但时间效率很低,在实际软件开发中不会用这种方法,也不可能得到面试官的青睐。第二种方法把递归的算法用循环实现,极大地提高了时间效率。第三种方法把求斐波那契数列转换成求矩阵的乘方,是一种很有创意的算法。虽然我们可以用O(logn)求得矩阵的n次方,但由于隐含的时间常数较大,很少会有软件采用这种算法。另外,实现这种解法的代码也很复杂,不太适用面试。因此第三种方法不是一种实用的算法,不过应聘者可以用它来展示自己的知识面。
除了面试官直接要求编程实现斐波那契数列之外,还有不少面试题可以看成是斐波那契数列的应用,比如:
题目二:一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
首先我们考虑最简单的情况。如果只有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(n-2)。分析到这里,我们不难看出这实际上就是斐波那契数列了。
源代码:
本题完整的源代码详见09_Fibonacci项目。
测试用例:
- 功能测试(如输入3、5、10等)。
- 边界值测试(如输入0、1、2)。
- 性能测试(输入较大的数字,如40、50、100等)。
本题考点:
- 考查对递归、循环的理解及编码能力。
- 考查对时间复杂度的分析能力。
- 如果面试官采用的是青蛙跳台阶的问题,那同时还在考查应聘者的数学建模能力。
本题扩展:
在青蛙跳台阶的问题中,如果把条件改成:一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级,此时该青蛙跳上一个n级的台阶总共有多少种跳法?我们用数学归纳法可以证明f(n)=2n-1。
相关题目:
我们可以用2×1(图2.13的左边)的小矩形横着或者竖着去覆盖更大的矩形。请问用8个2×1的小矩形无重叠地覆盖一个2×8的大矩形(图2.13的右边),总共有多少种方法?
图2.13 一个2×1的矩形和2×8的矩形
我们先把2×8的覆盖方法记为f(8)。用第一个1×2小矩形去覆盖大矩形的最左边时有两个选择,竖着放或者横着放。当竖着放的时候,右边还剩下2×7的区域,这种情形下的覆盖方法记为f(7)。接下来考虑横着放的情况。当1×2的小矩形横着放在左上角的时候,左下角必须和横着放一个1×2的小矩形,而在右边还还剩下2×6的区域,这种情形下的覆盖方法记为f(6),因此f(8)=f(7)+f(6)。此时我们可以看出,这仍然是斐波那契数列。
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论