斐波那契数(Fibonacci)

来自维基百科的定义：

斐波那契數的特點是每一個數都是前二個數的和。頭二項是0和1，此數列的前幾項如下： 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987…

斐波那契数的图示：

数学计算公式（Online LaTex）：

将数学计算公式转为代码：

#include <math.h>

double fibonacci(int n)
{
    double a = (1 + sqrt(5)) / 2;
    double b = (1 - sqrt(5)) / 2;
    return (pow(a, n) - pow(b, n)) / sqrt(5);
}

递归算法（时间复杂度过大）：

double fibonacci(int n)
{
    if (n == 1)
        return n;
    else
        return fibonacci(n - 1) + fibonacci(n - 2);
}