枚举法解决百元买百鸡PPT课件.ppt_第1页
枚举法解决百元买百鸡PPT课件.ppt_第2页
枚举法解决百元买百鸡PPT课件.ppt_第3页
枚举法解决百元买百鸡PPT课件.ppt_第4页
枚举法解决百元买百鸡PPT课件.ppt_第5页
已阅读5页，还剩11页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

枚举法实例 信息工程学院 主讲教师 门瑞 什么是枚举法 基本思想 枚举也称穷举 指的是从问题可能的解的集合中一一列举各元素 用题目给定的条件判定哪些是无用的 哪些是有用的 能使命题成立 即为其解 本质上属于搜索算法 2 什么是枚举法 特点 容易理解 步骤单一 得到的结果肯定是正确的 通常会涉及到求极值 如最大 最小等 数据量大的话 可能会造成时间崩溃 3 引子 例1 以下式子中的每个汉字代表一个数字 求出这些汉字代表的数字分别是多少 慕课制作组X慕 组组组组组组 4 枚举法 计算机解决枚举问题 算法简单 精确度高 常用多重循环解决枚举问题 while循环 for循环 效率低 当问题的规模变大 循环的阶数增加 执行的速度严重变慢 5 百元买百鸡问题 例2 鸡翁一 值钱五 鸡母一 值钱三 鸡雏三 值钱一 百钱买百鸡 问鸡翁 母 雏各几何 解题思路 设鸡翁 鸡母 鸡雏的数量分别为x y z 则有以下方程x y z 1005x 3y z 3 100此三元一次方程有多个解 可用枚举法求解 6 百元买百鸡问题 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 7 百元买百鸡问题 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 枚举次数 100 100 100 100万次 8 百元买百鸡问题 限定变量的取值范围x的取值范围是1 x 20y的取值范围是1 y 33减少循环的层数 判断时间z 100 x y 有没有更好的解法呢 9 百元买百鸡问题 C语言解法二 main intx y z for x 1 x 20 x for y 1 y 33 y if 100 x y 3 0 枚举次数 20 33 660次 10 百元买百鸡问题 有没有更好的解法呢 11 百元买百鸡问题 x y z 1005x 3y z 3 100 y 25 7 4 xz 75 3 4 x x 4ky 25 7kz 75 3k 化简 令x 4k 分析题意可知 k只能取1 2 3 12 百元买百鸡问题 C语言解法三 main intk for k 1 k 3 k printf 鸡翁 d只 鸡母 d只 鸡雏 d只 n 4k 25 7k z 枚举次数 3次 13 枚举法 优化策略 对问题多加分析 减少循环重数和次数 合理选择用于枚举的变量 减少每种情况的判断时间 是否有其他更好的方法 14 知识拓展 试用枚举法解决以下两个问题 从1 10的10个数中 每次取2个数 要使它们的和大于10 一共有多少种取法 从学校到少年宫有4条东西走向的马路和3条南北走
人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论