百鸡百钱问题及其算法分析.doc

百钱百鸡问题的最佳解决方案（陕西师范大学计算机科学学院10级计科一班 西安 710062）摘要：本文主要讨论百鸡百钱问题，通常用蛮力法策略，用枚举法表现，排除明显不合理情况，列举出符合问题的解，分别验证解的可行性，得到最优算法。关键词：蛮力法；枚举；百鸡百钱；The money the chicken question the best solutionduan xi-juan, zhongmei, zhao shan-shan, zhao ya-wen(School of Computer Science, ,Shanxi Normol University, Xian 710062)Abstact :In this article, we mainly discuss the chicken and the money problem. Usually use brute force method strategy, with enumeration method performance, eliminate obviously unreasonable situation, Enumerate conform to the problem solution, which verified the feasibility of the solution, and get the optimal algorithm. Keywords: The brute force method;Enumeration;Hundred chickens money1引言在求解一个较小规模的问题时，可以根据问题中的约束条件把可能的情况一一列举出来，然后注意尝试从中找到满足约束条件的解，若该问题规模较大，符合条件的情况很多，则需要进一步考虑，排除一些明显不合理的情况，尽可能减少问题可能解的列举数目。2问题描述百钱百鸡问题。中国古代数学家张丘建在他的算经中提出了他的著名的“百钱百鸡问题”：鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一；百钱买百鸡，翁、母、雏各几何？3算法设计根据问题中的约束条件将可能的情况一一列举出来，但如果情况很多，排除一些明显的不会理的情况，尽可能减少问题可能解的列举数目，然后找出满足问题条件的解。1）算法设计一首先问题有三种不同的鸡，那么我们可以设鸡翁为x只，鸡母为y只，鸡雏为z只。由题意给出一共要用100钱买一百只鸡，如果我们全部买鸡翁最多可以买1005=20只，显然x的取值范围是120之间；如果全部买鸡母最多可以买100333只，显然y的取值范围在133之间；如果全部买鸡雏最多可以买1003300只，可是题目规定是买100只，所以z的取值范围是1100.那么约束条件为：xyz100且5x3y+1003100.开始定义x.y,zx=20?y=33?z=99?百鸡百钱？结束N输出结果NNNYYYY流程图如下： 算法1程序运行结果截图：2）算法设计二假如我设了鸡翁和鸡母的个数为x和y了，那么鸡翁和鸡母的数量就是确定的，那么鸡雏的数量就是固定的为100xy,那么此时就不再需要进行枚举了，约束条件就只有一个了：5x3yz3100.流程图如下所示：结束图5-9 程序执行流程图算法2程序运行结果截图：4算法分析算法设计一需要枚举尝试次，算法的效率显然很低。算法设计二只须枚举尝试次。实现时约束条件又限定z能被3整除时，才会判断“”。这样省去了不整除3时的算术计算和条件判断，进一步提高了算法的效率。5结束语有此例可以看出，枚举法是蛮力策略的一种变现形式，也是一种使用非常普遍的思维方法。然而对于同一个问题，可以有不同的枚举范围，不同的枚举对象，解决问题的效率差别就会很大，选择合适的方法会让解决问题的效率大大提高。6参考文献1吕国英 算法设计与分析（第二版）M.北京:清华大学出版社，2009.2朱清新 计算机算法分析导论M.北京