《劍指offer》面試題10：斐波那契數列(含矩陣乘法解法)

更多劍指offer面試習題請點選： 《劍指offer》（第二版）題集目錄索引

斐波那契數指的是這樣一個數列：0、1、1、2、3、5、8、13、21、……

這個數列從第三個數開始，之後的每一個數都由它前的兩數相加得到。

我們知道在程式設計中我們可以用遞歸和疊代兩種方法求指定的斐波那契數，但這兩種方法各有利弊。

差別：遞歸法（時間複雜度O(2^n)）寫出來的代碼可讀性強，就相當于把書上的數學公式 翻譯成代碼，但這種方法效率太慢了，當你求第50個斐波那契數，你的電腦可能得運算十多分鐘。而且遞歸很容易造成棧溢出，每調用一次函數就得開辟一塊空間，而求第50個斐波那契數所調用函數的次數是令人發指，同樣的那在棧上開辟的空間大小也就可想而知，棧溢出就很正常了。

疊代法：（時間複雜度O(N)）相對而言疊代法的運算效率就高的多了，疊代是通過循環來求的，隻要建立3個臨時變量，就能很快的求出斐波那契數，而且速度快的一匹（那怕求第100斐波那契數也隻是一瞬間的事），但疊代法的代碼可讀性較弱，而且初學者也不容易寫出這種代碼。

下面就是這兩種方法的具體實作代碼：

<遞歸法：>

#include <stdio.h>
#include <windows.h>

int fib(int num) 
{
    if (num <= )
        return n;
    else
        return fib(num - ) + fib(num - );
}
           

<疊代法：>
int fib(int num)
{
    int n1 = ;
    int n2 = ;
    int sum = ;

    if (num == )
        return n1;

    while (num > )  //這裡當num<=2時，不進行運算，直接傳回sum的值
    {
        sum = n1 + n2;
        n1 = n2;
        n2 = sum;
        num--;
    }
    return sum;
}
           

斐波那契數列求解高階版：基于矩陣乘法（時間複雜度O(logn)）

數學公式參考下面文章：

http://blog.csdn.net/flyfish1986/article/details/48014523

< code C>

typedef struct Matrix2By2
{
    long long m00;
    long long m01;
    long long m10;
    long long m11;

}Matrix2By2;

Matrix2By2 Mul(Matrix2By2 matrix1, Matrix2By2 matrix2)
{
    Matrix2By2 ret;
    ret.m00 = matrix1.m00 * matrix2.m00 + matrix1.m01 * matrix2.m10;
    ret.m01 = matrix1.m00 * matrix2.m01 + matrix1.m01 * matrix2.m11;
    ret.m10 = matrix1.m10 * matrix2.m00 + matrix1.m11 * matrix2.m10;
    ret.m11 = matrix1.m10 * matrix2.m01 + matrix1.m11 * matrix2.m11;

    return ret;
}

Matrix2By2 MatrixPower(unsigned int n)
{
    Matrix2By2 Init = { , , ,  };

    Matrix2By2 ret;

    if ( == n)
    {
        ret = Init;
    }
    else if ( == (n & )) 
    {
        ret = MatrixPower(n / ); //偶數處理
        ret = Mul(ret, ret);
    }
    else if ( == (n & ))
    {
        ret = MatrixPower((n - ) / ); //奇數處理
        ret = Mul(ret, ret);
        ret = Mul(ret, Init);
    }
    return ret;
}


long long Fibonacci(unsigned int n)
{
    if (n < )
        return n;
    else
    {
        Matrix2By2 ret = MatrixPower(n - );
        return ret.m00;
    }
}
           

擴充題：青蛙跳台階問題

一隻青蛙一次可以跳1級台階，也可以跳2級台階。求該青蛙跳上一個n級的台階總共有多少種跳法。

解題思路：

1. 有1級台階：那就隻有一種跳法；
2. 有2級台階：有兩種跳法；

3. 有n級台階：此時n>=2，那第一跳時隻有兩種跳法。

   ①第一跳跳1級台階，那跳法數目就是後面的n-1級台階的跳法數目；

   ②第二跳跳2級台階，那跳法數目就是後面的n-2級台階的跳法數目；

   ③是以不同跳法的總數目 f(n) = f(n-1) + f(n-2)。

< code >

long long JumpStep(unsigned int n)//遞歸
{
    if (n <= )
        return n;
    else
        return jump_step(n - ) + jump_step(n - );
}

long long JumpStep(unsigned int n)//非遞歸
{
    if (n <= )
        return n;

    long long n1 = ;
    long long n2 = ;
    long long sum = ;

    int i = ;
    while (n > )
    {
        sum = n1 + n2;
        n1 = n2;
        n2 = sum;
        n--;
    }
    return sum;
}
           

青蛙跳台階進階題：如果這隻青蛙一次能跳1級台階，也能跳2級台階……也能跳n級台階，那他跳一個n級的台階，共有幾種跳法？

解題思路：

< code >

long long est_jum_step(unsigned int n)//非遞歸
{

    if (n <= )
        return n;
    else
    {
        n -= ;
        long long sum = ;
        while (n > )
        {
            sum *= ;
            n--;
        }
        return sum;
    }
}

long long est_jum_step(unsigned int n)//遞歸
{
    if (n <= )
        return  n;
    else
        return *est_jum_step(n - );
}
           

這裡還有一個擴充題：鋪瓷磚，于上面一題大同小異。