求解斐波那契数列的第n项

  对于Fibonacci数列,1,1,2,3,5,8,12,...求解第n项值,我们通常用的是递归算法,即递推式f(n) = f(n-1)+f(n-2).然而这其实是一种效率极低的算法,当n达到41时,就已经需要1s左右,随着n的增加,时间是指数级增长的。

  因为该递归算法有太多的重复计算,如下图所示,所用时间T(n) = T(n-1)+T(n-2)+Θ(1),可以知道T(n)有Ω((3/2)n)的下界,T(n)<O(2^n),可以看到这是指数级的时间复杂度。

             

  具体代码实现如下:

Elemtype Fibonacci(int n)
{
    if(n==1||n==2)
        return 1;
    else
        return Fibonacci(n-1)+Fibonacci(n-2);
}

  基于这种情况,我们首先想到的就是使用迭代法改写,代码如下所示:

Elemtype Fibonacci_Iterate(int n)
{
    if(n==1||n==2) return 1;
    Elemtype f1 = 1,f2 = 1;
    for(int j=3;j<=n;++j){
        Elemtype temp = f1+f2;
        f1 = f2;
        f2 = temp;
    }
    return f2;
}

  迭代法具有O(n)的时间复杂度。

  其实斐波那契数列还有一种O(logn)的算法,那就是用矩阵乘法,如下图所示,该公式可以由归纳法证明。用这个公式求F(n)则可以用分治法,求矩阵的n次方我们只需求n/2次方,然后对其结果再进行一次矩阵乘法。如果n的是奇数,我们就先对n-1做该计算,在将其结果与矩阵matrix进行一次矩阵乘法。假设求F(n)需要时间T(n),T(n) = T(n/2)+Θ(1),所以其时间复杂度为O(logn).

                  

  C语言代码实现如下,每当递归返回时,free掉下一层申请的内存。

Elemtype matrix[4] = {1,1,1,0};

Elemtype* MultipMatrix(Elemtype *m1,Elemtype *m2)
{
    Elemtype *ret = (Elemtype*)malloc(sizeof(Elemtype)*4);
    ret[0] = m1[0]*m2[0]+m1[1]*m2[2];
    ret[1] = m1[0]*m2[1]+m1[1]*m2[3];
    ret[2] = m1[2]*m2[0]+m1[3]*m2[2];
    ret[3] = m1[2]*m2[1]+m1[3]*m2[3];
    return ret;
}    

Elemtype* Fibonacci_Matrix(int n)
{
    if(n==1) return matrix;
    Elemtype *temp = Fibonacci_Matrix(n >> 1);
    Elemtype *ret = NULL;
    if(n & 0x1){
        ret = MultipMatrix(MultipMatrix(temp,temp),matrix);
//        return MultipMatrix(MultipMatrix(temp,temp),matrix);
    }
    else{
        ret = MultipMatrix(temp,temp);
//        return MultipMatrix(temp,temp);
    }
    if(temp!=matrix)
        free(temp);
    return ret;
}
//matrix method

  对于迭代法和矩阵法,当n的规模越大,优势就越明显,当我用如下测试代码,所用时间约为0.17s,而改用迭代法实现的代码,用时达到了4s以上。

  int n = 1000000;
    start = clock();
    for(int i=0;i<1000;++i){
        Elemtype *temp = Fibonacci_Matrix(n);
        printf("%lld\n",temp[1]);
//        printf("%lld\n",Fibonacci(n));
//        printf("%lld\n",Fibonacci_Iterate(n));
    }
    end = clock();

    double t = ((double)(end-start))/CLK_TCK;
    printf("%f",t);

  总结,如果我们的n的规模不是很大,则可以用迭代法,因为这种算法实现相对容易。当n规模很大时,则最好使用矩阵法,当然,此时的F(n)早已超出了C语言long long的范围,需要想办法另外实现更大整数的表示。

  C语言的动态内存申请和释放使代码容易出错,所以可以考虑使用C++的智能指针来代替,或者定义一个矩阵类,实现=,*等矩阵运算。

时间: 07-27

求解斐波那契数列的第n项的相关文章

poj 3070 Fibonacci (矩阵快速幂求斐波那契数列的第n项)

题意就是用矩阵乘法来求斐波那契数列的第n项的后四位数.如果后四位全为0,则输出0,否则 输出后四位去掉前导0,也...就...是...说...输出Fn%10000. 题目说的如此清楚..我居然还在%和/来找后四位还判断是不是全为0还输出时判断是否为0然后 去掉前导0.o(╯□╰)o 还有矩阵快速幂的幂是0时要特判. P.S:今天下午就想好今天学一下矩阵乘法方面的知识,这题是我的第一道正式接触矩阵乘法的题,欧耶! #include<cstdio> #include<iostream>

用递归法计算斐波那契数列的第n项

   斐波纳契数列(Fibonacci Sequence)又称黄金分割数列,指的是这样一个数列:1.1.2.3.5.8.13.21.--在数学上,斐波纳契数列以如下被以递归的方法定义:F0=0,F1=1,Fn=F(n-1)+F(n-2)(n>=2,n∈N*)在现代物理.准晶体结构.化学等领域,斐波纳契数列都有直接的应用,为此,美国数学会从1960年代起出版了<斐波纳契数列>季刊,专门刊载这方面的研究成果. [Fibonacci.cpp] #include<iostream>#

c语言:写一个函数,输入n,求斐波拉契数列的第n项(5种方法,层层优化)

写一个函数,输入n,求斐波拉契数列的第n项. 斐波拉契数列:1,1,2,3,5,8...,当n大于等于3时,后一项为前面两项之和. 解:方法1:从斐波拉契数列的函数定义角度编程 #include<stdio.h> int fibonacci(int n) { int num1=1, num2=1, num3=0,i; if (n <= 2) { printf("斐波拉契数列的第%d项为:%d\n",n,num1); } else { for (i = 2; i <

求斐波那契数列的相邻两项的比值,精确到小数后三位。

未完成,只能假设知道是9和10代入. 代码如下: package zuoye; import java.math.BigDecimal; /* * 求斐波那契数列的相邻两项的比值,精确到小数后三位. * p1,p2,p3......pi,pj,...求pi/pj * 1 1 2 3 5 8 13 * 5/8,8/13,...收敛 */ public class Test { static double feibo(int x){ if(x==1||x==2) return 1; return f

51nod 1242 斐波那契数列的第N项(矩阵快速幂)

1242 斐波那契数列的第N项 基准时间限制:1 秒 空间限制:131072 KB 分值: 0 难度:基础题  收藏  关注 斐波那契数列的定义如下: F(0) = 0 F(1) = 1 F(n) = F(n - 1) + F(n - 2) (n >= 2) (1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, ...) 给出n,求F(n),由于结果很大,输出F(n) % 1000000009的结果即可. Input 输入1个数n(1 <=

1242 斐波那契数列的第N项

1242 斐波那契数列的第N项  基准时间限制:1 秒 空间限制:131072 KB 分值: 0 难度:基础题 斐波那契数列的定义如下: F(0) = 0 F(1) = 1 F(n) = F(n - 1) + F(n - 2) (n >= 2) (1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, ...) 给出n,求F(n),由于结果很大,输出F(n) % 1000000009的结果即可. Input 输入1个数n(1 <= n <

python脚本10_打印斐波那契数列的第101项

#打印斐波那契数列的第101项 a = 1 b = 1 for count in range(99): a,b = b,a+b else: print(b) 方法2: #打印斐波那契数列的第101项 a = 1 b = 1 for i in range(2,101): if i == 100: print(a+b) b += a a = b-a 原文地址:https://www.cnblogs.com/KunGe-13/p/10204841.html

【编程小题目1】求解斐波拉契数列问题

题目:古典问题:有一对兔子,从出生后第3个月起每个月都生一对兔子,小兔子长到第三个月后每个月又生一对兔子,假如兔子都不死,问每个月的兔子总数为多少? 程序分析: 兔子的规律为数列1,1,2,3,5,8,13,21.... 斐波那契数列又因数学家列昂纳多·斐波那契以兔子繁殖为例子而引入,故又称为“兔子数列”.Fibonacci 数列定义:n = 1,2 时,fib(n) = 1n > 2 时,fib(n) = fib(n-2) + fib(n-1) // 递归算法求解Fibonacci 数列 #i

(矩阵快速幂)51NOD 1242斐波那契数列的第N项

斐波那契数列的定义如下: F(0) = 0 F(1) = 1 F(n) = F(n - 1) + F(n - 2) (n >= 2) (1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, ...) 给出n,求F(n),由于结果很大,输出F(n) % 1000000009的结果即可. 输入 输入1个数n(1 <= n <= 10^18). 输出 输出F(n) % 1000000009的结果. 输入样例 11 输出样例 89解:由于斐波那