降维打击面试题系列：生成函数（二）斐波那契数列的生成函数

在上一篇中，我们尝试用生成函数巧妙地处理了无穷长度的序列。这一技巧看上去非常有用。于是我们可以尝试使用生成函数来处理数列问题。

我们的第一个案例，就是系列开头提到的青蛙跳台阶问题：

青蛙跳台阶问题：一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

这个问题非常经典，我们分析一下：假如青蛙要跳上第n级台阶，要么从n-1阶跳上来，要么从n级跳上来。

于是有：Fn=Fn−1+Fn−2F_n = F_{n - 1} + F_{n - 2}Fn​=Fn−1​+Fn−2​

这个递推公式是经典的斐波那契数列。

斐波那契数列是非常经典的数列，它有很多"外衣"，比如，斐波那契数列最初用于解决兔子繁殖问题。

假设有一对兔子，长两个月它们就算长大成年了。然后以后每个月都会生出1对兔子，生下来的兔子也都是长两个月就算成年，然后每个月也都会生出1对兔子了。这里假设兔子不会死，每次都是只生1对兔子。求n月后，兔子总数。

斐波那契数列还跟黄金分割有密不可分的联系：

有一 1x2 的长方形，我们以其长边为边，做一个正方形，与原有长方形拼接，形成一个新的长方形，重复此过程，求n次后长方形长边的长度。

按照这样重复，这个长方形的比例会越来越接近黄金分割。

如果我们单看题面，你能否分辨出青蛙跳台阶和这些本质上是同一问题呢？从现实问题中抽象出算法问题，并没有什么捷径，只能多看多练习，我们所讲的算法套路，一般都是针对从算法问题到算法阶段的。

斐波那契数列是一个经典的数学问题，处理它的最佳算法已经被研究得非常充分了。这里我们首先从生成函数的角度介绍一下求解斐波那契数列的方法。

生成函数

我们正式定义一下斐波那契数列：

这个数列是：

我们把它“挂”到一个生成函数上。这样，我们就得到了一个生成函数：

这仍然是个无穷的数列，我们参考上一篇中对生成函数的处理技巧，考虑一下如何消去无穷项，使它变成一个简单的函数。

我们看，xnx^nxn项的系数是FnF_nFn​，我们能否利用递推关系Fn=Fn−1+Fn−2F_n = F_{n - 1} + F_{n - 2}Fn​=Fn−1​+Fn−2​来把无穷项消掉呢？

思考一下，我们发现，可以分别在等式两边乘以xxx和x2x^2x2，这样就能造成数列“移位”。

之后与原式相减，就可以消去无穷项：

再整理一下，得到：

这个G(x)看上去又非常友好了，于是我们可以暴力使用泰勒级数展开。

www.wolframalpha.com/input?i=%5C…

于是我们就得到了斐波那契数列的通项公式。

这个公式中存在n次幂，所以它的时间复杂度不能达到O(1)O(1)O(1)，但是它也不需要O(n)O(n)O(n)。有一种经典算法，叫做快速幂算法，可以利用乘法的结合律，使得幂运算达到O(log(n))O(log(n))O(log(n))的时间复杂度。

快速幂算法

接下来我们来讲解快速幂算法计算xnx^nxn

首先我们考虑简单的情况，假设n是2的整数次幂，比如1024。

那么显然，我们只需要做10次平方运算，就可以得到x1024x^{1024}x1024。

但是，如果不是整数次幂呢？比如 x1025x^{1025}x1025。

答案是，我们可以进行一定的“微调”，x1025=x1024⋅x1x^{1025} = x^{1024} \cdot x^1x1025=x1024⋅x1。

那么，如果是更难“微调”的情况，比如 x1314x^{1314}x1314 又该怎么办呢？

其实，我们只需要把这个数字用二进制表示出来，然后对应其中的1位，乘上相应的倍数即可：

因为求 x^{1024} 的过程中必然要求出比他小的次数，所以只需要选出需要的次数相乘即可。最终代码如下：

const pow = (v, n) => {
    let r = v, m = n - 1, c = v;
    while(m > 0) {
        if(m % 2)
            r = r * c;
        m = m >> 1;
        c = c * c;
    }
    return r;
}

我们也可以把它写成递归的形式，看起来比较简洁：

const pow = (v, n) => n === 1 ? v :
    n % 2 === 0 ? (x => x * x)(pow(v, n / 2)) :
        pow(v, n - 1) * v

矩阵

尽管生成函数求出通项公式可以提供O(log(n))O(log(n))O(log(n))的算法，但是因为这其中涉及浮点运算，在具体性能和精度上都不算好。线性代数中为我们提供了一个更好的算法，利用矩阵乘法。

斐波那契数列递推公式是两项相加，这不好处理，所以我们考虑，给这个数列的每一项添加一点冗余，形成一个矢量数列：

我们不难看出，这样的一个数列，第n项和第n+1项之间的关系是：

如何实现这个向量转换呢？我们看到，这里a和b的幂次都是1，所以这属于一个线性变换，矢量的线性变换可以用矩阵完成：

所以我们这个矢量数列的递推公式可以写成：

通项公式则是：

矩阵乘法符合结合律，所以一样可以用快速幂算法达到O(log(n))O(log(n))O(log(n))的时间复杂度，但我们首先要把快速幂算法改造得更通用一些：

const pow = (v, n, mul = (a, b) => a * b) => {
    let r = v, m = n - 1, c = v;
    while(m > 0) {
        if(m % 2)
            r = mul(r, c);
        m = m >> 1;
        c = mul(c, c);
    }
    return r;
}

这个改进版的快速幂代码，可以允许我们传入一个"乘法运算"，于是我们实现一个二阶矩阵乘法：

const mul = (x, y) => [
    [x[0][0] * y[0][0] + x[0][1] * y[1][0], x[0][0] * y[0][1] + x[0][1] * y[1][1]], 
    [x[1][0] * y[0][0] + x[1][1] * y[1][0], x[1][0] * y[0][1] + x[1][1] * y[1][1]]
];

为了避免我们再实现一个向量和矩阵的乘法，我们把初始向量补充为一个等效的矩阵：

最后我们根据矩阵的通项公式写出最终代码：

const fibnacci = n => mul([[1,1],[0,0]], pow([[0,1],[1,1]], n, mul))[0][0];

倍增公式

除了上面两种解法，斐波那契数列还有一种编写代码更为简洁的写法，我们可以利用斐波那契数列的倍增公式：

我们有了前面的通项公式，这个公式不难证明。其实比较困难的部分是想到有这个公式，不过数学家先贤们已经帮助我们铺好了路，我们程序员只要想办法用就行了。

这个公式允许我们以大约每次翻倍的速度推进计算斐波那契数列，所以粗略估计利用这个公式可以写出一个O(log(n))O(log(n))O(log(n))的算法。

不过，实际落到代码上，还需要一点斟酌。

首先我们考虑让公式中的m等于n，于是可以得到：

但是，我们发现这个公式只适用于偶数，并且我们需要Fn−1,Fn,Fn+1F_{n - 1}, F_n, F_{n + 1}Fn−1​,Fn​,Fn+1​ 三个值才能求出 n 的 2 倍项。如果我们直接使用这个公式递归，恐怕效果不会好。

但是我们发现，其实 Fn−1,Fn,Fn+1F_{n - 1}, F_n, F_{n + 1}Fn−1​,Fn​,Fn+1​ 三个属于相邻项，也就是说，根据斐波那契数列的递推公式，只需要有其中两项，我们就可以求出另外一项。

受到前面矩阵运算把相邻两项视为一个向量的启发，我们能否每次递归都算出相邻两项呢？

我们再把m设为n+1,可以得到：

考虑到据斐波那契数列的递推公式 Fn−1=Fn+1−FnF_{n - 1} = F_{n + 1} - F_nFn−1​=Fn+1​−Fn​， 我们代入后可以得到：

这样，我们就有了从 Fn,Fn+1F_n, F_{n + 1} Fn​,Fn+1​通向 F2n,F2n+1F_{2n}, F_{2n + 1} F2n​,F2n+1​的途径。

最终，我们参考快速幂的思路，据此公式编写JS代码：

const fibnacci = n => {
    const fib = n =>
        n === 0 ? [0, 1] :
        n % 2 === 0 ?
            (([a, b]) => [(b - a) * a + a * b, a * a + b * b])(fib(n / 2)) :
            (([a, b]) => [b, a + b])(fib(n - 1))
    return fib(n)[0];
}

结语

在处理斐波那契数列问题上，三种方法可以说各有优势，矩阵和生成函数具有极好的通用性，能够应对各种不同的变体。倍增公式则胜在代码简洁。在后面的部分，我会带你更充分利用矩阵和生成函数的关联性，来解决更广泛的组合问题。