蛮力法之百鸡百钱问题
摘要: 本次报告主要讨论百鸡百钱问题，通常使用蛮力法策略，用枚举法来表现，列举出满足问题条件的解，排除一些明显不合理情况，分别验证解的可行性，得到最优算法。
关键词： 蛮力法；枚举法；百鸡百钱；
Hundred chickens money
Abstract: This paper reports hundred chickens money, usually using a brute force method strategy, use enumeration method to the performance, meet the conditions listed problem solution, exclude some obvious unreasonablesituation, respectively, to verify the feasibility of the solution, optimal algorithm.
Key words: the brute force method; enumeration; hundred chickens money;
1 引言
在求解一个较小规模的问题时，可以根据问题中的约束条件把可能的情况一一列举出来，然后注意尝试从中找到满足约束条件的解，若该问题规模较大，符合条件的情况很多，则需要进一步考虑，排除一些明显不合理的情况，尽可能减少问题可能解的列举数目。
2 问题概述
中国古代数学家张丘建在他的《算经》中提出了著名的“百钱百鸡问题”：鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一；百钱买百鸡，翁，母，雏各几何？
译为;现一只公鸡5元钱，一只母鸡3元钱，三只小鸡1元钱；给你一百元钱去买公鸡、母鸡、小鸡共一百只，问你应当买多少只公鸡？多少只母鸡？多少只小鸡？
通过对问题的理解，可列出两个三元一次方程，去解这个不定解方程，找出存在的解。我们要用到“懒惰”的蛮力法其实就和这类似，不同的是我们只需要加以条件，让电脑帮助我们计算，解出结果。
3 算法设计
在公鸡（x），母鸡（y）数量确定后，根据总数100只，小鸡的数量z也就确定为：z=100-x-y，无需再对小鸡的数量进行枚举，此时的约束条件：5x+3y+z/3=100 且 小鸡的数量是3的倍数，这样只需枚举20*34=660次。
int main()
{int x,y,z;
for(x=0;x<20;x++)
for(y=0;y<33;y++)
{
z=100-x-y;
if(z%3==0 && 5*x+3*y+z/3==100)
{
printf("公鸡=%d 母鸡=%d 小鸡=%d\n",x,y,z);
}
}
return 0;
}
);
流程图如下所示：
图1——蛮力算法流程图
图2——蛮力算法程序运行截图
4 算法分析
首先设x,y,z分别为公鸡，母鸡，小鸡的数量。
由于题中条件的限制，我们可以估算出公鸡，母鸡，小鸡的数量范围。
即：
若全买公鸡，最多买100/5=20只，显然：0<x<20;
同理：0<y<33 0<z<100;
约束条件：x+y+z=100 且 5x+3y+z/3=100 且 小鸡数量是3的倍数；
算法如下：
int main()
{int x,y,z;
for(x=0;x<20;x++)
for(y=0;y<33;y++)
for(z=0;z<100;z++)
{
if(x+y+z==100 && z%3==0 && 5*x+3*y+z/3==100)
{
printf("公鸡=%d 母鸡=%d 小鸡=%d\n",x,y,z);
}
}
return 0;
}
若用上面算法，需要枚举尝试20*33*100=66000次，算法的效率太低。因此我们将算法加以改进：
即：在公鸡（x），母鸡（y）数量确定后，根据总数100只，小鸡的数量z也就确定为：z=100-x-y，无需再对小鸡的数量进行枚举，此时的约束条件：5x+3y+z/3=100 且 小鸡的数量是3的倍数，这样只需枚举20*34=660次。
修改后的算法为：
int main()
{int x,y,z;
for(x=0;x<20;x++)
for(y=0;y<33;y++)
{
z=100-x-y;
if(z%3==0 && 5*x+3*y+z/3==100)
{
printf("公鸡=%d 母鸡=%d 小鸡=%d\n",x,y,z);
}
}
return 0;
}
);
5 结束语
由上述实例可以看出，枚举法是蛮力策略的一种变现形式，也是一种使用非常普遍的思维方法。然而对于同一个问题，可以选择不同的枚举范围，不同的枚举对象，这样解决问题的效率差别可能会很大。所以选择合适的方法会让解决问题的效率大大提高。
经过这次的实验，我们充分的认识到团队合作的重要性，通过这次练习，让我们小组更加深刻的认识到蛮力法的优越性以及优中求优，对算法加以修正，做到最好。
6 参考文献
郑莉 董渊.北京:清华大学出版社, 2009.8
严蔚敏,吴伟民.数据结构.北京:清华大学出版社, 2009:173-178.
吕国英.算法设计与分析[M].北京:清华大学出版,2009:154-165.
第二篇：百钱买百鸡问题
百钱买百鸡问题：我的另一种说法……公鸡8文钱一只，母鸡4文钱一只，小鸡2文钱四只，问公鸡、母鸡、小鸡各多少只？