本帖最后由 蓝色骨头 于 2013-4-10 23:31 编辑
package heimatest;
import java.math.BigInteger;
import java.util.Arrays;
/*
* 思路:
* 动态规划思想
* 用cowSub(years)表示一头牛years年后将生多少牛。
* 那么cowSub(years) = (years-3) + cowSub(years-3) + cowSub(years-4) +……+ cowSub(0)
* 其中(years-3)表示这头牛生的牛的数量,当years < 3时cowSub(years)为0
* cowSub(years-3) + cowSub(years-4) +……+ cowSub(0)表示这头牛生的牛 再繁衍的牛的数量
* 那么如果有一头years年后的牛总数为:cowSub(years)+1,其中1为原来的这头牛
*
* 因为递归时会产生重复计算,
* 比如在计算cowSub(10)是要计算cowSub(4),在计算cowSub(7)时也要计算cowSub(4)
* 所以可以定义一个数组cowSub,cowSub表示一头牛i年后将生多少头牛。
* 如果没有计算过了就计算这个值,否则直接返回cowSub。
*
* 当years比较大时int类型不够,使用BigInteger
*/
public class CowTest {
public static int cow(int years){
int[] cowSub = new int[years]; //创建数组,用于保留计算结果,避免重复计算,dp思想
Arrays.fill(cowSub, -1); //初始化为-1表示没有计算过
return cowSub(cowSub, years) + 1;
}
private static int cowSub(int[] cowSub,int years){
if( years < 3 ){
return 0;
}
int count =0;
for(int i = 3; i <= years; i++){
count++;
if(cowSub[years-i] == -1){
cowSub[years-i] = cowSub(cowSub, years-i);
}
count += cowSub[years-i];
}
return count;
}
/*
* 发现int长度不够,直接使用BigInteger
*/
private static BigInteger one = new BigInteger("1");
private static BigInteger nagtiveOne = new BigInteger("-1");
public static BigInteger cow2(int years){
BigInteger[] cowSub = new BigInteger[years]; //创建数组,用于保留计算结果,避免重复计算,dp思想
Arrays.fill(cowSub, nagtiveOne); //初始化为-1表示没有计算过
return cowSub2(cowSub, years).add(one);
}
private static BigInteger cowSub2(BigInteger[] cowSub,int years){
if( years < 3 ){
return new BigInteger("0");
}
BigInteger count = new BigInteger("0");
for(int i = 3; i <= years; i++){
count = count.add(one);
if(cowSub[years-i].compareTo(nagtiveOne) == 0){
cowSub[years-i] = cowSub2(cowSub, years-i);
}
count = count.add(cowSub[years-i]);
}
return count;
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
for(int n = 0; n < 100; n++){
System.out.println(n+" year: "+cow(n)+" cows");
}
for(int n = 0; n < 100; n++){
System.out.println(n+" year: "+cow2(n)+" cows");
}
}
}
|