斐波那契数列的表达式为：

{{\large F \small (n) = \large F \small (n-1) + \large F \small (n-2)}}

其Pascal’s triangle求和表达式为：

{{Fn=\displaystyle\sum_{k=0}^{\frac{n-1}{2}}\dbinom{n-k-1}{k}}}

Ok,有了公式就可以瞎搞。

最慢的写法：

unsigned long fib1(int num){
    if(num<=2)
        return 1;
    else
        return fib1(num-1) +fib1(num-2)
}

时间复杂度大约为:

{{O(2^N)}}

---

使用一叉递归：

unsigned long fib2sFunc(int num, unsigned long a, unsigned long b, unsigned long count)
{
    if(count == num)
        return b;
    return fib2sFunc(num, b, a + b, ++count);
}
unsigned long fib2(int num)
{
    return fib2sFunc(num, 0, 1, 1);
}

时间复杂度为：

{{O(N)}}

---

使用迭代：

unsigned long fib3(int n)
{
    unsigned long x = 0, y = 1;
    for (int j = 1; j < n; j++)
    {
        y = x + y;
        x = y - x;
    }
    return y;
}

时间复杂度同样为：

{{O(N)}}

---

使用矩阵：

class FibMtrxStu
{
public:
    unsigned long mtr[2][2];
    FibMtrxStu(const FibMtrxStu&rhs){
        this->mtr[0][0] = rhs.mtr[0][0];
        this->mtr[0][1] = rhs.mtr[0][1];
        this->mtr[1][0] = rhs.mtr[1][0];
        this->mtr[1][1] = rhs.mtr[1][1];
    }
    FibMtrxStu(unsigned long a, unsigned long b, unsigned long c, unsigned long d){
        this->mtr[0][0] = a;
        this->mtr[0][1] = b;
        this->mtr[1][0] = c;
        this->mtr[1][1] = d;
    }
    FibMtrxStu& operator=(const FibMtrxStu &rhs){
        this->mtr[0][0] = rhs.mtr[0][0];
        this->mtr[0][1] = rhs.mtr[0][1];
        this->mtr[1][0] = rhs.mtr[1][0];
        this->mtr[1][1] = rhs.mtr[1][1];
    return *this;
    }
    friend FibMtrxStu operator*(const FibMtrxStu& lhs, const FibMtrxStu& rhs){
        FibMtrxStu ret(0, 0, 0, 0);
        ret.mtr[0][0] = lhs.mtr[0][0] * rhs.mtr[0][0] + lhs.mtr[0][1] * rhs.mtr[1][0];
        ret.mtr[0][1] = lhs.mtr[0][0] * rhs.mtr[0][1] + lhs.mtr[0][1] * rhs.mtr[1][1];
        ret.mtr[1][0] = lhs.mtr[1][0] * rhs.mtr[0][0] + lhs.mtr[1][1] * rhs.mtr[1][0];
        ret.mtr[1][1] = lhs.mtr[1][0] * rhs.mtr[0][1] + lhs.mtr[1][1] * rhs.mtr[1][1];
        return ret;
    }
};

FibMtrxStu recursion(const FibMtrxStu& m, int num)
{
    if (num == 1)
        return m;
    if (num % 2 == 0)
        return recursion(m*m, num / 2);
    else
        return recursion(m*m, num / 2) * m;
}

unsigned long fib4(int num)
{
    FibMtrxStu FibMtrxStu0(1, 1, 1, 0);
    FibMtrxStu0 = recursion(FibMtrxStu0, num - 1);
    return FibMtrxStu0.mtr[0][0];
}

时间复杂度为：

{{O(\log N)}}

---

使用STL的公式：

unsigned long fib5(int n)
{
    double z = sqrt(5.0);
    double x = (1 + z) / 2;
    double y = (1 - z) / 2;
    return (unsigned long)(pow(x, n) - pow(y, n)) / z + 0.5;
}

这时间复杂度同矩阵：

{{O(\log N)}}