一 问题描述

假设第1个月有一对诞生的兔子，第2个月兔子进入成熟期，第3个月兔子开始生育，而一对成熟的兔子每月会生一对兔子，兔子永不死去，那么从一对初生的兔子开始，12个月后会生成多少对兔子？M个月会生多少对兔子。

二 算法分析

从第3个月开始，当月的兔子数=上月的兔子数+当月新生的兔子数，而当月新生的兔子数正好是上上个月的兔子数，因此，前面相邻两项之和构成了后一项。即当月的兔子数=上月兔子数+上上月兔子数。正好符合斐波那契数列特征。

1,1,2,3,5,8,13,21,34 ......

三 实现

package fib;

import java.util.Date;

public class FibTest {
    // 用45对兔子进行测试
    public static void main(String[] args) {
        Date date1 = new Date();
        long fib2 = fib2(45);
        Date date2 = new Date();
        System.out.println(date2.getTime() - date1.getTime() + "---------" + fib2);
        long fib1 = fib1(45);
        Date date3 = new Date();
        System.out.println(date3.getTime() - date2.getTime() + "---------" + fib1);
    }
    // 递归实现
    static long fib1(int n) {
        if (n < 1) {
            return -1;
        } else if (n == 1 || n == 2) {
            return 1;
        } else {
            return fib1(n - 1) + fib1(n - 2);
        }
    }

    // 数组实现
    static long fib2(int n) {
        long temp;
        if (n < 1) {
            return -1;
        }
        long[] sum = new long[n + 1];
        sum[1] = 1;
        sum[2] = 1;
        int i;
        for (i = 3; i <= n; i++) {
            sum[i] = sum[i - 1] + sum[i - 2];
        }
        return sum[n];
    }
}

四 测试结果

0---------1134903170

7182---------1134903170

五 说明

数组存储算法明显优于递归算法，数组存储算法是用空间换时间。

六 好算法衡量标准

• 正确性
• 易读性
• 健壮性
• 高效性
• 低存储
  前三项是基本标准，好算法的评判标准是高效率和低存储。