Cracking the coding interview--Q8.1

January 8, 2013
作者:Hawstein
出处:http://hawstein.com/posts/8.1.html
声明:本文采用以下协议进行授权: 自由转载-非商用-非衍生-保持署名|Creative Commons BY-NC-ND 3.0 ,转载请注明作者及出处。

题目

原文:

Write a method to generate the nth Fibonacci number.

译文:

写一个函数来产生第n个斐波那契数。

解答

斐波那契数列的定义如下:

f(1) = f(2) = 1;
f(n) = f(n-1) + f(n-2);

这个定义是递归的,因此很容易根据以上的定义写出它的递归解法, 由于这个数列的递增速度飞快XD,我们先重定义一下long long好方便使用:

typedef long long ll;

递归版本:

ll fib(ll n){
    if(n < 1) return -1;
    if(n == 1 || n == 2) return 1;
    else return fib(n-1) + fib(n-2);
}

当然了,根据定义我们也可以很容易地写出它的非递归版本(迭代版本):

ll fib1(ll n){
    if(n < 1) return -1;
    if(n == 1 || n == 2) return 1;
    ll a = 1, b = 1;
    for(ll i=3; i<=n; ++i){
        ll c = a + b;
        a = b;
        b = c;
    }
    return b;
}

空间复杂度O(1),时间复杂度O(n),看起来既简单又快速。可是,我们还有更快的解法。 根据上面的递推公式,我们可以得到它的矩阵版本:

从上图可以看出,写成矩阵递推形式,可以让我们一推到底。最后的f(1)=f(2)=1, 因此,这个问题就转换成了,如何求矩阵的幂。当然了,要快速,不然就没有什么意义了。 我们先把问题退化一下,先不考虑求矩阵的幂,而是求一个整数的幂,这个够简单的吧。

先来看看最naive的解法:(方便起见,这里假设n为非负数,不对n小于0的情况做讨论)

ll pow(ll m, ll n){
    ll res = 1;
    for(ll i=0; i<n; ++i)
        res *= m;
    return res;
}

时间复杂度O(n)。现在让我们来考虑一种更快的方法,假设我们要计算m^13 , 然后我们把指数13写成二进制形式13=1101,一开始结果res=1.我们要计算的幂可以写成:

m^13 = m^1 * m^4 * m^8

我们可以很直观的得出,如果指数13的二进制形式1101中的某一位为1,那么, res就去乘以那一位对应的一个数。比如,1101从低位起,第1位为1,那么res乘以m^1 , 第二位为0,res不需要乘以m^2 ,第三位为1,res乘以m^4 ,第四位为1,res乘以m^8 , 最后得到的就是:

res = m^1 * m^4 * m^8

而且由于每次res去乘以的数(如果该位为0则不乘)都是上一次那个数的平方, 所以,这个数我用完一次,就对它取平方,准备下一次的使用即可。看代码:

ll pow1(ll m, ll n){
    ll res = 1;
    while(n > 0){
        if(n&1) res *= m;
        m *= m;
        n >>= 1;
    }
    return res;
}

时间复杂度O(logn),正是我们想要的快速版本。OK, 这时候如果让你快速求矩阵的幂,是不是很简单了?只需要将实数乘法改成矩阵乘法即可。

void pow(ll s[2][2], ll a[2][2], ll n){
    while(n > 0){
        if(n&1) mul(s, s, a);
        mul(a, a, a);
        n >>= 1;
    }
}

基本上是一模一样的,只不过由于计算结果是矩阵,不能直接用return进行返回, 而是在函数的参数列表中返回。矩阵乘法函数如下(只考虑2*2的矩阵乘法)

void mul(ll c[2][2], ll a[2][2], ll b[2][2]){
    ll t[4];
    t[0] = a[0][0]*b[0][0] + a[0][1]*b[1][0];
    t[1] = a[0][0]*b[0][1] + a[0][1]*b[1][1];
    t[2] = a[1][0]*b[0][0] + a[1][1]*b[1][0];
    t[3] = a[1][0]*b[0][1] + a[1][1]*b[1][1];
    c[0][0] = t[0];
    c[0][1] = t[1];
    c[1][0] = t[2];
    c[1][1] = t[3];
}

于是,求斐波那契数列第n项的O(logn)解法如下:

ll fib2(ll n){
    if(n < 1) return -1;
    if(n == 1 || n == 2) return 1;

    ll a[2][2] = { {1, 1}, {1, 0} };
    ll s[2][2] = { {1, 0}, {0, 1} };
    pow(s, a, n-2);
    return s[0][0] + s[0][1];
}

完整代码如下:

#include <iostream>
using namespace std;

typedef long long ll;
ll fib(ll n){
    if(n < 1) return -1;
    if(n == 1 || n == 2) return 1;
    else return fib(n-1) + fib(n-2);
}
ll fib1(ll n){
    if(n < 1) return -1;
    if(n == 1 || n == 2) return 1;
    ll a = 1, b = 1;
    for(ll i=3; i<=n; ++i){
        ll c = a + b;
        a = b;
        b = c;
    }
    return b;
}
void mul(ll c[2][2], ll a[2][2], ll b[2][2]){
    ll t[4];
    t[0] = a[0][0]*b[0][0] + a[0][1]*b[1][0];
    t[1] = a[0][0]*b[0][1] + a[0][1]*b[1][1];
    t[2] = a[1][0]*b[0][0] + a[1][1]*b[1][0];
    t[3] = a[1][0]*b[0][1] + a[1][1]*b[1][1];
    c[0][0] = t[0];
    c[0][1] = t[1];
    c[1][0] = t[2];
    c[1][1] = t[3];
}
void pow(ll s[2][2], ll a[2][2], ll n){
    while(n > 0){
        if(n&1) mul(s, s, a);
        mul(a, a, a);
        n >>= 1;
    }
}
ll fib2(ll n){
    if(n < 1) return -1;
    if(n == 1 || n == 2) return 1;

    ll a[2][2] = { {1, 1}, {1, 0} };
    ll s[2][2] = { {1, 0}, {0, 1} };
    pow(s, a, n-2);
    return s[0][0] + s[0][1];
}
int main(){
    for(int i=1; i<20; ++i)
        cout<<fib(i)<<" ";
    cout<<endl;
    for(int i=1; i<20; ++i)
        cout<<fib1(i)<<" ";
    cout<<endl;
    for(int i=1; i<20; ++i)
        cout<<fib2(i)<<" ";
    cout<<endl;
    return 0;
}

全书题解目录:

Cracking the coding interview–问题与解答

全书的C++代码托管在Github上:

https://github.com/Hawstein/cracking-the-coding-interview