小牛问题

public class Main {

public static void main(String[] args) {
long start = System.currentTimeMillis();
for (int year = 1; year <= 50; year ++) {
//System.out.println("递归算法：第" + year + "年：" + (getSons(3, year, 1) + 1));//7秒多
//这个递归比下面的慢了一层的时间，而且是最外层的，在使用递归的时候一定要优化层数，越少越好！！！
//System.out.println("迭代算法：第" + year + "年：" + getCow(year));//几乎0秒
//System.out.println("第" + year + "年：（递归->）" + (getSons(3, year, 1) + 1) + "\t（迭代->）" + getCow(year));
System.out.println(getCowSons(year) + 1);//4秒多
//注意这个递归比上面的快了一层的时间，而且是最外层的，在使用递归时候，一定要优化层数，越少越好！！！！
//System.out.println(getCowSons2(year) + 1);//几乎0秒
}
long end = System.currentTimeMillis();
System.out.println("运算时间：" + (end - start)/1000.0);
}


//用循环做的，当年数大于50的时候，效率明显高于递归！！
//缺点： 当要改成10年生一个的话，就麻烦了。。。。。
//迭代算法
public static long getCow (long year) {

long matrue = 0, one = 1, two = 0, three = 0;
for (int i =1; i <= year - 1; i ++) {
matrue += three;//3岁的变成熟的和原来成熟的加在一起了
three = two;//2岁的变成三岁的
two = one;//1岁的变成两岁的
one = matrue;//成熟的生下1岁的，3岁得下一年生出1岁得，成熟的下一年也生出一岁的，加在一起
}
return matrue + one + two + three;//所有的 cow 加在一起，就是今年的牛数
}

//不好的递归算法
//如果要求一年生五个 只需要最后的结果乘 5 就是了！！！！
public static int getCowSons(int year) {//num是多少年开始生小牛,year 表示第几年

int sons = 0;
if (year > 3) {
sons = year - 3;
for (int j = 0; j < year - 3; j ++) {
sons += getCowSons(year - 3 - j);
}
}
return sons;
}

public static int getCowSons2(int year) {

int mature = 0, one = 1, two = 0, three = 0;
for (int i = 1; i < year; i ++) {
mature += three;
three = two;
two = one;
one =mature;
}
return mature + one + two + three;
}

//递归算法效率问题太严重了，层次越多，效率越低，内存使用越厉害，能不用就别用了！！！
//50次 之后每一次的时间 是 上面次数 的 时间 之和 ，而用村换做 根本看不出差距
//不过下面这种做法可以任意修改三个参数
public static long getSons(long jiange, long age, long num) { // jiange 是多少年之后开始下小羊，age 头羊的年龄，num 是一年 下 小羊只数！
//如果说要改写成一年生 多个 只需要 在最后的结果上乘以 几 就可以了，可以看成是几个 农场一起 ，每个农场还是一个罢了
long sons = 0;
if (age > jiange) {
sons = (age - jiange) * num;
age = age - jiange;
for (long j = 0; j < age; j ++) {
sons += num * getSons(jiange, age - j, num);
}
}
return sons;
}

//一般的计算机系统栈的默认大小只有 64K
//所以递归的层数不可能很高
//4个int局部变量的递归函数
//最多只能递归4000层
//再多就要Stack Overflow了
//递归调用函数的开销相当的大


//**********************************************
//System.out.println(Integer.MAX_VALUE);
//long num = 1;
//for (int i = 0; i < 31; i ++) {
//num *= 2;
//}
//System.out.println(num - 1);
//**********************************************
}