枚举法解决百元买百鸡.ppt

枚举法解决百元买百鸡.ppt

ID:51463094

大小:2.29 MB

页数:16页

时间:2020-03-23

枚举法解决百元买百鸡.ppt_第1页
枚举法解决百元买百鸡.ppt_第2页
枚举法解决百元买百鸡.ppt_第3页
枚举法解决百元买百鸡.ppt_第4页
枚举法解决百元买百鸡.ppt_第5页
资源描述:

《枚举法解决百元买百鸡.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、枚举法实例信息工程学院主讲教师:门瑞什么是枚举法信息工程学院基本思想枚举也称穷举,指的是从问题可能的解的集合中一一列举各元素。用题目给定的条件判定哪些是无用的,哪些是有用的。能使命题成立,即为其解。本质上属于搜索算法什么是枚举法信息工程学院特点容易理解,步骤单一。得到的结果肯定是正确的。通常会涉及到求极值(如最大,最小等)。数据量大的话,可能会造成时间崩溃。引子信息工程学院【例1】以下式子中的每个汉字代表一个数字,求出这些汉字代表的数字分别是多少?慕课制作组X慕组组组组组组枚举法信息工程学院计算

2、机解决枚举问题算法简单、精确度高。常用多重循环解决枚举问题(while循环、for循环)。效率低——当问题的规模变大,循环的阶数增加,执行的速度严重变慢。百元买百鸡问题【例2】鸡翁一,值钱五,鸡母一,值钱三,鸡雏三,值钱一。百钱买百鸡,问鸡翁、母、雏各几何?解题思路:设鸡翁、鸡母、鸡雏的数量分别为x,y,z,则有以下方程x+y+z=1005x+3y+z/3=100此三元一次方程有多个解,可用枚举法求解。信息工程学院百元买百鸡问题C语言解法一:main(){intx,y,z;for(x=1;x<=

3、100;x++)for(y=1;y<=100;y++)for(z=1;z<=100;z++)if((z%3==0)&&(x+y+z==100)&&(5*x+3*y+z/3==100))printf(“鸡翁%d只,鸡母%d只,鸡雏%d只",x,y,z);}信息工程学院百元买百鸡问题C语言解法一:信息工程学院main(){intx,y,z;for(x=1;x<=100;x++)for(y=1;y<=100;y++)for(z=1;z<=100;z++)if((z%3==0)&&(x+y+z==1

4、00)&&(5*x+3*y+z/3==100))printf(“鸡翁%d只,鸡母%d只,鸡雏%d只",x,y,z);}枚举次数:100*100*100=100万次!百元买百鸡问题限定变量的取值范围x的取值范围是1<=x<=20y的取值范围是1<=y<=33减少循环的层数、判断时间z=100-x-y信息工程学院有没有更好的解法呢?百元买百鸡问题C语言解法二:main(){intx,y,z;for(x=1;x<=20;x++)for(y=1;y<=33;y++)if(((100-x-y)%3==

5、0)&&(5*x+3*y+(100-x-y)/3==100)){z=100-x-y;printf(“鸡翁%d只,鸡母%d只,鸡雏%d只",x,y,z);}}枚举次数:20*33=660次!百元买百鸡问题有没有更好的解法呢?信息工程学院百元买百鸡问题x+y+z=1005x+3y+z/3=100y=25-7/4*xz=75+3/4*xx=4ky=25-7kz=75+3k化简令x=4k分析题意可知:k只能取1,2,3信息工程学院百元买百鸡问题C语言解法三:main(){intk;for(k=1;k

6、<=3;k++)printf(“鸡翁%d只,鸡母%d只,鸡雏%d只",4k,25-7k,z);}枚举次数:3次!信息工程学院枚举法信息工程学院优化策略对问题多加分析,减少循环重数和次数。合理选择用于枚举的变量。减少每种情况的判断时间。是否有其他更好的方法。知识拓展信息工程学院试用枚举法解决以下两个问题从1—10的10个数中,每次取2个数,要使它们的和大于10,一共有多少种取法?从学校到少年宫有4条东西走向的马路和3条南北走向的马路,小明从学校步行到少年宫(只许向东或向南行走),最多有多少种走

7、法?谢谢观看信息工程学院主讲教师:门瑞

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。