百元百鸡问题

昨天看到有一个百元百鸡的问题，以前以为这类问题都是很头疼的问题，自己应该解决不了，我本来就是个笨蛋。

今天看来，我错了，不是我太笨，是太懒了。

最初版：

public class Util{
    /** 百元百鸡问题
    	@author niewj
    	@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 代替