站内搜索: 请输入搜索关键词

当前页面: 开发资料首页J2SE 专题请高手们赐教-老师布置的一道有点难的java题

请高手们赐教-老师布置的一道有点难的java题

摘要: 请高手们赐教-老师布置的一道有点难的java题


有位科学家曾出了这样一道数学题:有一头母牛,它每年年初要生一头小母牛;每头小母牛从第四个年头起,每年年初也要生一头小母牛。按此规律,若无牛死亡,第20年头上共有多少头母牛?


要求用java编写一段代码实现这道题并计算出结果


等比数列........


这不是编程题,这是数学题!!!!!!


public class Test {

public static void main(String args[]) {
int n = 20;
System.out.println(cattle(n));
}

public static int cattle(int n) {
if (n <= 0)
return 0;
if (n <= 3)
return 1;
return cattle(n - 1) + cattle(n - 3);
}

}


偶数学不好,不会,帮顶


递归也不错 反正算法不复杂


2 ,3,4,6,9,13,19,27.........
算法就是第四年,即4以后的这年Numof(4)=numof(3)+numof(3-2)
numof(5)=numof(4)+numof(4-2);。。。。。。。。。。numof(n)=numof(n-1)+numof(n-1-2)


if (n <= 3)
return 1; //return n+1;


知道算法,些程序应该不是难题了。如下:
public class CattleNum {
static int a = 2;

static int b = 3;

static int c = 4;

static int result;

public static void main(String[] args) {
int n=20;
System.out.println("result"+cattle(n));
}

public static int cattle(int n) {
if (n < 1) {
System.out.println("error");
result = n;
} else if (n == 1) {
result = a;
} else if (n == 2) {
result = b;
} else if (n == 3) {
result = c;
} else {
result = cattle(n - 1) + cattle(n - 3);
}
return result;
}


恩!楼上的说的不错!
numof(n)=numof(n-1)+numof(n-1-2)
主要是看2 ,3,4,6,9,13,19,27.........的规律.



呵呵!应该是2,3,4,6,9,13,19,28,41,60



呵呵,现在我头脑里出现的都是小母牛~~~


你们老师好可爱~~~楼上的应该已经给楼主答案了吧!~


amwiacel() ( ) 信誉:100 Blog 2006-10-30 11:46:00 得分: 0


等比数列........


-----------------------------------------

晕,怎么会是等比数列呢:
第二年 第三年 第四年 第五年 第六年 第七年 第八年 第九年 第十年。。。(牛的总数)
2头牛 3头 4 6 9 11 16 24 32
晕了~~~~~
第二年是两头牛吧,好第三年是3头没错吧,第四年是4头,第5年是6头!第二年的小牛以后每年要生啦~~~,第六年是8头?错!是9头牛,因为大牛第三年生的小牛以后每年又要生了~~~,。。。第九年是24头,因为小牛第五年生下的小小牛以后每年又要生了。。。所以20年以后多少头我就不知道了·#@…##·¥
用计算机实现的方法还是你自己慢慢想吧~~~ 呵呵


偶来看看,


数学不行,那就先学数学吧
编程就是数学,是不然就改行吧


fffffffffffffffff


斐博那契问题。把兔子变成了母牛


其实用计算机解题的最大好处就是不用去想,只需要讲故事就好了。

import java.util.*;

class Cow
{
int born_year;//母牛的出生年
public Cow(int _born_year)
{
born_year = _born_year;
}

public boolean bred(int current_year)
{
//如果母牛已经4岁了,它就会生一头小母牛
if( current_year >= (born_year+4) )
return true;
else
return false;
}
}

public class WorldOfCow
{
int current_year;
Vector cows = null;

public WorldOfCow()
{
//这个世界诞生了,但什么都没有
//不知道现在是哪一年current_year
//只有一个牛栏的标牌cows
}

public void init()
{
current_year = 2006;//上帝说今年是2006年
cows = new Vector();//上帝说要有一个空的牛栏
cows.addElement(new Cow(0));//上帝创造了一头母牛放进牛栏,它。。。居然是公元0年出生的
}

public void spend()//度过一年
{
current_year ++;//年份增加了
for(int i=0;i{
Cow cow = (Cow)cows.elementAt(i);//找出一头母牛
if(cow.bred(current_year))//她今年生小牛了吗?
cows.addElement(new Cow(current_year));//生了的话就把小牛也关进牛栏
}
}

public int getQuantityOfWorld()//数数现在牛栏里有几头牛?
{
return cows.size();
}

public static void main(String[] argv)
{
WorldOfCow world = new WorldOfCow(); //上帝创造了一个新的世界
world.init();//上帝对这个世界进行了初始化
for(int i=0;i<20;i++)
world.spend();//这个世界度过了20年

System.out.println("20年过去了,共有"+ world.getQuantityOfWorld() + "头母牛生活在这个大陆上");
}
}


随便写的,没有调试,有错的话,大家不要见笑


小  中  大  母  总记
第一年 1     1   2
二 1  1  1    3
三 1  1 1  1   4
4 1 1  1  2   5
5 2  1  1  3   7
 6  3  2  1  4   10
 7  4  3  2  5   14
 8  5  4  3  7   19
 9  7  5  4  10  26
 10  10  7  5  14  36
 11  14 10 7 19 40
12 19 14 10 26 69
13 26 19 14 36 85
14 36 26 19 50 231
15 50 36 26 69
16 69 50 36 85
17 85 69 50 121
18 121 85 69 171
19 171 121 85 240
20 240 171 121 325

结果是 240+171+121+325 = ?
唉 1看就出答案!
代码自己写,规律自己找



年\牛 小  中  大  母  总记
第一年 1     1   2
二 1  1  1    3
三 1  1 1  1   4
4 1 1  1  2   5
5 2  1  1  3   7
 6  3  2  1  4   10
 7  4  3  2  5   14
 8  5  4  3  7   19
 9  7  5  4  10  26
 10  10  7  5  14  36
 11  14 10 7 19 40
12 19 14 10 26 69
13 26 19 14 36 85
14 36 26 19 50 231
15 50 36 26 69
16 69 50 36 85
17 85 69 50 121
18 121 85 69 171
19 171 121 85 240
20 240 171 121 325

结果是 240+171+121+325 = ?
唉 1看就出答案!
代码自己写,规律自己找


/*
有位科学家曾出了这样一道数学题:有一头母牛,它每年年初要生一头小母牛;
每头小母牛从第四个年头起,每年年初也要生一头小母牛。按此规律,若无牛死亡,
第20年头上共有多少头母牛?
第1年 2
第2年 3
第3年 4
第4年 6=第3年+第1年
第5年 9=第4年+第2年
.
.

f(x)=
2 x=1;
3 x=2
4 x=3
f(x-1)+f(x-3) x>=4
*/
class Crows
{
public static void main(String[] args)
{
Crows cow=new Crows();
int total=cow.birthNum(20);
System.out.println(total);
}
public int birthNum(int year)//year年出生的牛可以生的牛的头数
{
if(year==1)
return 2;
else if(year==2)
return 3;
else if(year==3)
return 4;
else
return birthNum(year-1)+birthNum(year-3);
}
}



看错了题,以为4年后小牛才能才能生牛,SORRY!


想了解网上冲浪免费赚钱的秘密吗,也许你已经知道了,不过我给你推荐的这个网站可是一个很不错的哦!注册后就可以有0.45美元一小时,最高可达0.75美元,详情请到我的小站来了解一下吧,不会让你失望的

http://zhusan.blog.hexun.com/5726307_d.html


/*
有位科学家曾出了这样一道数学题:有一头母牛,它每年年初要生一头小母牛;
每头小母牛从第四个年头起,每年年初也要生一头小母牛。按此规律,若无牛死亡,
第20年头上共有多少头母牛?
第1年 2
第2年 3
第3年 4
第4年 6=第3年+第1年
第5年 9=第4年+第2年
.
.

f(x)=
2 x=1
3 x=2
4 x=3
f(x-1)+f(x-3) x>=4

*/
class Crows
{
public static void main(String[] args)
{
Crows cow=new Crows();
int total=cow.birthNum(20);
System.out.println(total);
}
public int birthNum(int year)
{
if(year==1)
return 2;
else if(year==2)
return 3;
else if(year==3)
return 4;
else
return birthNum(year-1)+birthNum(year-3);
}
}

刚才写的注释不当



用递归的方法在效率上是很不好的哦


我晕,这个问题中只有四种牛:
1)该年出生的牛(不生牛)
2)去年出生的牛(不生牛)
3)前年出生的牛(不生牛)
4)可生育的牛
我的实现是这样的:
package Test;

public class Cow {
static int num1;
static int num2;
static int num3;
static int num4;

public static void main(String [] arg)
{
for(int i=1;i<=20;i++)
{
System.out.println(count(i));
}


}

private static int count(int year)
{
num1=0;
num2=0;
num3=0;
num4=1;
int temp;
for(int i=1;i<=year;i++)
{
temp=num4;
num4=num3+num4;
num3=num2;
num2=num1;
num1=temp;
}
return num1+num2+num3+num4;
}



}


输出结果为:
2
3
4
5
7
10
14
19
26
36
50
69
95
131
181
250
345
476
657
907



大家的思路好象都是先从 第一年 几头牛.....第5年几头牛 ......

然后归纳法推出数学模型 ,然后用代码实现,递归或循环...

可惜推到第5年的时候都错了,第5年应该是是6头牛.那么可想而知数学模型也错了,那代码也错了。

我推了一下:
2,3,4,5,6,8,11,15,20,26.......

alexwan(牧林) 老兄的思路蛮特别,一上来把牛分类.这个对的.可惜分类分的有点问题.

下面一个也是把牛分类的.(不是我做的)


public class Cow {
public static void main(String[] args) {
int n0 = 1, n1 = 0, n2 = 0, n3 = 0, n4 = 0, temp;
/* 开始时各年份能生小母牛的牛的数量,n0表示马上就能生的,n1表示过一年才能生的,n2表示过2年才能生的,依次类推 */
int year = 1;
while (year <= 20) {
temp = n0;
n0 += n1;
n1 = n2;
n2 = n3;
n3 = n4;
n4 = temp;
year++;
}
System.out.println("经过20年后,母牛的总数是" + (n0 + n1 + n2 + n3 + n4));
}

}

答案是经过20年后,母牛的总数是431









樓上OK


不是说第四个年初就能生吗?也就是过三年就能生吧?对题意的理解有点出入哦!


结分吧


我是初学者,见识到了大家的利害了。 呵呵
不错,这样的交流能造就大家。


比兔子复杂点,不过原理一样


只觉——递归最简单


呵呵。递归好方法


递归


用生成函数:
设第n年有a(n)头牛:
则n>=4时:a(n)=a(n-1)+a(n-3)
即:a(n)-a(n-1)-a(n-3)=0;
设 G(x)=a(1)+a(2)x+a(3)x^2+a(4)x^3+....
-xG(x)= -a(1)x+a(2)x^2-a(3)x^3+....
-x^3G(x)= -a(1)x^3+....
则从G(x)的第4项开始,由于a(n)-a(n-1)-a(n-3)=0,以后竖对准的每项和为0
即G(x)-xG(x)-x^3G(x) //3个等式中左边之和
=a(1)+a(2)x+a(3)x^2-a(1)x+a(2)x^2 //3个等式中右边之和
然后解出G(x)
G(0)=a(1)
G(0)'=a(2)
之后可得G(x)的n阶导函数数的关于x=0的值恰好是n!*a(n+1)
然后就可以得到a(n+1)的通式

可以具体搜索"生成函数"或是"母函数"或是"Generating Function"获得更多关于生成函数的用法


因该第四年就可以生了 ~~ 而不是过了四年第五年再生吧

didoleo(冷月无声) 的程序跟题目有点出入吧


//个人意见。呵呵~~~
public class Cow {
public static void main(String[] args) {
int n0 = 1, n1 = 0, n2 = 0, n3 = 0, temp;
/* 开始时各年份能生小母牛的牛的数量,n0表示马上就能生的(母牛),n1表示过一年才能生的

(大牛),n2表示过2年才能生的(中牛),n3表示过3年才能生的(小牛)*/
int year = 1;
while (year <= 20) {
temp = n3;
n3 = n0 + n1;//因为过了一年,大牛会变母牛,所以小牛的数量应该是大牛+母牛
n0 = n0 + n1;
n1 = n2;
n2 = temp;
System.out.println("经过"+year+"年后,母牛的总数是" + (n0 + n1 + n2 + n3));
year++;
}
System.out.println("经过20年后,母牛的总数是" + (n0 + n1 + n2 + n3 ));
}
}

//算出来的结果和递归的结果一样。。不知道有没有错。。。


递归


效率嘛……

public class Test
{
static final int totalYear = 20;

public static void main(String arg[])
{

System.out.print("The total number of cows in the " + totalYear + "nd year is: " + countCows());

}

public static int countCows()
{
final int[] cowsCount = new int[totalYear];
int thisYear = 0;

cowsCount[0] = 2;
System.out.println(thisYear + 1 + " : " + cowsCount[thisYear]);
thisYear++;

for (; thisYear < 3; thisYear++)
{
cowsCount[thisYear] = cowsCount[thisYear - 1] + 1;
System.out.println(thisYear + 1 + " : " + cowsCount[thisYear]);
if (thisYear >= totalYear)
{
return cowsCount[thisYear];
}
}


for (; thisYear < totalYear ; thisYear++)
{
cowsCount[thisYear] = cowsCount[thisYear - 1] + cowsCount[thisYear - 3];
System.out.println(thisYear + 1 + " : " + cowsCount[thisYear]);
}
return cowsCount[thisYear - 1];
}
}

=================================
1 : 2
2 : 3
3 : 4
4 : 6
5 : 9
6 : 13
7 : 19
8 : 28
9 : 41
10 : 60
11 : 88
12 : 129
13 : 189
14 : 277
15 : 406
16 : 595
17 : 872
18 : 1278
19 : 1873
20 : 2745

The total number of cows in the 20nd year is: 2745


这样就避免递归了……


ArrayList cowList = new ArrayList(); //store object cow
cowList.add(String.ValueOf(4)); //add first cow
for(int i=0;i<20;i++)
{
for(int j=0;j {
if(Integer.parsInt(cowList.get(j))>=4)
{
int iTemp = Integer.parsInt(cowList.get(j)) + 1;
cowList(i) = String.ValueOf(iTemp); //aging one
cowList.add(String.ValueOf(1)); //add one cow to Arraylist
}
else
{
int iTemp = Integer.parsInt(cowList.get(j)) + 1;
cowList(i) = String.ValueOf(iTemp); //aging one
}
}
}

//finally, the cowList.size() will be the result


import java.util.ArrayList;
import java.util.List;

/**
* 有位科学家曾出了这样一道数学题:有一头母牛,它每年年初要生一头小母牛;
* 每头小母牛从第四个年头起,每年年初也要生一头小母牛。
* 按此规律,若无牛死亡,第20年头上共有多少头母牛?
*/
public class NeuTest {

public static void main(String[] args) {
List list = new ArrayList();
list.add(new Neu(3));
for(int i = 0; i < 20; i ++) {
for(int j = 0; j < list.size(); j ++) {
Neu n = list.get(j);
if(n.age >= 3) {
list.add(new Neu());
}
n.age++;
}
}
System.out.println(list.size());
}
}
class Neu {
Neu(int a) {
this.age = a;
}
Neu() {

}
int age = 0;
}


2745


shoucang


满天小牛 飞啊飞。


这分明是数学题啊


呵呵 多谢高手们的指点 小弟在此谢过了
看了你们的回复我大开眼界 这几天学习有点忙所以今天才....
我这几天有好好研究了研究这道题我觉得应该这样做:
解: F[n]=F[n-2]+F[n-3]+F[n-4]
F[1]=1 F[2]=2 F[3]=3 F[4]=4



class ZyTest2
{
public static void main(String args[])
{
int f[];
f=new int[20];

f[0]=1;
f[1]=2;
f[2]=3;
f[3]=4;

for(int k=4;k<20;k++)
{
f[k]=f[k-4]+f[k-3]+f[k-2];
}

System.out.println("共有"+f[19]+"头牛.") ;
}
}
而且算出来的答案1873头也和老师给的答案一致


分我已经结过了 请各位笑纳
^_^
1) 正解是F[n]=F[n-1]+F[n-4];
2) 要避免使用递归。见我的方法。


↑返回目录
前一篇: 如何判断一个String是否符合e_mail格式???
后一篇: 字符串相等的问题