百鸡百钱问题实验报告.doc

百鸡百钱问题摘要: 本次报告主要讨论百鸡百钱问题,通常使用蛮力法策略,用枚举法来表现,列举出满足问题条件的解,排除一些明显不合理情况,分别验证解的可行性,得到最优算法。关键词:蛮力法;枚举法;百鸡百钱;HundredchickensmoneyAbstract:Thispaperreportshundredchickensmoney,usuallyusingabruteforcemethodstrategy,useenumerationmethodtotheperformance,meettheconditionslistedproblemsolution,excludesomeobviousunreasonablesituation,respectively,toverifythefeasibilityofthesolution,:thebruteforcemethod;enumeration;hundredchickensmoney;1 引言在求解一个较小规模的问题时,可以根据问题中的约束条件把可能的情况一一列举出来,然后注意尝试从中找到满足约束条件的解,若该问题规模较大,符合条件的情况很多,则需要进一步考虑,排除一些明显不合理的情况,尽可能减少问题可能解的列举数目。2 问题概述公元前5世纪,我国古代数学家张丘建在他的《算经》中提出了著名的百鸡百钱问题“鸡翁一,值钱五;鸡母一,值钱三;鸡雏一,值钱一;百钱买百鸡,鸡翁,母,雏各几何?”3算法设计根据问题中的约束条件将可能的情况一一列举出来,但如果情况很多,排除一些明显的不会理的情况,尽可能减少问题可能解的列举数目,然后找出满足问题条件的解。完成百鸡百钱问题的常规算法(懒惰枚举)的实现和改进算法(非懒惰枚举)的实现,以实验方法证明对于同一问题可以有不同的枚举范围,不同的枚举对象,解决问题的效益差别会很大。算法设计一懒惰枚举法:首先问题有三种不同的鸡,那么我们可以设鸡翁为x只,鸡母为y只,鸡雏为z只。由题意给出一共要用100钱买一百只鸡,如果我们全部买鸡翁最多可以买100/5=20只,显然x的取值范围是1~20之间;如果全部买鸡母最多可以买100/3=33只,显然y的取值范围在1~33之间;如果全部买鸡雏最多可以买100*3=300只,可是题目规定是买100只,所以z的取值范围是1~:x+y+z=100且5*x+3*y+z/3=100。流程图如下所示:懒惰算法算法语言描述main(){intx,y,z;   //定义鸡翁,鸡母,鸡雏intcount=0;  //统计时间复杂度的变量for(x=1;x<=20;x++)  //鸡翁的取值范围for(y=1;y<=34;y++) //鸡母的取值范围for(z=1;z<=100;z++)//鸡雏的取值范围100==x+y+zand100==5*x+3*y+z/3; //约束条件  Cout<<x<<y<<z;//输出鸡翁,鸡母,鸡雏的可能取值count++;//统计此算法的时间复杂度}  程序运行结果截图:图1——懒惰算法程序运行截图算法设计二非懒惰枚举法:假如我设了鸡翁和鸡母的个数为x和y了,那么鸡翁和鸡母的数量就是确定的,那么鸡雏的数量就是固定的为100-x-y,那么此时就不再需要进行