百元百鸡有关问题
百元百鸡问题
昨天看到有一个百元百鸡的问题,以前以为这类问题都是很头疼的问题,自己应该解决不了,我本来就是个笨蛋。
今天看来,我错了,不是我太笨,是太懒了。
最初版:
public class Util{ /** 百元百鸡问题 @author nKF61564 @since 2012-3-21 上午10:43:47 @return void */ public static void calc(int money,int num){ int cock=money/5; int hen=money/3; int chilk=money*3; for(int i=0;i<=cock;i++){ for(int j=0;j<=hen;j++){ for(int k=0;k<=chilk;k++){ if(i+j+k==num && i*5+j*3+k/3==money && k%3==0){ System.out.println("公鸡="+i+"\t母鸡="+j+"\t雏鸡="+k); } } } } } public static void main(String[] args){ /* 100元,100只鸡 公鸡5/只;母鸡3/只;雏鸡3/只*/ long begin=System.currentTimeMillis(); int money=100; int num=100; calc(money,num); System.out.println(System.currentTimeMillis()-begin); } }
结果:
公鸡=0 母鸡=25 雏鸡=75 公鸡=4 母鸡=18 雏鸡=78 公鸡=8 母鸡=11 雏鸡=81 公鸡=12 母鸡=4 雏鸡=84 耗时:0ms(有时15ms)
但是如果换成千元千鸡,就很耗时间了。
耗时:266ms
修改后:
for(int i=0;i<=cock;i++){ for(int j=0;j<=hen;j++){ int k=num-i-j; if (i*5+j*3+k/3==money && k%3==0) { System.out.println("公鸡="+i+"\t母鸡="+j+"\t雏鸡="+ k); } } }
还是千元千鸡:
耗时:16ms
数量上升到5000之后,2层循环只20ms之内,但是三层的结果:
耗时:30513ms
上升到10000,就得等半天了。
1 楼
pankanghe
2012-03-22
改下
for(int k=0;k<=chilk;k += 3){
if(7i+4j==money){//todo}
}
1、 用三元方程式得出 7i+4j==money
2、money = num
3、k%3 == 0 用 k+=3 代替
for(int k=0;k<=chilk;k += 3){
if(7i+4j==money){//todo}
}
1、 用三元方程式得出 7i+4j==money
2、money = num
3、k%3 == 0 用 k+=3 代替