算法学习之斐波那契数列

Jackey C/C++ 737 次浏览 , , 没有评论

什么是斐波那契数列?

斐波那契数列(Fibonacci sequence),又称黄金分割数列,因数学家莱昂纳多·斐波那契(Leonardo Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”,指的是这样一个数列:0、1、1、2、3、5、8、13、21、34、……在数学上,斐波那契数列以如下被以递推的方法定义:F(0)=0,F(1)=1, F(n)=F(n - 1)+F(n - 2)(n ≥ 2,n ∈ N*)在现代物理、准晶体结构、化学等领域,斐波纳契数列都有直接的应用,为此,美国数学会从 1963 年起出版了以《斐波纳契数列季刊》为名的一份数学杂志,用于专门刊载这方面的研究成果。 —— 以上来自百度百科

斐波那契数列代码实现

// 时间复杂度:O2^n
int fib(int n) {
    if (n == 0)
        return 0;

    if (n == 1)
        return 1;

    return fib(n - 1) + fib(n - 2);
}

int main() {
    int n = 10;
    time_t startTime = clock();
    int res = fib(n);
    time_t endTime = clock();

    cout<<"fib("<<n<<") = "<<res<<endl;
    cout<<"time : "<<double(endTime - startTime)/CLOCKS_PER_SEC<<" s"<<endl;

    return 0;
}

斐波那契数列代码优化

vector<int> memo;
int num = 0;

// 记忆化搜素
// 算法复杂度:ON
int fib(int n) {

    num++;

    if (n == 0)
        return 0;

    if (n == 1)
        return 1;

    if (memo[n] == -1)
        memo[n] = fib(n - 1) + fib(n - 2);

    return memo[n];
}

int main() {

    num = 0;

    int n = 1000;
    memo = vector<int>(n + 1, -1);

    time_t startTime = clock();
    int res = fib(n);
    time_t endTime = clock();

    cout<<"fib("<<n<<") = "<<res<<endl;
    cout<<"time : "<<double(endTime - startTime)/CLOCKS_PER_SEC<<" s"<<endl;
    cout<<"run function fib() "<<num<<" times"<<endl;

    return 0;
}

斐波那契数列之动态规划法

// 动态规划
int fib2(int n) {
    vector<int> memo2(n + 1, -1);

    memo2[0] = 0;
    memo2[1] = 1;
    for (int i = 2; i <=n ; ++i) {
        memo2[i] = memo2[i - 1] + memo2[i - 2];
    }

    return memo2[n];
}

int main() {

    num = 0;

    int n = 40;
    memo = vector<int>(n + 1, -1);

    time_t startTime = clock();
    int res = fib2(n);
    time_t endTime = clock();

    cout<<"fib("<<n<<") = "<<res<<endl;
    cout<<"time : "<<double(endTime - startTime)/CLOCKS_PER_SEC<<" s"<<endl;
    cout<<"run function fib() "<<num<<" times"<<endl;

    return 0;
}

 

发表评论

您的电子邮箱地址不会被公开。

Go