侧边栏壁纸
博主头像
孔子说JAVA博主等级

成功只是一只沦落在鸡窝里的鹰,成功永远属于自信且有毅力的人!

  • 累计撰写 285 篇文章
  • 累计创建 125 个标签
  • 累计收到 4 条评论

目 录CONTENT

文章目录

算法:神奇的斐波那契数列

孔子说JAVA
2019-10-10 / 0 评论 / 0 点赞 / 82 阅读 / 2,216 字 / 正在检测是否收录...

1、问题来源

1202年,意大利数学家Leonardo Fibonacci提出了这样一个问题:在最佳条件下,一年里,一对兔子能繁殖多少对兔子?这个理论实验规定,母兔总是生下成对的兔宝宝,每对由一公一母组成。两只新生的兔子被安置在一个有围栏的院子里,然后让像正常兔子一样繁殖。长到一个月才能开始繁殖,所以第一个月只有一对兔子。在第二个月月底,母兔产下两只兔子。当第三个月到来时,原来的一对兔子又产了一对新生儿,而它们早期的后代则已经成年。此时便留下了三对兔子,其中两对将在下个月再生两对兔子。

  • 每个月的兔子对数为:1,1,2,3,5,8,13,21,34,55,89,144。这个数列从第3项开始,每一项都等于前两项之和,这个数列被命名为斐波那契数列。如果取数列前两个元素为1,那么递推关系就是:f(n)=f(n-1)+f(n-2)。曾经有一度数学家们将0作为斐波那契数列的首项(或第0项)。

2、实现方式及优缺点

菲波拉契数列问题可以有两种方式实现: 递归算法、循环算法。

1.递归算法

优点:

  1. 代码简洁、清晰,并且容易验证正确性。

缺点:

  1. 它的运行需要较多次数的函数调用,如果调用层数比较深,每次都要创建新的变量,需要增加额外的堆栈处理,会对执行效率有一定影响,占用过多的内存资源。
  2. 递归算法解题的运行效率较低。在递归调用的过程中系统为每一层的返回点、局部变量等开辟了栈来储存。递归次数过多容易造成栈溢出等

注意: 递归就是在过程或函数里调用自身;使用递归策略时要注意的几个条件:

  1. 必须有一个明确的递归结束条件,称为递归出口。
  2. 递归需要有边界条件、递归前进段和递归返回段。
  3. 当边界条件不满足时,递归前进。当边界条件满足时,递归返回。

2.循环算法

优点:

  1. 速度快,结构简单。

缺点:

  1. 并不能解决所有的问题。有的问题适合使用递归而不是循环。如果使用循环并不困难的话,最好使用循环。

3、题目分析

题目1:古典问题:有一对兔子,从出生后第3个月起每个月都生一对兔子,小兔子长到第三个月后每个月又生一对兔子,假如兔子都不死,问每个月的兔子总数为多少?

分析:第1个月:1对兔子,第2个月:1对兔子。

第3个月:新生一对兔子,共有2对兔子,其中1对兔子年龄>=3,1对兔子年龄==1,简单表示为:1(3)/0(2)/1(1), 括号外表示兔子数量,括号内数字表示兔子年龄。

第4个月:够3个月龄的兔子生一对,不够3个月的年龄+1(若达到3,可以生兔子), 1(3)/1(2)/1(1),共3对兔子。

第5个月:有一对兔子刚刚达到3个月龄,加上已经达到3个月龄的,共有2对兔子可以生小兔子,2(3)/1(2)/2(1),共5对兔子。

找规律,按月份列出兔子数量(多少对):1,1,2,3,5…,   这是一个菲波拉契数列问题。

题目2:青蛙跳台阶问题,一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶。求该青蛙跳上一个n级台阶总共有多少种跳法?

分析:当n = 1, 只有1中跳法;当n = 2时,有2种跳法;当n = 3 时,有3种跳法;当n = 4时,有5种跳法;当n = 5时,有8种跳法;…规律类似于Fibonacci数列:  1, 2, 3, 5, 8…

题目3:青蛙变态跳台阶问题,一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

分析:先跳到n-1级,再一步跳到n级,有f(n-1)种;

先跳到n-2级,再一步跳到n级,有f(n-2)种;

先跳到n-3级,再一步跳到n级,有f(n-3)种;

先跳到第1级,再一步跳到n级,有f(1)种;

所以:f(n)=f(n-1)+f(n-2)+f(n-3)+···+f(1), f(n-1)=f(n-2)+f(n-3)+···+f(1), 推出f(n)=2*f(n-1)

4、JAVA实现代码

public class Fblqs {
	
	/**
	 * 菲波拉契数列 - 递归算法实现
	 * 
	 * @param num 月数量
	 * @return
	 */
	public static int recursion(int num) {
		int sum = 1;
		if (num <= 2) {
			return sum;
		}
		return recursion(num-1) + recursion(num-2);
	}
	
	/**
	 * 菲波拉契数列 - 循环实现
	 * 
	 * @param num 月数量
	 * @return
	 */
	public static int circulate(int num) {
		int f1 = 1;//f1代表1月
		int f2 = 1;//f2代表下一月,即2月
		if(num <= 2) {
			return f2;
		}
		for (int i = 3; i <= num; i++) {
			int f = f1 + f2;
			f1 = f2;
			f2 = f;
		}
		return f2;
	}
	
	/**
	 * 青蛙变态跳台阶问题
	 * 算法:f(n) = 2*f(n-1)
	 * 
	 * @param num
	 * @return
	 */
	public static int jumpFloor(int num) {
		if (num <= 2) {
			return num;
		}
		int jumpNum = 2;
		for (int i = 3; i <= num; i++) {
			jumpNum *= 2;
		}
		return jumpNum;
	}
	
	public static void main(String[] args) {
		System.out.println(recursion(30));
		System.out.println(circulate(30));
		System.out.println(jumpFloor(30));
	}
}
0

评论区