百鸡百钱的最佳解决办法-陕西师范大学计算机科学学院 枚举法

《百鸡百钱的最佳解决办法-陕西师范大学计算机科学学院 枚举法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、百钱百鸡问题的最佳解决方案（陕西师范大学计算机科学学院10级计科一班西安710062）摘要：本文主要讨论百鸡百钱问题，通常用蛮力法策略，用枚举法表现，排除明显不合理情况，列举出符合问题的解，分别验证解的可行性，得到最优算法。关键词：蛮力法；枚举；百鸡百钱；Themoneythechickenquestionthebestsolutionduanxi-juan,zhongmei,zhaoshan-shan,zhaoya-wen(SchoolofComputerScience,,ShanxiNormolUniversity,Xi’an710062)Abstact:Inthisarticle,

2、wemainlydiscussthechickenandthemoneyproblem.Usuallyusebruteforcemethodstrategy,withenumerationmethodperformance,eliminateobviouslyunreasonablesituation,Enumerateconformtotheproblemsolution,whichverifiedthefeasibilityofthesolution,andgettheoptimalalgorithm.Keywords:Thebruteforcemethod;Enumeration;

3、Hundredchickensmoney1引言在求解一个较小规模的问题时，可以根据问题中的约束条件把可能的情况一一列举出来，然后注意尝试从中找到满足约束条件的解，若该问题规模较大，符合条件的情况很多，则需要进一步考虑，排除一些明显不合理的情况，尽可能减少问题可能解的列举数目。2问题描述百钱百鸡问题。中国古代数学家张丘建在他的《算经》中提出了他的著名的“百钱百鸡问题”：鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一；百钱买百鸡，翁、母、雏各几何？3算法设计根据问题中的约束条件将可能的情况一一列举出来，但如果情况很多，排除一些明显的不会理的情况，尽可能减少问题可能解的列举数目，然后找出满足问

4、题条件的解。1）算法设计一首先问题有三种不同的鸡，那么我们可以设鸡翁为x只，鸡母为y只，鸡雏为z只。由题意给出一共要用100钱买一百只鸡，如果我们全部买鸡翁最多可以买100／5=20只，显然x的取值范围是1～20之间；如果全部买鸡母最多可以买100／3＝33只，显然y的取值范围在1～33之间；如果全部买鸡雏最多可以买100×3﹦300只，可是题目规定是买100只，所以z的取值范围是1～100.那么约束条件为：x＋y＋z＝100且5×x＋3×y+100／3＝100.开始定义x.y,zx<=20?y<=33?z<=99?百鸡百钱？结束N输出结果NNNYYYY流程图如下：算法1程序运行结果截图

5、：2）算法设计二假如我设了鸡翁和鸡母的个数为x和y了，那么鸡翁和鸡母的数量就是确定的，那么鸡雏的数量就是固定的为100﹣x﹣y,那么此时就不再需要进行枚举了，约束条件就只有一个了：5×x＋3×y＋z／3＝100.流程图如下所示：结束图5-9程序执行流程图算法2程序运行结果截图：4算法分析算法设计一需要枚举尝试次，算法的效率显然很低。算法设计二只须枚举尝试次。实现时约束条件又限定z能被3整除时，才会判断“”。这样省去了不整除3时的算术计算和条件判断，进一步提高了算法的效率。5结束语有此例可以看出，枚举法是蛮力策略的一种变现形式，也是一种使用非常普遍的思维方法。然而对于同一个问题，可以有不同

6、的枚举范围，不同的枚举对象，解决问题的效率差别就会很大，选择合适的方法会让解决问题的效率大大提高。6参考文献[1]吕国英算法设计与分析（第二版）[M].北京:清华大学出版社，2009.[2]朱清新计算机算法分析导论[M].北京:人民邮电大学出版社[3]谭浩强C语言程序设计（第三版）清华大学出版社