剑指Offer面试题:8.斐波那契数列
2023-04-18 12:30:56 时间
一、题目:斐波那契数列
题目:写一个函数,输入n,求斐波那契(Fibonacci)数列的第n项。斐波那契数列的定义如下:
二、效率很低的解法
很多C/C++/C#/Java语言教科书在讲述递归函数的时候,大多都会用Fibonacci作为例子,因此我们会对这种解法烂熟于心:
public static long FibonacciRecursively(uint n) { if (n <= 0) { return 0; } if (n == 1) { return 1; } return FibonacciRecursively(n - 1) + FibonacciRecursively(n - 2); }
上述递归的解法有很严重的效率问题,通过求解第10项的调用过程图来分析:
从上图中不难发现:在这棵树中有很多结点是重复的,而且重复的结点数会随着n的增大而急剧增加,这意味计算量会随着n的增大而急剧增大。事实上,用递归方法计算的时间复杂度是以n的指数的方式递增的。
三、实用循环的解法
改进的方法并不复杂。上述递归代码之所以慢是因为重复的计算太多,我们只要想办法避免重复计算就行了。这里的办法是从下往上计算,首先根据f(0)和f(1)算出f(2),再根据f(1)和f(2)算出f(3)……依此类推就可以算出第n项了。很容易理解,这种思路的时间复杂度是O(n)。
public static long FibonacciIteratively(uint n) { int[] result = { 0, 1 }; if (n < 2) { return result[n]; } long fibNMinusOne = 1; long fibNMinusTwo = 0; long fibN = 0; for (uint i = 2; i <= n; i++) { fibN = fibNMinusOne + fibNMinusTwo; fibNMinusTwo = fibNMinusOne; fibNMinusOne = fibN; } return fibN; }
四、单元测试
(1)单元测试用例
[TestMethod] public void FibonacciTest1() { Assert.AreEqual(FibonaaciHelper.FibonacciIteratively(0),0); } [TestMethod] public void FibonacciTest2() { Assert.AreEqual(FibonaaciHelper.FibonacciIteratively(1), 1); } [TestMethod] public void FibonacciTest3() { Assert.AreEqual(FibonaaciHelper.FibonacciIteratively(2), 1); } [TestMethod] public void FibonacciTest4() { Assert.AreEqual(FibonaaciHelper.FibonacciIteratively(3), 2); } [TestMethod] public void FibonacciTest5() { Assert.AreEqual(FibonaaciHelper.FibonacciIteratively(4), 3); } [TestMethod] public void FibonacciTest6() { Assert.AreEqual(FibonaaciHelper.FibonacciIteratively(5), 5); } [TestMethod] public void FibonacciTest7() { Assert.AreEqual(FibonaaciHelper.FibonacciIteratively(6), 8); } [TestMethod] public void FibonacciTest8() { Assert.AreEqual(FibonaaciHelper.FibonacciIteratively(7), 13); } [TestMethod] public void FibonacciTest9() { Assert.AreEqual(FibonaaciHelper.FibonacciIteratively(8), 21); } [TestMethod] public void FibonacciTest10() { Assert.AreEqual(FibonaaciHelper.FibonacciIteratively(9), 34); } [TestMethod] public void FibonacciTest11() { Assert.AreEqual(FibonaaciHelper.FibonacciIteratively(10), 55); } [TestMethod] public void FibonacciTest12() { Assert.AreEqual(FibonaaciHelper.FibonacciIteratively(40), 102334155); }
(2)单元测试结果
①测试通过结果
②代码覆盖率
相关文章
- 当iPhone不再神奇,频繁人事变动显露苹果的艰难抉择
- Google意外发布了Fuchsia OS的第一个“候选版本”
- Facebook开发AI语音助手,或是“钱途”未卜
- 那些年,我们一起卸载过的软件…
- 苹果产品的三种死法
- 刚入行做UI设计,需要考虑哪些问题?
- iPhone全线降价后,之前买贵的怎么退差价?
- 由“硬”变“软”的苹果这次能成功吗?
- 没有硬件的苹果发布会:中年危机的解药
- 苹果发布会亮点汇总:这些东西值得一看
- 十多年后,我们终于看到了初代 iPhone 原型机巨大的红色开发板
- 苹果进行iPhone问世后重大转型:硬件时代转向互联网服务
- 新一代iPad真香,但苹果重回昔日巅峰还差得远
- 继苹果iCloud服务出现大面积瘫痪之后 Siri也中招了
- 另一种绕过 Android P以上非公开API限制的办法
- 专利曝光!谷歌即将推出可折叠智能手机
- 苹果宣布今年WWDC将于6月3日举行 新系统要来了
- css中z-index属性
- css中translate函数的用法
- css中transition方法的介绍