那个两天前的牛生牛的问题,大家都用什么方法解决啊？ - 黑马程序员技术交流社区

/**
* 一个农夫养了一头牛，三年后，这头牛每一年会生出1头牛，生出来的牛三年后，又可以每年生出一头牛……
* 问农夫10年后有多少头牛?n年呢?(不考虑其他因素，只考虑此数学问题)
* @author Lihsh-PC
*
*/
public class Test {
/**
* @param args
*/
public static void main(String[] args) {
//十年后实际上是第十一年
//n年后也就是第n+1年
System.out.println("你想知道n年后有多少头牛，那请先输入n吧：");
Scanner scanner = new Scanner(System.in);
int years = scanner.nextInt();
System.out.println(years + "年后有"+ getSum(years + 1) +"头牛");
}
/**
* 由题目可以知道：对于每一头牛单独而言，增长规律是1、2、3、4、5，6从第三项开始是一个等差数列 (可以看出从第四天看是，该天的牛数为第三天，第二天，第一天的牛之和)
* 从第四天开始出生的牛又要重复上述的等差数列 0、0、0、1、2、3、4(已在第一头牛中计算了father)（和上面是一样的道理）
* 第五天出生的牛。。 0、0、0、1、2、3、4()(已在第一头牛中计算了father)（和上面是一样的道理）
* -----------------------------------------------------------
* 1、1、1、2、3、4、6、9....
* 其实也就是兔子(斐波纳契数列)出生的问题的变种,最后我们得出的结论就是第n(n>4)天的牛数量是第(n-2)天,第(n-3)天,第(n-4)天的牛数量之和
* 即f(n)=f(n-2)+f(n-3)+f(n-4)(n > 4)
* f(1)=1
* f(2)=1
* f(3)=1
* 或者f(n)=1 n<4
* f(4) = 2
* 由上面的分析可以看出，是一个递归的问题
* @param years 多少年后
*/
public static int getSum(int years){
if(years == 0)
return 0;
else if(years >= 1 && years <= 3)
return 1;
else if(years > 3)
return getSum(years -2) + getSum(years -3) + getSum(years -4);
else
System.out.println("输入有误，请重新输入！");
return years;
}
}

复制代码

public class PruduceCattle {
/** 一个农夫养了一头牛，三年后，这头牛每一年会生出1头牛，生出来的牛三年后，又可以每年生出一头牛……
* 问农夫10年后有多少头牛?n年呢?(不考虑其他因素，只考虑此数学问题)
* 规律:即f(n)=f(n-2)+f(n-3)+f(n-4)(n > 4);这个用递归效率奇低.
* 我找的规律:f(n)=f(n-1)+f(n-3);(n>3)
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Long begin=System.currentTimeMillis();
System.out.println(getCattleCount(1000));
System.out.println(System.currentTimeMillis()-begin+"毫秒");
/*50 1000
83316385 4.239507006748923E165
0毫秒 31毫秒*/
/*Long begin=System.currentTimeMillis();
System.out.println(getSum(50));//这是最快的,我开始试1000,结果有十几分钟没出结果.而上面的算法算1000,只需要32毫秒.
System.out.println(System.currentTimeMillis()-begin+"毫秒");*/
}
public static int getSum(int years) {
if (years == 0)
return 0;
else if (years >= 1 && years <= 3)
return 1;
else if (years > 3)
return getSum(years - 2) + getSum(years - 3) + getSum(years - 4);
else
System.out.println("输入有误，请重新输入！");
return years;
}
public static double getCattleCount(int n){
double sum=0;
double first=1;
double second=1;
double thread=1;
for(int i=0;i<n-3;i++){
sum=first+thread;
first=second;
second=thread;
thread=sum;
}
if(n<=3)
return 1;
else return sum;
}
}

复制代码