乐趣区

关于java:面试题精选神奇的斐波那契数列

jiezi

斐波那契数列，其最开始的几项是 0、1、1、2、3、5、8、13、21、34……，前面的每一项是前两项之和，事实上，斐波那契在数学上有本人的严格递归定义。

f0 = 0
f1 = 1
f(n) = f(n-1) + f(n-2)

斐波那契数列其实有很多乏味的性质，比方你拿斐波那契里每项数为半径绘制 1 / 4 圆弧，你就会失去驰名的 黄金螺旋线 。

上图只是绘制到了 10 多项，如果持续绘制，会变成上面这样。。

另外斐波那契数还有一个神奇的性质，f(n-1)/f(n)约等于黄金分割比例，n 越大，其越靠近黄金分割比 0.6180339887……。

扯远了，回到明天的正题，如何求斐波那契数列第 n 项，如果作为面试题的话，也能够考查候选人很多方面，比方递归、优化、数学…… 当然当初大厂面试时很大可能也不会间接出斐波那契了，而是可能呈现其变形，文末会给出几个相干参考题。

求解斐波那契数列第 n 项有很多种形式

递归求解

依据其递归定义，咱们很容易写出以下递归函数来计算斐波那契第 n 项。

    private static long fibonacci(int n) {if (n == 0) {return 0L;}
        if (n == 1) {return 1L;}
        return fibonacci(n-1) + fibonacci(n-2); 
    }

尽管按其数学定义来看，代码是没问题，但这种实现效率非常低，存在着大量的反复计算，不信你用你本人电脑执行下fibonacci(30) 试试！哦，对了，如果面试官让你剖析下上述代码的工夫复杂度，你会剖析吗？？

                          fib(5)   
                     /                \
               fib(4)                fib(3)   
             /        \              /       \ 
         fib(3)      fib(2)         fib(2)   fib(1)
        /    \       /    \        /      \
  fib(2)   fib(1)  fib(1) fib(0) fib(1) fib(0)
  /     \
fib(1) fib(0)

像上图中，fib(3) fib(2) 被反复计算屡次，实际上对于任意 n，其 n - 2 节点都会呈现在其左右子树中 。大抵看起来递归求斐波那契数列的工夫复杂度为 O(2^n)，这个也不是准确上界，准确证实见递归求解斐波那契数列的工夫复杂度——几种简洁证实
当然递归版本也有有办法优化的，咱们之前打 ACM 的时候有种办法叫做记忆化搜寻，其本质上就是把计算结果缓存下来，下次用的时候就间接取，而不是反复计算，这样能够防止上述代码中大量的反复计算，能够将其工夫复杂度从 O(2^n) 降至 O(n)。针对下面代码的改变也很简略，你能够本人试试（提醒：就是加个全局数组保障下后果）。

递推求解

咱们在解决问题的时候，逆向思维也很重要，逆向思维往往能找到更高效间接的解决方案。上述递归的形式其实是从后往前计算，事实上咱们能够从前往后计算。竟然咱们已知 f0 和 f1，那咱们就能够算出 f2，紧接着算出 f3 f4，始终到 fn。

    private static long fibonacci(int n) {long[] fb = new long[n+1];
        fb[1] = 1;
        for (int i = 2; i <= n; i++) {fb[i] = fb[i-1] + fb[i-2];
        }
        return fb[n];
    }

不过上述代码仍旧有优化空间。咱们计算 fb[i]只须要 fb[i-1]和 fb[i-2]两项即可，是不是 0 到 i - 3 都白存了！其实 只须要保留长度为 2 的滑动窗口即可，优化后代码如下：

    private static long fibonacci(int n) {if (n < 2) {return n;}
        long fa = 0L;
        long fb = 1L;
        long fc = fa + fb;
        for (int i = 2; i < n; i++) {
            fc = fa + fb; 
            fa = fb;
            fb = fc;
        }
        return fc;
    }

比内公式

其实斐波那契第 n 项是有计算公式的，称为 比内公式 ，如下：

在维基百科 Fibonacci number 上有严格的证实过程，有趣味能够参考下。但这个公式其实并不适宜计算机来计算。首先，根号 5 是个无理浮点数，家喻户晓当今的计算机在解决浮点数时是有精度损失的，另外计算机计算浮点数的速度也比较慢。当然，你也别惦记着把这个公式背下来，你面试过程中不肯定能想起来这个，当然如果你是数学大牛的话，你能够参考下推导过程，间接在面试现场把论断推导进去，必定能唬住大部分面试官的。

矩阵幂运算

下面曾经说了比内公式有低效和精度损失的问题，我这里当然有更牛 x 的计划了，那就是借助矩阵的运算来解决，借助如下公式，咱们能够计算出斐波那契的第 n 项。

如果再进一步，公式能够化简为：

具体推导过程见维基百科 Fibonacci number，当然这里我间接用 octave 验证过了，毫无问题。

>>fb = [1,1;1,0]
fb =
   1   1
   1   0

>>fb^10
ans =
   89   55
   55   34
   
>>fb^30
ans =
   1346269    832040
    832040    514229

小学三年级的时候咱们学过求 n 次方的 疾速幂算法 ，能够把求 n 次方的工夫复杂度从O(n) 升高到 O(log(n))，对于矩阵咱们当然也能够用疾速幂算法(不晓得疾速幂的同学能够去温习下了)。

    // 疾速求矩阵的 n 次方  
    private static long[][] pow(long[][] matrix, int n) {if (n == 1) {return matrix;}
        long[][] res = pow(matrix, n/2);
        res = multi(res, res);
        if (n%2 == 1) {res = multi(res, matrix);
        }
        return res;
    }
    // 两个矩阵相乘 
    private static long[][] multi(long[][] m1,  long[][] m2) {long[][] res = new long[2][2];
        res[0][0] = m1[0][0]*m2[0][0] + m1[0][1]*m2[1][0];
        res[0][1] = m1[0][0]*m2[0][1] + m1[0][1]*m2[1][1];
        res[1][0] = m1[1][0]*m2[0][0] + m1[1][1]*m2[1][0];
        res[1][1] = m1[1][0]*m2[0][1] + m1[1][1]*m2[1][1];
        return res;
    }
    
    public static void main(String[] args) {long[][] fb = {{1,1},{1,0}};
        long[][] res = pow(fb, 10);
        System.out.println(res[0][1]);
    }

上述几种解法把工夫复杂度从 O(2^n)升高到了 O(log(n))，实际上还有 O(1)的解法。斐波那契数列其实是一个增长很快的数列，n 用不了多大就会超过 int 甚至 long 所能示意的范畴 (n 大略几十就会溢出)，所以能够间接存下来，用的时候间接取，用空间换工夫，从而达到 O(1) 的工夫复杂度。

面试题扩大

求斐波那契第 n 项尽管看起来很根底，但它也有着很高级的解法，平庸中蕴藏着不凡。事实上，你当初进来面试，大概率不会遇到面试官间接问你斐波那契，而是其变形题或是和其余内容交融的题，比方：

  1. 你每次能够上 1 级台阶，或者 2 级台阶，问：上到第 n 级台阶总共有多少种不同的门路？
  2. fib(i)对应的是斐波那契的第 i 项，找到所有第 fin(i)个素数 (i<=20)，比方 fib(20) 是 6765，第 6765 个素数是 67931。

欢送关注我的面试专栏面试题精选，永恒收费 继续更新，本专栏会收集我遇到的比拟经典面试题，除了提供详尽的解法外还会从面试官的角度提供扩大题，心愿能帮忙大家找到更好的工作。另外，也征集面试题，如果你遇到了不会的题 私信通知我，有价值的题我会给你出一篇博客。

退出移动版