精华内容
下载资源
问答
  • 斐波那契数列算法分析

    万次阅读 2018-08-13 12:50:47
    斐波那契数列算法分析 背景: 假定你有一雄一雌一对刚出生的兔子,它们在长到一个月大小时开始交配,在第二月结束时,雌兔子产下另一对兔子,过了一个月后它们也开始繁殖,如此这般持续下去。每只
    原文地址为:
    斐波那契数列算法分析
    

    斐波那契数列算法分析

    背景:

    假定你有一雄一雌一对刚出生的兔子,它们在长到一个月大小时开始交配,在第二月结束时,雌兔子产下另一对兔子,过了一个月后它们也开始繁殖,如此这般持续下去。每只雌兔在开始繁殖时每月都产下一对兔子,假定没有兔子死亡,在一年后总共会有多少对兔子?

    在一月底,最初的一对兔子交配,但是还只有1对兔子;在二月底,雌兔产下一对兔子,共有2对兔子;在三月底,最老的雌兔产下第二对兔子,共有3对兔子;在四月底,最老的雌兔产下第三对兔子,两个月前生的雌兔产下一对兔子,共有5对兔子;……如此这般计算下去,兔子对数分别是:1, 1, 2, 3, 5, 8, 13, 21, 34, 55,89, 144, ...看出规律了吗?从第3个数目开始,每个数目都是前面两个数目之和。这就是著名的斐波那契(Fibonacci)数列。

     

    有趣问题:

    1,有一段楼梯有10级台阶,规定每一步只能跨一级或两级,要登上第10级台阶有几种不同的走法?

    答:这就是一个斐波那契数列:登上第一级台阶有一种登法;登上两级台阶,有两种登法;登上三级台阶,有三种登法;登上四级台阶,有五种方法……所以,1235813……登上十级,有89种。

    2,数列中相邻两项的前项比后项的极限是多少,就是问,当n趋于无穷大时,F(n)/F(n+1)的极限是多少?

    答:这个可由它的通项公式直接得到,极限是(-1+5)/2,这个就是所谓的黄金分割点,也是代表大自然的和谐的一个数字。

     

     

    数学表示:

    Fibonacci数列的数学表达式就是:

    F(n) = F(n-1) + F(n-2)

    F(1) = 1

    F(2) = 1

     

    递归程序1

    Fibonacci数列可以用很直观的二叉递归程序来写,用C++语言的描述如下:

    long fib1(int n)

    {

              if (n <= 2)

    {

              return 1;

    }

    else

    {

              return fib1(n-1) + fib1(n-2);

    }

    }

    看上去程序的递归使用很恰当,可是在用VC2005的环境下测试n=37的时候用了大约3s,而n=45的时候基本下楼打完饭也看不到结果……显然这种递归的效率太低了!!

    递归效率分析:

    例如,用下面一个测试函数:

    long fib1(int n, int* arr)

    {

             arr[n]++;

             if (n <= 2)

             {

                  return 1;

             }

             else

             {

                  return fib1(n-1, arr) + fib1(n-2, arr);

             }

    }

    这时,可以得到每个fib(i)被计算的次数:

    fib(10) = 1     fib(9) = 1      fib(8) = 2      fib(7) = 3

    fib(6) = 5      fib(5) = 8      fib(4) = 13    fib(3) = 21

    fib(2) = 34   fib(1) = 55    fib(0) = 34

    可见,计算次数呈反向的Fibonacci数列,这显然造成了大量重复计算。

    我们令T(N)为函数fib(n)的运行时间,当N>=2的时候我们分析可知:

    T(N) = T(N-1) + T(N-2) + 2

    fib(n) = fib(n-1) + fib(n-2)所以有T(N) >= fib(n)归纳法证明可得

    fib(N) < (5/3)^N

    N>4时,fibN>= (3/2)^N

    标准写法:

    显然这个O(3/2)^N 是以指数增长的算法基本上是最坏的情况。

    其实,这违反了递归的一个规则:合成效益法则。

    合成效益法则(Compound interest rule):在求解一个问题的同一实例的时候,切勿在不同的递归调用中做重复性的工作。

    所以在上面的代码中调用fib(N-1)的时候实际上同时计算了fib(N-2)。这种小的重复计算在递归过程中就会产生巨大的运行时间。

     

    递归程序2

    用一叉递归程序就可以得到近似线性的效率,用C++语言的描述如下:

    long fib(int n, long a, long b, int count)

    {

         if (count == n)

             return b;

         return fib(n, b, a+b, ++count);

    }

     

    long fib2(int n)

    {

         return fib(n, 0, 1, 1);

    }

    这种方法虽然是递归了,但是并不直观,而且效率上相比下面的迭代循环并没有优势。

     

    迭代解法:

    Fibonacci数列用迭代程序来写也很容易,用C++语言的描述如下:

    //也可以用数组将每次计算的f(n)存储下来,用来下次计算用(空间换时间)

    long fib3 (int n)

    {

         long x = 0, y = 1;

         for (int j = 1; j < n; j++)

         {

             y = x + y;

             x = y - x;

         }

         return y;

    }

    这时程序的效率显然为ONN = 45的时候<1s就能得到结果。

     

    矩阵乘法

    我们将数列写成:

    Fibonacci[0] = 0Fibonacci[1] = 1

    Fibonacci[n] = Fibonacci[n-1] + Fibonacci[n-2] (n >= 2)

    可以将它写成矩阵乘法形式:

    将右边连续的展开就得到:

    下面就是要用O(log(n))的算法计算:

    显然用二分法来求,结合一些面向对象的概念,C++代码如下:

    class Matrix

    {

    public:

           long matr[2][2];

     

           Matrix(const Matrix&rhs);

           Matrix(long a, long b, long c, long d);

           Matrix& operator=(const Matrix&);

           friend Matrix operator*(const Matrix& lhs, const Matrix& rhs)

           {

                  Matrix ret(0,0,0,0);

                  ret.matr[0][0] = lhs.matr[0][0]*rhs.matr[0][0] + lhs.matr[0][1]*rhs.matr[1][0];

                  ret.matr[0][1] = lhs.matr[0][0]*rhs.matr[0][1] + lhs.matr[0][1]*rhs.matr[1][1];

                  ret.matr[1][0] = lhs.matr[1][0]*rhs.matr[0][0] + lhs.matr[1][1]*rhs.matr[1][0];

                  ret.matr[1][1] = lhs.matr[1][0]*rhs.matr[0][1] + lhs.matr[1][1]*rhs.matr[1][1];

                  return ret;

           }

    };

     

    Matrix::Matrix(long a, long b, long c, long d)

    {

           this->matr[0][0] = a;

           this->matr[0][1] = b;

           this->matr[1][0] = c;

           this->matr[1][1] = d;

    }

     

    Matrix::Matrix(const Matrix &rhs)

    {

           this->matr[0][0] = rhs.matr[0][0];

           this->matr[0][1] = rhs.matr[0][1];

           this->matr[1][0] = rhs.matr[1][0];

           this->matr[1][1] = rhs.matr[1][1];

    }

     

    Matrix& Matrix::operator =(const Matrix &rhs)

    {

           this->matr[0][0] = rhs.matr[0][0];

           this->matr[0][1] = rhs.matr[0][1];

           this->matr[1][0] = rhs.matr[1][0];

           this->matr[1][1] = rhs.matr[1][1];

           return *this;

    }

     

    Matrix power(const Matrix& m, int n)

    {

           if (n == 1)

                  return m;

           if (n%2 == 0)

                  return power(m*m, n/2);

           else

                  return power(m*m, n/2) * m;

    }

     

    long fib4 (int n)

    {

           Matrix matrix0(1, 1, 1, 0);

           matrix0 = power(matrix0, n-1);

           return matrix0.matr[0][0];

    }

    这时程序的效率为Olog(N)

     

    公式解法:

    O1的时间就能求得到F(n)了:

     

    注意:其中[x]表示取距离x最近的整数。

    C++写的代码如下:

    long fib5(int n)

    {

         double z = sqrt(5.0);

         double x = (1 + z)/2;

         double y = (1 - z)/2;

         return (pow(x, n) - pow(y, n))/z + 0.5;

    }

    这个与数学库实现开方和乘方本身效率有关的,我想应该还是在O(log(n))的效率。

     

    总结:

    上面给出了5中求解斐波那契数列的方法,用测试程序主函数如下:

    int main()

    {

         cout << fib1(45) << endl;

         cout << fib2(45) << endl;

         cout << fib3(45) << endl;

         cout << fib4(45) << endl;

    cout << fib5(45) << endl;

         return 0;

    }

    函数fib1会等待好久其它的都能很快得出结果并且相同为1134903170

    而后面两种只有在n = 1000000000的时候会显示出优势。由于我的程序都没有涉及到高精度,所以要是求大数据的话,可以通过取模来获得结果的后4位来测试效率与正确性。

    另外斐波那契数列在实际工作中应该用的很少,尤其是当数据n很大的时候(例如:1000000000),所以综合考虑基本普通的非递归O(n)方法就很好了,没有必要用矩阵乘法。

     

    附录

    程序全部源码:

    #include <iostream>

    #include <vector>

    #include <string>

    #include <cmath>

    #include <fstream>

     

    using namespace std;

     

    class Matrix

    {

    public:

           long matr[2][2];

     

           Matrix(const Matrix&rhs);

           Matrix(long a, long b, long c, long d);

           Matrix& operator=(const Matrix&);

           friend Matrix operator*(const Matrix& lhs, const Matrix& rhs)

           {

                  Matrix ret(0,0,0,0);

                  ret.matr[0][0] = lhs.matr[0][0]*rhs.matr[0][0] + lhs.matr[0][1]*rhs.matr[1][0];

                  ret.matr[0][1] = lhs.matr[0][0]*rhs.matr[0][1] + lhs.matr[0][1]*rhs.matr[1][1];

                  ret.matr[1][0] = lhs.matr[1][0]*rhs.matr[0][0] + lhs.matr[1][1]*rhs.matr[1][0];

                  ret.matr[1][1] = lhs.matr[1][0]*rhs.matr[0][1] + lhs.matr[1][1]*rhs.matr[1][1];

                  return ret;

           }

    };

     

    Matrix::Matrix(long a, long b, long c, long d)

    {

           this->matr[0][0] = a;

           this->matr[0][1] = b;

           this->matr[1][0] = c;

           this->matr[1][1] = d;

    }

     

    Matrix::Matrix(const Matrix &rhs)

    {

           this->matr[0][0] = rhs.matr[0][0];

           this->matr[0][1] = rhs.matr[0][1];

           this->matr[1][0] = rhs.matr[1][0];

           this->matr[1][1] = rhs.matr[1][1];

    }

     

    Matrix& Matrix::operator =(const Matrix &rhs)

    {

           this->matr[0][0] = rhs.matr[0][0];

           this->matr[0][1] = rhs.matr[0][1];

           this->matr[1][0] = rhs.matr[1][0];

           this->matr[1][1] = rhs.matr[1][1];

           return *this;

    }

     

    Matrix power(const Matrix& m, int n)

    {

           if (n == 1)

                  return m;

           if (n%2 == 0)

                  return power(m*m, n/2);

           else

                  return power(m*m, n/2) * m;

    }

     

    //普通递归

    long fib1(int n)

    {

                  if (n <= 2)

                  {

                         return 1;

                  }

                  else

                  {

                         return fib1(n-1) + fib1(n-2);

                  }

    }

    /*上面的效率分析代码

    long fib1(int n, int* arr)

    {

                  arr[n]++;

                  if (n <= 1)

                  {

                         return 1;

                  }

                  else

                  {

                         return fib1(n-1, arr) + fib1(n-2, arr);

                  }

    }

    */

     

    long fib(int n, long a, long b, int count)

    {

           if (count == n)

                  return b;

           return fib(n, b, a+b, ++count);

    }

    //一叉递归

    long fib2(int n)

    {

           return fib(n, 0, 1, 1);

    }

     

    //非递归方法O(n)

    long fib3 (int n)

    {

           long x = 0, y = 1;

           for (int j = 1; j < n; j++)

           {

                  y = x + y;

                  x = y - x;

           }

           return y;

    }

     

    //矩阵乘法O(log(n))

    long fib4 (int n)

    {

           Matrix matrix0(1, 1, 1, 0);

           matrix0 = power(matrix0, n-1);

           return matrix0.matr[0][0];

    }

     

    //公式法O(1)

    long fib5(int n)

    {

           double z = sqrt(5.0);

           double x = (1 + z)/2;

           double y = (1 - z)/2;

           return (pow(x, n) - pow(y, n))/z + 0.5;

    }

     

    int main()

    {

           //n = 45时候fib1()很慢

           int n = 10;

           cout << fib1(n) << endl;

           cout << fib2(n) << endl;

           cout << fib3(n) << endl;

           cout << fib4(n) << endl;

           cout << fib5(n) << endl;

           return 0;

    }


    转载请注明本文地址: 斐波那契数列算法分析
    展开全文
  • 斐波那契数列算法 兔子问题 推理过程(公司笔试面试类型题)(斐波那契数列) 第一个月: 1 小兔子 =1 第二个月: 1 小兔子 =1 第三个月: 1 对大兔子 1 对小兔子(本月生) ...

    斐波那契数列算法

    兔子问题

    推理过程(公司笔试面试类型题)(斐波那契数列)

    第一个月: 1 小兔子 =1
    第二个月: 1 小兔子 =1
    第三个月: 1 对大兔子 1 对小兔子(本月生) = 1 + 1 = 2
    第四个月: 1 对大兔子 1 对小兔子(本月生) 1 对小兔子(上月生)= 1 + 1 + 1 = 3
    第五个月: 2 对大兔子 2 对小兔子(本月生) 1 对小兔子(上月生)= 2 + 2 + 1 = 5
    第六个月: 3 对大兔子 3 对小兔子(本月生) 2 对小兔子(上月生)= 3 + 3 + 2 = 8
    第七个月: 5 对大兔子 5 对小兔子(本月生) 3 对小兔子(上月生)= 5 + 5 + 3 =13
    ………………以此类推

    基本代码如下:(三种写法)
    n1=1
    n2=1
    num = input("请输入计算的斐波那契数列个数:")
    
    if num.isdigit():#isdigit()自动判断小于零
        num=int(num)
        if num == 0:
            print("输入内容非法")
        if num==1:
            print(n2)
        if num==2:
            print(n2,n2)
        if num>=3:
            for i in range(1,num+1):
                if i==1:
                    print(1,end=',')
                elif i==2:
                    print(1,end=',')
                else:
                    # result =n1 +n2    #计算当前月份的兔子数
                    # print(result,end=',')
                    # #交换数据
                    # n1 = n2
                    # n2 = result       #两种交换数值写法
                    n1, n2 = n2, n1 + n2
                    print(n2, end=',')  # 灵活的语法结构
    
        pass
    else:
        print("输入内容非法")
    
    利用递归实现斐波那契额算法代码如下:
    
    def recur_fibo(n):
        """递归函数
        输出斐波那契数列"""
        if n <= 1:
            return n
        else:
            #返回第n个元素的前两个数相加的值
            return (recur_fibo(n - 1) + recur_fibo(n - 2)) 
    # 获取用户输入
    nterms = int(input("您要输出几项? "))
    
    # 检查输入的数字是否正确
    if nterms <= 0:
        print("输入正数")
    else:
        print("斐波那契数列:")
        for i in range(nterms):
            print(recur_fibo(i),end=' ')
    
    
    利用lambda表达式 + 递归实现斐波那契数列写法如下:
    while True:
        n=int(input("你要输入几项?:"))
        if n<= 0:
            print("输入正数")
        else:
            fbnq=lambda n: fbnq(n-1)+fbnq(n-2) if n>2 else 1
            print("第",n,"项的斐波那契值为:",fbnq(n))
    
    

    总结:

    斐波那契数列就是从第三个元素开始,第n个元素的值就等于(n-1)+(n-2)
    的值。找规律也是写算法代码的必修课。

    如有纰漏,请多指教

    展开全文
  • 斐波那契数列算法实现 法一:递归方法 /* 斐波那契数列: n:0 1 2 3 4 5 6 7 对应斐波那契值: 0 1 1 2 3 5 8 13 */ //递归方法 时间复杂度:O(2^n) public static int fib(int n){ if (n<=1){ return n;...

    斐波那契数列的算法实现

    法一:递归方法

    /*
        斐波那契数列:   n:0 1 2 3 4 5 6 7
           对应斐波那契值: 0 1 1 2 3 5 8 13
         */
     //递归方法  时间复杂度:O(2^n)
        public static int fib(int n){
            if (n<=1){
                return n;
            }
            return fib(n-1)+fib(n-2);
        }
    

    递归法时间复杂度分析

    在这里插入图片描述

    时间复杂度:O(2^n) 时间复杂度较大不建议使用

    法二:使用for循环

    //使用for循环  时间复杂度:O(n)
        public static int fib2(int n){
            if (n<=1){
                return n;
            }
            int first = 0;
            int second = 1;
            for (int i = 0; i < n-1 ; i++) {
                int sum = first + second;
                first = second;
                second = sum;
            }
            return second;
        }
    

    时间复杂度:O(n)

    展开全文
  • 斐波那契数列Fibonacci sequence),又称黄金分割数列、因数学家列昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入。 简单而言,斐波那契数列以如下递推的方法定义:F(1)=1,F(2)=1, F(n)=F(n - ...

    斐波那契数列

    斐波那契数列(Fibonacci sequence),又称黄金分割数列、因数学家列昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入。
    简单而言,斐波那契数列以如下递推的方法定义:F(1)=1,F(2)=1, F(n)=F(n - 1)+F(n - 2)(n ≥ 3,n ∈ N*)

    实现思路

    斐波那契数列递归实现

    class Solution {
    public:
        int Fbi(int number) {
            if(number <= 2) return number;
            return Fbi(number-1)+Fbi(number-2);
        }
    };
    

    递归方法实现非常简单,但是当number变大的时候,递归算法的内存开销会非常大,所以可以使用动态规划的方式。

    class Solution {
    public:
        int Fibonacci(int n) {
            int f = 0, g = 1;
            while(n--) {
                g += f;
                f = g - f;
            }
            return f;
        }
    };
    
    

    迭代的思路和动态规划类似

    class Solution {
    public:
        int Fibonacci(int n) {
            if(n == 0)
                return 0;
            if(n == 1)
                return 1;
            int numfn1 = 0, numfn2 = 1;
            int currentnum = 0;
            for(int i=2; i<=n; ++i) {
                currentnum = numfn1+numfn2;
                numfn1 = numfn2;
                numfn2 = currentnum;
            }
            return currentnum;
        }
    };
    

    动态规划和迭代的方式会节省不少的内存开销,非常适合运算量大的情况。
    以上三种代码就是一般动态规划的解决思路。

    常见题目

    1*一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。

    class Solution {
    public:
        int jumpFloor(int number) {
            if(number < 4) return number;
            return jumpFloor(number-1)+jumpFloor(number-2);
        }
    };
    

    2我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2n的大矩形,总共有多少种方法?

    比如n=3时,23的矩形块有3种覆盖方法:
    在这里插入图片描述

    class Solution {
    public:
        int rectCover(int number) {
           if(number<3)
           {
            return number;
           }
               return rectCover(number-1)+rectCover(number-2);
        }
    };
    
    class Solution {
    public:
        int rectCover(int number) {
          int f = 0,g  = 1;
          while(number--){
          g += f;
          f= g -f;
        }
         return f;
    };
    
    展开全文
  • 斐波那契数列 Fibonacci 斐波那契数列是这样的数列: 0、1、1、2、3、5, 8、13、21、34 …… 下一项是上两项的和。 2 是上两项的和(1+1) 3 是上两项的和(1+2)、 5 是(2+3)、 依此类推! 更多有意思的介绍可以...
  • 斐波那契数列算法复杂度计算过程

    千次阅读 2018-07-27 09:35:11
    2. 斐波那契数列也可以用矩阵乘法来将时间复杂度压缩到log(n). 假设A为要乘的矩阵, 大概有n-2个, 例如两个矩阵乘过后再自乘 为4个,再自乘为8个,直到达到n-2g个为止,所以时间复杂度为log(n)。  作者:...
  • 4阶斐波那契序列如下:f0=f1=f2=0, f3=1,…,fi=fi-1+fi-2+fi-3+fi-4,利用容量为k=4的循环队列,构造序列的前n+1项(f0, f1 , f2 ,… fn ),要求满足fn ≤200而fn+1 >200。
  • 斐波那契数列算法优化 最早研究这个数列的是斐波那契,他当时为了描述如下情况的兔子生长数目: * 第一个月初有一对刚诞生的兔子 * 第二个月之后(第三个月初)它们可以生育 * 每月每对可生育的兔子会诞生下...
  • 斐波那契数列算法及其优化 提示:斐波那契数列:1 1 2 3 5 8 13…。 # 一、斐波那契数列是什么? 示例:规律:前两个数字等于第三个数字之和。 二、运用函数递归方法 代码如下(示例): #include<stdio.h> int...
  • 斐波那契数列算法分析.doc
  • 斐波那契数列几种实现算法 # 1. 递归实现: def fib(n): if n < 3: return 1 return (fib(n-1)+ fib(n-2)) print(fib(10)) # 时间复杂度O(2^n) # 空间复杂度 O(n) # 空间复杂度:包括 1、变量 2、stack ...
  • 计算斐波那契数列算法 public class Fib { static int f(int k) { if (k <= 2) { return 1; } else { return f(k - 2) + f(k - 1); } } public static void main(String[] args) { System....
  • 一、递归算法 import java.util.Scanner; //Fibonacci数列:1,1,2,3,5,8,... //求该数列第n个数的值。 //数列满足递归公式:F1=1,F2+=1,Fn=Fn-1 + Fn-2 public class Fibonacci { public static void main...
  • 斐波那契数列算法

    2018-03-17 23:46:48
    斐波那契数列算法 斐波那契数列定义:数列的第一项和第二项为1,以后各项都为前后两项之和。根据定义设置定义前后两个变量left和right,分别用于生成下一项的两个加数。result变量是保存输出的变量值。因此设计程序...
  • python实现斐波那契数列算法优化 斐波那契数列的具体实现原理就不需要再阐述了,就是具体的第n项等于前两项之和,其中第0项为0,第一项为1.当然你也看成从第一项开始,第一项和第二项都是1的数列。 所以我们最基本...
  • python 斐波那契数列 算法

    热门讨论 2021-01-18 15:43:56
    斐波那契数,通常用F(n)表示,形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是: F(0) = 0,F(1) = 1 F(n) = F(n - 1) + F(n - 2),其中 n > 1 给你 n ,请...
  • 斐波那契数列讲解算法的设计思路从斐波那契到递归带备忘录的递归从递归到动态规划动态规划算法设计思路分治算法设计贪心算法设计斐波那契数列的用途与特性斐波那契数列的用途斐波那契数列的特性算法设计总结 ...
  • Fibonacci 数列算法分析

    2016-11-18 09:21:00
    1 /*************************************************... 2 * Fibonacci 数列算法分析 3 *************************************************/ 4 #include<iostream> 5 #include<stdio.h> 6 #...
  • 主要介绍了JS实现斐波那契数列的五种方式(小结),文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧
  • 斐波那契数列算法及时间复杂度分析 斐波那契数列是一个很有意思的数列,应用领域非常广. 定义: F(n+1)=F(n)+F(n-1) 有意思的是,F(n)/F(n+1)趋于黄金分割0.618. 如何计算斐波那契数呢? 最朴素的思想,利用...
  • 斐波那契数列算法

    2020-12-26 15:19:02
    大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项(从0开始,第0项为0,第1项是1)。 示例1 输入 4 返回值 3 递归解法 这是最容易想到的最简单的方法: class Solution: ...
  • 算法-递推算法-斐波那契数列 /** * 递推算法 * 递推算法是一种理性思维模式的代表,其根据已有的数据和关系,逐步推导而得到结果。递推算法的执行过程如下: * (1)根据已知结果和关系,求解中间结果。 * 2)...
  • 斐波那契数列的迭代算法和递归算法

    万次阅读 多人点赞 2019-03-11 16:29:39
    使用迭代算法和递归算法都可以实现斐波那契数列,输出数列中的第N项,但是由于递归算法在计算时存在着大量的重复计算,所以在N值很大时,可能会造成内存的溢出,以及计算时间较长的情况出现,在使用迭代算法的情况下...
  • 【Java算法斐波那契数列算法+优化+代码(从入门到发疯)A.背景B.定义C.解法1.递归2.递归+HashMap缓存3.递归+数组缓存4.数组缓存+顺序递推5.顺序递推6.公式解法7.矩阵解法8.矩阵解法+快速幂D.尾声 本文作者: ...
  • 通过分别用递归法、迭代法、矩阵法以及公式法对斐波那契数列的C++算法进行分析,最终总结并得出计算斐波那契数列在时间效率层面上最优的算法为矩阵法,但综合考虑下来的最优算法为迭代法。
  • 斐波那契数列, 这个数列从第3项开始,每一项都等于前两项之和。 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ... 递归 : function fibonacci(n, first, second) { if(n == 1) { return first || 0; ...
  • Fibonacci数列算法分析

    2016-06-08 09:56:25
    斐波那契数列 |—F(0)=0 - | F(1)=1 |—F(n)=F(n-1)+F(n-2) n>1 对于小于47的自变量求值,函数值可以用单纯的int类型来表示。#include #include #include #include using namespace std;int fib

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 38,894
精华内容 15,557
关键字:

斐波那契序列算法