算法题：细胞分裂计算

题目：1个细胞的生命周期是 3 小时，1 小时分裂一次。求 n 小时后，容器内有多少细胞？

前提：到第三个小时，细胞先分裂在死亡

思路：

最开始细胞数: 1

1小时后细胞数：2

2小时后细胞数：4

3小时后细胞数：7，因为到了3小时，之前的细胞死亡了所以减1

所以递推公式：

        f(n) = f(n-1)*2-f(n-3)
	f(0) = 1
	f(1) = f(0)*2 
	f(2) = f(1)*2 
	f(3) = f(2)*2-f(0)

代码：

/**
 * 细胞分裂计算
 * 题目：1个细胞的生命周期是 3 小时，1 小时分裂一次。求 n 小时后，容器内有多少细胞？
 * 到第三个小时，细胞先分裂在死亡
 */
public class CellDivision {

    public static void main(String[] args) {
        int n = 6;
        System.out.println(n+"个小时后，细胞分裂数为:"+cd(n));
    }

    /**
     *  递推公式：
     *  f(n) = f(n-1)*-f(n-3)
     * 	f(0) = 1
     * 	f(1) = f(0)*2
     * 	f(2) = f(1)*2
     * 	f(3) = f(2)*2-f(0)=7
     * @param n
     * @return
     */
    public static int cd(int n) {
        if(n==0) {
            return 1;
        } else if(n==1) {
            return 2;
        } else if(n==2) {
            return 4;
        }
        int x = cd(n-1)*2-cd(n-3);
        System.out.println(n+"个小时后，细胞分裂数为:"+x);
        return x;
    }
}

输出：

3个小时后，细胞分裂数为:7
4个小时后，细胞分裂数为:12
5个小时后，细胞分裂数为:20
3个小时后，细胞分裂数为:7
6个小时后，细胞分裂数为:33
6个小时后，细胞分裂数为:33