斐波那契数列的迭代算法和递归算法

川长思鸟来 2023-09-28 16:16 124阅读 0赞

## 斐波那契数列 ##

> `斐波那契数列`（`Fibonacci sequence`），又称`“`黄金分割数列`“`，因数学家莱昂纳多·斐波那契（Leonardo Fibonacci）以兔子繁殖为例子而引入，故又称为`“`兔子数列`”`，指的是这样一个数列：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 年起出版了以《斐波纳契数列季刊》为名的一份数学杂志，用于专门刊载这方面的研究成果。

![在这里插入图片描述][eea7684d42754c3d9da4ecd5a5cd0f25.png_pic_center]

## 黄金分割数列 ##

> `黄金分割`是指将整体一分为二，较大部分与整体部分的比值等于较小部分与较大部分的比值，其比值约为0.618。这个比例被公认为是最能引起美感的比例，因此被称为黄金分割。

![在这里插入图片描述][8b39496df5614725b2b449d8557becb8.png_pic_center]

`把一条线段分割为两部分，使较大部分与全长的比值等于较小部分与较大的比值，则这个比值即为黄金分割。其比值是，近似值为0.618，通常用希腊字母Ф表示这个值。`

**附：黄金分割数前面的32位为：**0.6180339887 4989484820 458683436564

设一条线段AB的长度为a，C点在靠近B点的黄金分割点上，且AC为b，则b与a的比叫作黄金比  
![在这里插入图片描述][1e815861caed4cdfa1c92cddaf3842ca.png_pic_center]  
有趣的是，这样一个完全是自然数的数列，通项公式却是用无理数来表达的。而且当趋向于无穷大时，前一项与后一项的比值越来越逼近黄金分割0.618（或者说后一项与前一项的比值小数部分越来越逼近 0.618）。

## 兔子数列 ##

> 斐波那契数列又因数学家莱昂纳多·斐波那契以兔子繁殖为例子而引入，故又称为“兔子数列”。

**经典问题：**

一般而言，兔子在出生两个月后，就有繁殖能力，一对兔子每个月能生出一对小兔子来。如果所有兔子都不死：

我们不妨拿新出生的一对小兔子分析一下：

第一个月小兔子没有繁殖能力，所以还是一对

两个月后，生下一对小兔对数共有两对

三个月以后，老兔子又生下一对，因为小兔子还没有繁殖能力，所以一共是三对  
－－－－－－  
依次类推可以列出下表：  
![在这里插入图片描述][c680c699aae14170aa62a56dda8367da.png_pic_center]  
幼仔对数=前月成兔对数

成兔对数=前月成兔对数+前月幼仔对数

总体对数=本月成兔对数+本月幼仔对数

可以看出幼仔对数、成兔对数、总体对数都构成了一个数列。这个数列有关十分明显的特点，那是：前

面相邻两项之和，构成了后一项。

这个数列是意大利中世纪数学家斐波那契在<算盘全书>中提出的，这个级数的通项公式，除了具有

a(n+2)=an+a(n+1)的性质外，还可以证明通项公式为：an=(1/√5)\*\{\[(1+√5)/2\]n-\[(1-√5)/2\]n（n=1,2,3,…）

/**
     * 兔子问题
     * 斐波那契数列求值
     * @author tonylp
     *题目：古典问题：有一对兔子，从出生后第3个月起每个月都生一对兔子，
     *小兔子长到第三个月后每个月又生一对兔子，假如兔子都不死，问每个月的兔子总数为多少？
     *1.程序分析： 兔子的规律为数列1,1,2,3,5,8,13,21....
     */
    public class rabbit {
        
        public static final int MONTH = 15;
        public static void main(String[] args) {
        
            long f1 = 1L, f2 = 1L;
            long f;
            for(int i=3;i<MONTH;i++){
        
                f=f1+f2;
                f1=f2;
                f2=f;
                System.out.println("第"+i+"个月的兔子对数："+f2);
            }
        }
        
        //递归方法实现
        public static int fib(int month){
        
            if(month == 1 || month == 2){
        
                return 1;
            }else{
        
                return fib(month-1)+fib(month-2);
            }
        }
    }

## `斐波那契数列算法的应用` ##

> 相关数学题：排列组合、兔子繁殖问题、杨辉三角 …

/**
     * 平推方法实现
     */
    public static long fibLoop(int num){
        
        if(num<1||num>92) return 0;
        long a =1, b = 1, temp;
        for(int i =2;i<num;i++){
        
            temp =a;
            a=b;
            b+=temp;
        }
        return b;
    }
    
    /**
     * 递归方法实现
     * f(n) = f(n-1)+f(n-2)
     * 最高支持 n=92 ,否则超出 Long.MAX_VALUE
     *
     */
    public static  long fibRec(int num){
        
        if(num<1) return 0;
        if (num<3)return 1;
        return fibRec(num-1)+ fibRec(num-2);
    }
    
    
    /**
     * 带有缓存的方法， 比fibRec方法性能好很多
     */
    static long[] l=new long[93];
    static {
        l[1]=1;}
    public  static  long fibBuffec(int num){
        
        if(num<1||num >92) return 0;
        if (l[num]==0)
            l[num]=fibBuffec(num-1)+fibBuffec(num-2);
        return l[num];
    }
    
    
    
    /**
     * 1,2,3,4,5,6,7,8
     * 1,1,2,3,5,8,13,21
     * 支持num 超过92的超大型数字，使用了ArrayList进行缓存以提高性能
     */
    static List<BigDecimal> list =new ArrayList<>(93);
    static {
        
        list.add(BigDecimal.ZERO);
        list.add(BigDecimal.ONE);
    }
    public  static  BigDecimal fibBig(int num){
        
        if (num<0) return list.get(0);
        if (list.size()<=num)
            list.add(fibBig(num-1).add(fibBig(num-2)));
        return list.get(num);
    }

## 斐波那契数列的迭代算法和递归算法 ##

> 使用迭代算法和递归算法都可以实现斐波那契数列，输出数列中的第N项，但是由于递归算法在计算时存在着大量的重复计算，所以在N值很大时，可能会造成内存的溢出，以及计算时间较长的情况出现，在使用迭代算法的情况下同样可以实现计算斐波那契数列第N项的功能，

代码示例如下

迭代算法：

public static int FibonacciD(int num) {
        
    		if(num <= 0) {
        
    			return 0;
    		}
    		if(num == 1 || num == 2) {
        
    			return 1;
    		}
    		int first = 1,second =1,third = 0;
    		for(int i = 3; i<= num ;i++) {
        
    			third = first + second;
    			first = second;
    			second = third;
    		}
    		return third;
    	}

思路就是当 n <=0 时 return 0，当1 <= n <= 2时 return 1 ，当 n >= 3时，第n项 f(n) = f(n-2) + f(n-1)，所以在计算数列中第n项的时候可用一个for循环，初始化前两项的值，计算完成第N项之后，然后交换（n-2）项 （n-1）项的值，循环完成之后计算出的Third值即为数列中第N项的值

递归算法：

public static int Fibonacci(int i) {
        
    		if(i <= 0) {
        
    			return 0;
    		}
    		if(i == 1 || i == 2) {
        
    			return 1;
    		}
    		return Fibonacci(i -2) + Fibonacci(i-1);
    	}

在N值比较小的时候两种方式计算耗时的差异不大，但是当N值比较大的时候两者之间计算时间的差异就比较大了，

当N = 10 ，运行时间差异不大，基本上一致  
![在这里插入图片描述][6ba36d855d084724b33c2175b33d184c.png_pic_center]  
当N = 40 时，此时运行耗时差异已经比较大了  
![在这里插入图片描述][55ef59ed810f40d98ee57c96ab211366.png_pic_center]  
N = 45 时,耗时差异进一步加大  
![在这里插入图片描述][bc4c3cb9fc164a1ea854fba9b5f79594.png]  
所以当N 值趋近于一个较大的值时，再使用递归计算第N项值，耗费的时间将是一个很恐怖的值，因此当N值较大时优先使用迭代算法

## 关联算法文章： ##

> 这里有一些相关的文章，可以参考一下

1、[斐波那契数列的迭代算法和递归算法][Link 1]  
2、[埃氏筛法(埃氏算法)][Link 2]  
3、[BF算法（暴⼒算法）-- 模式匹配算法][BF_--]  
4、[数据结构：八大数据结构分类][Link 3]  
5、[JAVA中 常用七大排序算法][JAVA_]  
6、[Linked 链表反转 - 迭代 与 递归][Linked _ - _ _]

[eea7684d42754c3d9da4ecd5a5cd0f25.png_pic_center]: https://img-blog.csdnimg.cn/eea7684d42754c3d9da4ecd5a5cd0f25.png#pic_center
[8b39496df5614725b2b449d8557becb8.png_pic_center]: https://img-blog.csdnimg.cn/8b39496df5614725b2b449d8557becb8.png#pic_center
[1e815861caed4cdfa1c92cddaf3842ca.png_pic_center]: https://img-blog.csdnimg.cn/1e815861caed4cdfa1c92cddaf3842ca.png#pic_center
[c680c699aae14170aa62a56dda8367da.png_pic_center]: https://img-blog.csdnimg.cn/c680c699aae14170aa62a56dda8367da.png#pic_center
[6ba36d855d084724b33c2175b33d184c.png_pic_center]: https://img-blog.csdnimg.cn/6ba36d855d084724b33c2175b33d184c.png#pic_center
[55ef59ed810f40d98ee57c96ab211366.png_pic_center]: https://img-blog.csdnimg.cn/55ef59ed810f40d98ee57c96ab211366.png#pic_center
[bc4c3cb9fc164a1ea854fba9b5f79594.png]: https://img-blog.csdnimg.cn/bc4c3cb9fc164a1ea854fba9b5f79594.png
[Link 1]: https://blog.csdn.net/GoodburghCottage/article/details/125929088
[Link 2]: https://blog.csdn.net/GoodburghCottage/article/details/125912135
[BF_--]: https://blog.csdn.net/GoodburghCottage/article/details/125907253
[Link 3]: https://blog.csdn.net/GoodburghCottage/article/details/125681654
[JAVA_]: https://blog.csdn.net/GoodburghCottage/article/details/125594490
[Linked _ - _ _]: https://blog.csdn.net/GoodburghCottage/article/details/125597183