[关闭]
@chyoo1991 2015-09-07T01:17:30.000000Z 字数 544 阅读 1360

《剑指Offer系列》斐波那契数列的问题

coding 斐波那契数列


见书73页。

此处重新复习了下递归和迭代的不同。

递归写起来比较简洁。但是,因为递归是不断调用函数,调用函数要入栈出栈一些局部变量、函数返回地址等。这样上下文的切换,会带来过多的时间开销。而且会带来另一个问题:栈溢出。因此相同条件下会比循环的效率低很多。

斐波那契数列的递归版

  1. public class Fib {
  2. public static int fb(int n){
  3. if(n <= 0) //注意小于0的情况
  4. return 0;
  5. if(n == 1) //递归出口
  6. return 1;
  7. return fb(n - 1) + fb(n - 2);
  8. }
  9. }

这种写法会造成很多函数的重复调用,性能很低。实际上可以把中间结果保存起来,通过查取而不是继续调用函数迭代的方式解决。

迭代版

  1. public class Fib {
  2. public static long fb(int n){
  3. if(n <= 0)
  4. return 0;
  5. if(n == 1)
  6. return 1;
  7. long pre = 0;
  8. long cur = 1;
  9. for(int i = 2; i <= n; i++) {
  10. long tmp = pre + cur;
  11. pre = cur;
  12. cur = tmp;
  13. }
  14. return cur;
  15. }
  16. }

注意青蛙跳台阶的问题,就是用斐波那契数列来解决的。另有方块覆盖的问题,也是斐波那契数列来解决。

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注