百元买百鸡的算法优化

首先我们来描述一下题目：

买x只公鸡，y只母鸡，z只小鸡，要求一共100只，每只公鸡2元，每只母鸡1.5元，每只小鸡0.5元，要求一共100元，并且每一种鸡都要有。

我们以最初无脑的算法计算

public class BuyChicken{
	public static void main(String[] args){
		int plan = 1;
		for(int x = 1;x<100;x++){
			for(int y = 1;y<100;y++){
				for(int z = 1;z<100;z++){
					if(x+y+z==100&&2*x+1.5*y+0.5*z==100){
						System.out.println ("方案"+plan+"：公鸡："+x+"，母鸡："+y+"，小鸡："+z);
						plan++;
					}
				}
			}
		}
	}
}
           

运行结果：

方案1：公鸡：2，母鸡：47，小鸡：51
方案2：公鸡：4，母鸡：44，小鸡：52
方案3：公鸡：6，母鸡：41，小鸡：53
方案4：公鸡：8，母鸡：38，小鸡：54
方案5：公鸡：10，母鸡：35，小鸡：55
方案6：公鸡：12，母鸡：32，小鸡：56
方案7：公鸡：14，母鸡：29，小鸡：57
方案8：公鸡：16，母鸡：26，小鸡：58
方案9：公鸡：18，母鸡：23，小鸡：59
方案10：公鸡：20，母鸡：20，小鸡：60
方案11：公鸡：22，母鸡：17，小鸡：61
方案12：公鸡：24，母鸡：14，小鸡：62
方案13：公鸡：26，母鸡：11，小鸡：63
方案14：公鸡：28，母鸡：8，小鸡：64
方案15：公鸡：30，母鸡：5，小鸡：65
方案16：公鸡：32，母鸡：2，小鸡：66

进程已结束，退出代码 0

           

我们对此进行优化：

由题可知

x+y+z=100；

2x+1.5y+0.5*z=100；

可得：

3x+2y=100;

可知x最小为1，此时y最大为49；

y最小为1，此时x最大为32；

且z=100-x-y；

public class BuyChicken {
    public static void main(String[] args){
        int plan = 1;
        for(int x = 1;x<=32;x++){
            for(int y = 1;y<=49;y++){
                if(2*x+1.5*y+0.5*(100-x-y)==100) {
                    System.out.println("方案" + plan + "：公鸡：" + x + "，母鸡：" + y + "，小鸡：" + (100-x-y));
                    plan++;
                }
            }
        }
    }
}
           

但这并不是最简，我们可以根据3x+2y=100得出y的值，并且我们知道y与z的系数分别是1.5与0.5，要想刚好用100元买，x的数量必定是偶数（因为若x的数量为奇数，则y与z的总数量为奇数，所以y与z的数量必有一个为奇数）;

public class BuyChicken {
    public static void main(String[] args){
        int plan = 1;
        for(int x = 2;x<=32;x+=2){
            System.out.println("方案" + plan + "：公鸡：" + x + "，母鸡：" + (100-3*x)/2 + "，小鸡：" + (100-x-(100-3*x)/2));
            plan++;
        }
    }
}
           

这样就可以把循环次数从99* 99* 99次减少到16次了喔！

欢迎大家一起评论改进！