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

  1. 1、本文档共4页,可阅读全部内容。
  2. 2、原创力文档(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
PAGE PAGE 4 蛮力法之百鸡百钱问题 摘要: 本次报告主要讨论百鸡百钱问题,通常使用蛮力法策略,用枚举法来表现,列举出满足问题条件的解,排除一些明显不合理情况,分别验证解的可行性,得到最优算法。 关键词: 蛮力法;枚举法;百鸡百钱; 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元钱;给你一百元钱去买公鸡、母鸡、小鸡共一百只,问你应当买多少只公鸡?多少只母鸡?多少只小鸡? 通过对问题的理解,可列出两个三元一次方程,去解这个不定解方程,找出存在的解。我们要用到“懒惰”的蛮力法其实就和这类似,不同的是我们只需要加以条件,让电脑帮助我们计算,解出结果。 算法设计 在公鸡(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;x20;x++) for(y=0;y33;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只,显然:0x20; 同理:0y33 0z100; 约束条件:x+y+z=100 且 5x+3y+z/3=100 且 小鸡数量是3的倍数; 算法如下: int main() {int x,y,z; for(x=0;x20;x++) for(y=0;y33;y++) for(z=0;z100;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

文档评论(0)

186****6075 + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档