百鸡百钱问题实验报告

PAGEPAGE4蛮力法之百鸡百钱问题摘要:本次报告主要讨论百鸡百钱问题，通常使用蛮力法策略，用枚举法来表现，列举出满足问题条件的解，排除一些明显不合理情况，分别验证解的可行性，得到最优算法。关键词：蛮力法；枚举法；百鸡百钱；HundredchickensmoneyAbstract:Thispaperreportshundredchickensmoney,usuallyusingabruteforcemethodstrategy,useenumerationmethodtotheperformance,meettheconditionslistedproblemsolution,excludesomeobviousunreasonablesituation,respectively,toverifythefeasibilityofthesolution,optimalalgorithm.Keywords:thebruteforcemethod;enumeration;hundredchickensmoney;1引言在求解一个较小规模的问题时，可以根据问题中的约束条件把可能的情况一一列举出来，然后注意尝试从中找到满足约束条件的解，若该问题规模较大，符合条件的情况很多，则需要进一步考虑，排除一些明显不合理的情况，尽可能减少问题可能解的列举数目。2问题概述中国古代数学家张丘建在他的《算经》中提出了著名的“百钱百鸡问题”：鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一；百钱买百鸡，翁，母，雏各几何？译为;现一只公鸡5元钱，一只母鸡3元钱，三只小鸡1元钱；给你一百元钱去买公鸡、母鸡、小鸡共一百只，问你应当买多少只公鸡？多少只母鸡？多少只小鸡？通过对问题的理解，可列出两个三元一次方程，去解这个不定解方程，找出存在的解。我们要用到“懒惰”的蛮力法其实就和这类似，不同的是我们只需要加以条件，让电脑帮助我们计算，解出结果。算法设计在公鸡（x），母鸡（y）数量确定后，根据总数100只，小鸡的数量z也就确定为：z=100-x-y，无需再对小鸡的数量进行枚举，此时的约束条件：5x+3y+z/3=100且小鸡的数量是3的倍数，这样只需枚举20*34=660次。 intmain(){intx,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);}}return0;});流程图如下所示：图1——蛮力算法流程图图2——蛮力算法程序运行截图4算法分析首先设x,y,z分别为公鸡，母鸡，小鸡的数量。由于题中条件的限制，我们可以估算出公鸡，母鸡，小鸡的数量范围。即： 若全买公鸡，最多买100/5=20只，显然：0<x<20;同理：0<y<330<z<100;约束条件：x+y+z=100且5x+3y+z/3=100且小鸡数量是3的倍数；算法如下： intmain(){intx,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); } }return0;}若用上面算法，需要枚举尝试20*33*100=66000次，算法的效率太低。因此我们将算法加以改进：即：在公鸡（x），母鸡（y）数量确定后，根据总数100只，小鸡的数量z也就确定为：z=100-x-y，无需再对小鸡的数量进行枚举，此时的约束条件：5x+3y+z/3=100且小鸡的数量是3的倍数，这样只需枚举20*34=660次。修改后的算法为： intmain(){intx,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);}}return0;});5结束语由上述实例可以看出，枚举法是蛮力策略的一种变现形式，也是一种使用非常普遍的思维方法。然而对于同一个问题，可以选择不同的枚举范围，不同的枚举对象，这样解决问题的效率差别可能会很大。所以选择合适的方法会让解决问题的效率大大提高。经过这次的实验，我们充分的认识到团队合作的重要性，通过这次练习，让我们小组更加深刻的认识到蛮力法的优越性以及优