【算法】斐波那契数列

主要内容:

  1. 斐波那契数列(兔子问题)
  2. 递归算法和递推算法

斐波那契数列(兔子问题)

问题描述:刚出生的兔子,长到第三个月开始(忽略月份大小)就可以繁殖下一代。假如1月1日抱来一公一母两只兔子,那么3月1日时,就会生出第一代兔子,并且正好也是一公一母。假设兔子没有死亡,每代兔子都可以正常繁殖下一代,那么计算抱来一对兔子第N月时,兔子的总量是多少对。(刚抱来算第一个月)

【算法】斐波那契数列

观察可知,从第三月开始,每个月的兔子总量等于前两个月的兔子总量之和,由此,便很容易确定其可以用斐波那契数列的思路来解决。

  公式:Fib(n)=Fib(n-1)+Fib(n-2),n>3

现在来使用代码实现,我使用的是java来实现

递归算法和递推算法

package lucas;

import java.util.Scanner;

/**兔子问题<br/>
 * 问题描述:<br/>
 * 刚出生的兔子,长到第三个月开始(忽略月份大小)就可以繁殖下一代。<br/>
 * 假如1月1日抱来一公一母两只兔子,那么3月1日时,就会生出第一代兔子,并且正好也是一公一母。<br/>
 * 假设兔子没有死亡,每代兔子都可以正常繁殖下一代,
 * 那么计算抱来一对兔子第N月时,兔子的总量是多少对。(刚抱来算第一个月)
 * @author LENOVO
 *
 */
public class Rabbit {
	//递归,斐波那契数列
	public static double Fib(double n){
		if(n==1.0||n==2.0){
			return 1.0;
		}else{
			return Fib(n-1.0)+Fib(n-2.0);
		}
	}
	public static void main(String[] args) {
		/*
		 * 由题意可知,兔子序列从第三个月开始,
		 * 每个月的数据是前两个月的和,所以很容易想到递归
		 * 使用double(8字节)可以容纳很大的数字
		 * 用递归很慢,只适合小一点的数字。
		 * */
		double f,n;
		System.out.print("抱来兔子的第N月:");
		Scanner sc=new Scanner(System.in);
		n=sc.nextDouble();
		System.out.print("当前兔子总量(对):");
		f=Fib(n);
		System.out.format("%.0f",f);
	}

}

  得到的结果(真的很慢):

【算法】斐波那契数列

兔子的增长序列是斐波那契数列,所以考虑使用递推算法。

递推算法要比递归速度快很多,空间占用也少很多。

package lucas;

import java.util.Scanner;

/**兔子的增长序列是斐波那契数列,所以考虑使用
 * 递推算法。<br/>
 * 递推算法要比递归速度快很多,空间占用也少很多。
 * @author LENOVO
 *
 */
public class Rabbit2 {

	public static void main(String[] args) {
		double f,n,i;
		double a,b;//存储前2个月兔子总量
		
		System.out.println("抱来兔子的第n月:");
		Scanner sc=new Scanner(System.in);
		n=sc.nextDouble();
		
		a=b=f=1.0;
		//从第3月才开始累加
		for(i=3.0;i<=n;i++){
			f=a+b;//计算第i月的数量
			a=b;
			b=f;
		}
		System.out.print("当前兔子总量(对)");
		System.out.format("%.0f",f);		
	}

}

  结果显示(真的是秒速):

【算法】斐波那契数列

 

参考自:http://www.cnblogs.com/kangjianwei101/p/5221542.html

上一篇:算法导论——斐波那契堆


下一篇:C# 4种方法计算斐波那契数列 Fibonacci