百元百鸡问题

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

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

最初版：

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