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

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