百钱买百鸡问题--优化的力量

百钱买百鸡问题--优化的力量

百钱买百鸡问题 -- 优化的力量

--BlackRose百度空间

问题来源

中国古代数学家张丘建在他的《算经》中提出了著名的"百钱买百鸡问题"：鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一。百钱买百鸡，问翁、母、雏各几何？

基本思想

利用计算机来解决"百钱买百鸡问题"是程序设计语言中的一个经典的例子，"百钱买百鸡问题"的解决，基本思想是采用穷举法，即列举各种可能的买鸡情况 从中选出鸡的总数为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_2()

{

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_3()

{

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_4()

{

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循环直接输出结果。后续时间复杂度什么的分析就不分析了，根据程序一目了然。

虽然程序很简单，但是我们可以从中知道任何程序都是可以不断被优化的，优化的力量是无穷的！