百钱买百鸡问题

果子

问题来源
中国古代数学家张丘建在他的《算经》中提出了著名的"百钱买百鸡问题"：鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一。百钱买百鸡，问翁、母、雏各几何？
基本思想
利用计算机来解决"百钱买百鸡问题"是程序设计语言中的一个经典的例子，"百钱买百鸡问题"的解决，基本思想是采用穷举法，即列举各种可能的买鸡情况从中选出鸡的总数为100只且买鸡的钱也刚好是100元的公鸡、母鸡和小鸡数，但是采用不同的思路，可以得到不同的算法，其效率也不尽相同。
下面我们用不同的方法来求解这个简单的问题并分析各自的效率。
设公鸡x,母鸡y,小鸡z。则必须有：
x + y + z = 100
5*x + 3*y + z/3 = 100

方法一：
简单的利用x,y,z的范围构造三重for循环,
1<=x<=19
1<=y<=32
3<=y<=98且整除3
void hectoMC()
{
    size_t x,y,z;
    for(x=1;x<=19;++x)
        for(y=1;y<=32;++y)
            for(z=3;z<=96;z+=3)
            if(x+y+z==100 && 5*x+3*y+z/3==100)
            cout<<"x= "<<x<<" y= "<<y<<" z= "<<z<<endl;
}

方法二：
利用两重循环
将x+y+z = 100带入到第二个方程中化简可得：
7*x+4*y=100.理由这个消去一层循环

void hectoMC()
{
    size_t x,y;
    for(x=1;x<=19;++x) //要习惯for循环中的前置++
        for(y=1;y<=32;++y)
        if(7*x+4*y==100)
            cout<<"x= "<<x<<" y= "<<y<<" z= "<<100-x-y<<endl;
}

方法三：
将原三元一次方程组中的变量x看着常数，则y,z可以用x表示：
y = 25-7*x/4
z = 75+3*x/4
利用这个可以用一个变量即一冲循环完成程序：

void hectoMC()
{
    size_t x,y,z;
    for(x=4;x<=16;x+=4)
    {
        y = 25-7*x/4;
        z = 75+3*x/4;
        if(y>0 && y<=32 && z<=96)
        cout<<"x= "<<x<<" y= "<<y<<" z= "<<z<<endl;
    }
}

方法四：
继续研究方法三，我们发现：
根据y = 25-7*x/4;和y>0(其实是y>=1)的条件，我们可以推导出，x满足4<=x<=12且能被4整除，即只能取4,8,12三个值。
y = 25-7*x/4;可以肯定y<=25<32,所有y<=32这个条件不需要。
根据4<=x<=12，则z = 75+3*x/4<=75+9<=84<96,因此第三个条件z<=96也不需要判断。因此我们的终极程序就是：
void hectoMC()
{
    size_t x;
    for(x=4;x<=12;x+=4)
        cout<<"x= "<<x<<" y= "<<25-7*x/4<<" z= "<<75+3*x/4<<endl;
}
其实只有三个取值，你完全可以不用for循环直接输出结果。后续时间复杂度什么的分析就不分析了，根据程序一目了然。
虽然程序很简单，但是我们可以从中知道任何程序都是可以不断被优化的，优化的力量是无穷的！

啊冲

我一看长代码，就晕