斐波那契数列：初始值一对兔子，从出生第3个月起每个月都生一对兔子，假如兔子都不死，问N个月时兔子的数量
发布时间：2018-08-22作者：laosun阅读（4962）
初始值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
版权属于: 技术客
原文地址: https://www.sunjs.com/article/detail/eba24965f41b46c49fdbffbadca3d289.html
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
共 0 条评论