北京大学：《数据结构与算法》课程教学资源（实习课件PPT）基本算法与枚举法

枚举法 基本算法介绍之 张铭 2007.9.19

枚举法 —— 基本算法介绍之一 张铭 2007.9.19

主要内容 ◆1、枚举法思想简介 2、利用枚举法解题 2.1百钱百鸡☆ 2,2猴子分桃☆ 23宴会彩灯☆☆ 24质数方阵☆☆ 3、枚举vs.搜索

主要内容 Š 1、枚举法思想简介 Š 2、利用枚举法解题 „ 2.1 百钱百鸡 „ 2.2 猴子分桃 „ 2.3 宴会彩灯 „ 2.4 质数方阵 Š 3、枚举 vs. 搜索

1、枚举法思想简介 ◆基本思想 枚举也称穷举,指的是从问题可能的解的集 合中一一枚举各元素。 ■用题目给定的检验条件判定哪些是无用的, 哪些是有用的。能使命题成立,即为其解。 密码破解: ◆典型应用举例:蜜码破艉 枚举次数: 最好情况1 最坏情况kn

1、枚举法思想简介 Š 基本思想 „ 枚举也称穷举，指的是从问题可能的解的集 合中一一枚举各元素。 „ 用题目给定的检验条件判定哪些是无用的， 哪些是有用的。能使命题成立，即为其解。 Š 典型应用举例： 密码破解： 枚举次数： 最好情况1 最坏情况 密码破解： 枚举次数： 最好情况1 最坏情况 n k 密码破解

引子 ◆填写运算符 ◆输入任意5个数x1、x2、x3、x4、x5.每 相邻两个数间填上一个运算符。在填人四 个运算符后,使得表达式值为一个指定值 y(y由键盘输入)。求出所有满足条件的表达 结果分析 ◆要执行44=256次。当数字的个数超过20?

引子 Š 填写运算符 Š 输入任意5个数 x1、x2、x3、x4、x5. 每 相邻两个数间填上一个运算符。在填人四 个运算符后，使得表达式值为一个指定值 y(y由键盘输入)。求出所有满足条件的表达 式。 Š 结果分析 Š 要执行 ＝256次。当数字的个数超过20？ 4 4

枚举法初体验 ><◆枚举法的特点是算法简单,但是运算量 大是它的缺点。当问题的规模变大,循 环的阶数愈大,执行的速度愈慢。 ◆从全局观点使用枚举法,计算量容 易过大。在局部地方使用枚举法, 其效果会十分显著

枚举法初体验 Š 枚举法的特点是算法简单，但是运算量 大是它的缺点。当问题的规模变大，循 环的阶数愈大，执行的速度愈慢。 Š 从全局观点使用枚举法，计算量容 易过大。在局部地方使用枚举法， 其效果会十分显著

2、利用枚举法解题 优化策略 减少枚举次数 合理选择用于枚举的变量 ●注意枚举的顺序 减少判断每种情况的时间

2、利用枚举法解题 Š 优化策略 „ 减少枚举次数 z 合理选择用于枚举的变量 z 注意枚举的顺序 „ 减少判断每种情况的时间

21百钱买百鸡☆ ◆鸡翁一,值钱五,鸡母一,值钱三,鸡 雏三,值钱一。百钱买百鸡,问鸡翁、 母、雏各几何? 根据题意列方程: 5X+3y+z/3=100 x+y+z=100 (x,y,z>=0;3整除z)

2.1 百钱买百鸡 Š根据题意列方程： Š 鸡翁一，值钱五，鸡母一，值钱三，鸡 雏三，值钱一。百钱买百鸡，问鸡翁、 母、雏各几何？ 5x + 3y + z/3 = 100 x + y + z = 100 (x, y, z >= 0; 3整除z)

最简单直接的做法 根据方程写程序: ◆for(x=0;X<=100;x++) 枚举次数: 101+100++ for(y=0;y<=100-x;y++) 1=5151次 Z 00-X-y; if(z%3=0 &&15*x+9y+z=300) cout<<x<<k<<y<<<<z<<endl ·】

最简单直接的做法 Š for (x = 0; x <= 100; x++) for (y = 0; y <= 100 - x; y++) { z = 100 - x - y; if (z % 3 == 0 && 15 * x + 9 * y +z==300) cout<<x<<' '<<y<<''<<z<<endl; } Š 根据方程写程序： 枚举次数： 101+100+……+ 1 = 5151 次

另解 5X+3y+z/3=100 观察方程的 X+y+z=100 特点,消去 (x,y,2z>=0;3整除z) 个未知数z 7X+4y=100 x+y+z=100 (x,y,z>=0;3整除2)

另解 5x + 3y + z/3 = 100 x + y + z = 100 (x, y, z >= 0; 3整除z) 7x + 4y = 100 x + y + z = 100 (x, y, z >= 0; 3整除z) Š 观察方程的 特点，消去 一个未知数z

枚举次数大大减少 ◆根据整理后的方程写程序: ◆for(x=0;X<=14;x++) 枚举次数 100-7*x; 5151VS14 if (y %4)continue; else y / Z=100-X-y; if (z %3)continue; cout<<x<< k<<y<<<<z<<end

枚举次数大大减少 Š for (x = 0; x <= 14; x++) Š { Š y = 100 - 7 * x; Š if (y % 4) continue; else y /= 4; Š z = 100 - x - y; Š if (z % 3) continue; Š cout<<x<<' '<<y<<' '<<z<<endl; Š } Š 根据整理后的方程写程序： 枚举次数： 5151 VS 14