斐波那契数列:初始值一对兔子,从出生第3个月起每个月都生一对兔子,假如兔子都不死,问N个月时兔子的数量

发布时间:2018-08-22作者:laosun阅读(4827)

斐波那契数列:初始值一对兔子,从出生第3个月起每个月都生一对兔子,假如兔子都不死,问N个月时兔子的数量

    初始值1对兔子,从出生后第3个月起每个月都生一对兔子,小兔子长到第三个月后每个月又生一对兔子,假如兔子都不死,问每个月的兔子总数为多少?

    其实这就是一个斐波那契数列(Fibonacci sequence),又称黄金分割数列、因数学家列昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”。

    斐波拉契数列原理:除开前两项 后面每位数等于前两项相加之和  1、1、2、3、5、8、13、21、34、……

    我们可以使用递归方式来执行,程序如下:

    /**
     * 斐波那契数列
     * 
     * @author sun
     */
    public class Demo {
    	public static void main(String[] args) throws java.lang.Exception {
    		System.out.println(f1(5));
    	}
    
    	public static int f1(int month) {
    		if (month == 0 || month == 1 || month == 2)
    			return 1;
    		return f1(month - 1) + f1(month - 2);
    	}
    
    }

    但是这种方式会有效率问题,就是月份越大,执行越慢。比如我们要知道45个月后一共有多少兔子?

    所以博主再给出另外两种方式:

    package com.sunjs.java4;
    
    /**
     * 斐波那契数列
     * 
     * @author sun
     */
    public class Demo {
    
    	/**
    	 * 初始值1对兔子 <br>
    	 * 规则:兔子从出生三个月后每个月都会生出一对兔子,兔子长大三个月后都会生出一对兔子(不考虑兔子的死亡)<br>
    	 * 
    	 * @author sun
    	 * @param args
    	 * @throws java.lang.Exception
    	 */
    	public static void main(String[] args) throws java.lang.Exception {
    		int month = 45;
    
    		long s1 = System.currentTimeMillis();
    		int f1num = f1(month);
    		long s2 = System.currentTimeMillis();
    		System.out.println("递归方式:" + month + "个月后兔子的数量是:" + f1num + " 共耗时:" + (s2 - s1));
    
    		int f2num = f2(month);
    		long s3 = System.currentTimeMillis();
    		System.out.println("递推方式:" + month + "个月后兔子的数量是:" + f2num + " 共耗时:" + (s3 - s2));
    
    		int f3num = f3(month);
    		long s4 = System.currentTimeMillis();
    		System.out.println("递推数组方式:" + month + "个月后兔子的数量是:" + f3num + " 共耗时:" + (s4 - s3));
    	}
    
    	/**
    	 * 递归方式
    	 * 
    	 * @author sun
    	 * @param month
    	 * @return
    	 */
    	public static int f1(int month) {
    		if (month == 0 || month == 1 || month == 2)
    			return 1;
    		return f1(month - 1) + f1(month - 2);
    	}
    
    	/**
    	 * 递推方式,也就是普通的for循环
    	 * 
    	 * @author sun
    	 * @param month
    	 */
    	public static int f2(int month) {
    
    		int preRabbitNum = 1; // 上月兔子的数量和
    		int nowRabbitNum = 1; // 这一月兔子的数量和
    		int count; // 中间值 , 用来存数量的
    		for (int i = 3; i <= month; i++) {// 从第三个月开始计算
    			count = nowRabbitNum;
    			nowRabbitNum = preRabbitNum + nowRabbitNum;
    			preRabbitNum = count;
    		}
    		return nowRabbitNum;
    	}
    
    	/**
    	 * 递推方式-数组方式
    	 * 
    	 * @author sun
    	 * @param month
    	 */
    	public static int f3(int month) {
    		int num = 0;
    		int[] arrayList = new int[month];
    		arrayList[0] = arrayList[1] = 1;// 前两个月份
    		for (int i = 2; i < arrayList.length; i++) {
    			arrayList[i] = arrayList[i - 1] + arrayList[i - 2];
    			num = arrayList[i];
    		}
    		return num;
    	}
    
    }

    执行结果:

    递归方式:45个月后兔子的数量是:1134903170 共耗时:3925
    递推方式:45个月后兔子的数量是:1134903170 共耗时:0
    递推数组方式:45个月后兔子的数量是:1134903170 共耗时:0


3 +1

版权声明

 Java  源码  算法

 请文明留言

0 条评论