枚举法 主要内容 ◆1、枚举法思想简介 基本算法介绍之 ◆2、利用枚举法解题 2,1百钱百鸡☆ 张铭 22猴子分桃☆ 2007.9.19 23宴会彩灯☆ 24质数方阵☆☆ 3、枚举s,搜索 1、枚举法思想简介 引子 ◆基本思想 填写运算符 枚举也称穷举,指的是从问题可能的解的集 合中一 输入任意5个数xI、x2、x3、 枚举各元童 两个数间填上一个运算 用题目给定的检验条件判定哪些是无用的 个运算符后,使得表达 哪些是有用的。能使命题成立,即为其解。 y(y由健盘输入)。求出 结录升析 ◆典型应用举例:密码破艉 枚举次数 ·要执行4=256次,当数字的个数超过207 最坏情况kn 枚举法初体验 2、利用枚举法解题 少<~·枚举法的特点是算法简单,但是运算量 ◆优化策略 大是它的缺点。当问题的规模变大,循 减少枚举次数 环的阶数愈大,执行的速度愈慢。 ·合理选择用于枚举的变量 注意枚举的顺序 从全局观点使用枚举法,计算量容 减少判断每种情况的时间 易过大。在局部地方使用枚举法 其效果会十分显著1 枚举法 —— 基本算法介绍之一 张铭 2007.9.19 主要内容 Š 1、枚举法思想简介 Š 2、利用枚举法解题 „ 2.1 百钱百鸡 „ 2.2 猴子分桃 „ 2.3 宴会彩灯 „ 2.4 质数方阵 Š 3、枚举 vs. 搜索 1、枚举法思想简介 Š 基本思想 „ 枚举也称穷举，指的是从问题可能的解的集 合中一一枚举各元素。 „ 用题目给定的检验条件判定哪些是无用的， 哪些是有用的。能使命题成立，即为其解。 Š 典型应用举例： 密码破解： 枚举次数： 最好情况1 最坏情况 n k 密码破解 引子 Š 填写运算符 Š 输入任意5个数 x1、x2、x3、x4、x5. 每 相邻两个数间填上一个运算符。在填人四 个运算符后，使得表达式值为一个指定值 y(y由键盘输入)。求出所有满足条件的表达 式。 Š 结果分析 Š 要执行 ＝256次。当数字的个数超过20？ 4 4 枚举法初体验 Š 枚举法的特点是算法简单，但是运算量 大是它的缺点。当问题的规模变大，循 环的阶数愈大，执行的速度愈慢。 Š 从全局观点使用枚举法，计算量容 易过大。在局部地方使用枚举法， 其效果会十分显著。 2、利用枚举法解题 Š 优化策略 „ 减少枚举次数 z 合理选择用于枚举的变量 z 注意枚举的顺序 „ 减少判断每种情况的时间