斐波那契数列

斐波那契数列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 年起出版了以《斐波纳契数列季刊》为名的一份数学杂志,用于专门刊载这方面的研究成果。

在这里插入图片描述

黄金分割数列

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

在这里插入图片描述

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

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

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

兔子数列

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

经典问题:

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

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

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

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

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

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

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

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

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

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

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 ,运行时间差异不大,基本上一致
在这里插入图片描述
当N = 40 时,此时运行耗时差异已经比较大了
在这里插入图片描述
N = 45 时,耗时差异进一步加大
在这里插入图片描述
所以当N 值趋近于一个较大的值时,再使用递归计算第N项值,耗费的时间将是一个很恐怖的值,因此当N值较大时优先使用迭代算法

关联算法文章:

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

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

Logo

旨在为数千万中国开发者提供一个无缝且高效的云端环境,以支持学习、使用和贡献开源项目。

更多推荐