百鸡百钱问题实验报告(2300字)

发表于:2017.6.27来自:www.ttfanwen.com字数:2300 手机看范文

蛮力法之百鸡百钱问题

摘要: 本次报告主要讨论百鸡百钱问题,通常使用蛮力法策略,用枚举法来表现,列举出满足问题条件的解,排除一些明显不合理情况,分别验证解的可行性,得到最优算法。

关键词: 蛮力法;枚举法;百鸡百钱;

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元钱;给你一百元钱去买公鸡、母鸡、小鸡共一百只,问你应当买多少只公鸡?多少只母鸡?多少只小鸡?

通过对问题的理解,可列出两个三元一次方程,去解这个不定解方程,找出存在的解。我们要用到“懒惰”的蛮力法其实就和这类似,不同的是我们只需要加以条件,让电脑帮助我们计算,解出结果。 3 算法设计

在公鸡(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;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);

}

}

1

return 0;

}

);

流程图如下所示:

百鸡百钱问题实验报告

百鸡百钱问题实验报告

图1——蛮力算法流程图

图2——蛮力算法程序运行截图

2

4 算法分析

首先设x,y,z分别为公鸡,母鸡,小鸡的数量。

由于题中条件的限制,我们可以估算出公鸡,母鸡,小鸡的数量范围。

即:

若全买公鸡,最多买100/5=20只,显然:0<x<20;

同理:0<y<33 0<z<100;

约束条件:x+y+z=100 且 5x+3y+z/3=100 且 小鸡数量是3的倍数;

算法如下:

int main()

{int x,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); }

} 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,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);

3

}

}

return 0;

}

);

5 结束语

由上述实例可以看出,枚举法是蛮力策略的一种变现形式,也是一种使用非常普遍的思维方法。然而对于同一个问题,可以选择不同的枚举范围,不同的枚举对象,这样解决问题的效率差别可能会很大。所以选择合适的方法会让解决问题的效率大大提高。

经过这次的实验,我们充分的认识到团队合作的重要性,通过这次练习,让我们小组更加深刻的认识到蛮力法的优越性以及优中求优,对算法加以修正,做到最好。

6 参考文献

郑莉 董渊.北京:清华大学出版社, 2009.8

严蔚敏,吴伟民.数据结构.北京:清华大学出版社, 2009:173-178.

吕国英.算法设计与分析[M].北京:清华大学出版,2009:154-165.

4




第二篇:百钱买百鸡问题(附图)

百钱买百鸡问题:我的另一种说法……公鸡8文钱一只,母鸡4文钱一只,小鸡2文钱四只,问公鸡、母鸡、小鸡各多少只?

更多类似范文
┣ 课程设计实验报告 20600字
┣ 计算机算法实验报告 10300字
┣ 利用动态规划求解0-1背包问题 1700字
┣ 计算机算法设计与分析实验报告 12700字
┣ 更多背包问题实验报告
┗ 搜索类似范文

更多相关推荐:
计算机算法设计与分析实验报告900字

计算机算法设计与分析实验报告专业学号姓名指导老师实验一棋盘覆盖递归与分治策略一实验目的与要求1明确棋盘覆盖的概念2明确递归与分治策略的设计思路3利用递归与分治策略解决棋盘覆盖问题二实验题问题描述递归与分治策略算...

中国矿业大学计算机学院算法设计与分析实验报告7200字

算法实验报告实验一用分治法实现元素选择实验代码includeltiostreamgtusingnamespacestdintmaininta100nxintBinarySearchintaconstintamp...

完全背包问题2500字

课程名称班级姓名日期实验题目完全背包问题实验目的1学习掌握动态规划算法2学习划分子问题及确定优化函数并掌握其思想实验内容一个旅行者准备随身携带一个背包可以放入背包的物品有n种每种物品的重量和价值分别为wjvj如...

专栏推荐
大家在关注

地图地图CC