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

枚举法 主要内容 ◆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 注意枚举的顺序 „ 减少判断每种情况的时间

21百钱买百鸡☆ 最简单直接的做法 ◆鸡翁一,值钱五,鸡母一,值钱三,鸡 ◆根据方程写程序 值4 (X=0;x<100;x++) 枚举次数: 百钱买百鸡,问鸡翁 母、雏各几何? for(y-0;y<100-xy+)I=55次 ◆根据题意列方程 Z100-X-y f(%3=0 5X+3y+z/3= &&15*x+9y+z=30) y+z=10 另解 枚举次数大大减少 ◆根据整理后的方程写程序 5X+3y+z/3=100 观察方 ·for(x0;x<14:;x++ xy,z≥=03除z 枚举次数 v·100-7*x; X+4y=100 if (z %3)continue; x+y+z=100 v<<<<z<<endl 22猴子分桃子☆ 有一堆桃子和甲乙两组猴子,甲组3只猴子,乙组5 ◆第8只猴子来过后,还剩R8个桃子 组猴子先看到桃子 只猴子把桃子均分 第7只来过后,还剩R7个桃子 走了。第二、第三只猴子亦照样办理。 ◆第8只猴子拿走了一堆,还吃了一个 到了桃 这 R8/(5-1)=R8/4是它原来按5份分时的总量 还要加1,才是它看到的原始量 堆便走了。第二、第三、第四、第五只猴子亦照 样办理 R7=R8/4*5+1 请问:8只猴子分别来过之后,至少还剩多少个桃 ◆其他依次类推 子?原来至少有多少个桃子

2 2.1 百钱买百鸡 Š根据题意列方程： Š 鸡翁一，值钱五，鸡母一，值钱三，鸡 雏三，值钱一。百钱买百鸡，问鸡翁、 母、雏各几何？ 5x + 3y + z/3 = 100 x + y + z = 100 (x, y, z >= 0; 3整除z) 最简单直接的做法 Š 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, z >= 0; 3整除z) 7x + 4y = 100 x + y + z = 100 (x, y, z >= 0; 3整除z) Š 观察方程的 特点，消去 一个未知数z 枚举次数大大减少 Š 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 2.2 猴子分桃子 Š 有一堆桃子和甲乙两组猴子，甲组3 只猴子，乙组5 只。 Š 甲组猴子先看到桃子，第一只猴子把桃子均分成3 堆，结果剩下2 个，它吃了这两个，又拿了一堆便 走了。第二、第三只猴子亦照样办理。 Š 甲组走后，乙组又看到了桃子，第一只猴子把桃子 均分成5 堆，结果剩下1 个，它吃了这一个，又拿了 一堆便走了。第二、第三、第四、第五只猴子亦照 样办理。 Š 请问：8 只猴子分别来过之后，至少还剩多少个桃 子？原来至少有多少个桃子？ Š 第8只猴子来过后，还剩R8个桃子 „ 第7只来过后，还剩R7个桃子…… Š 第8只猴子拿走了一堆，还吃了一个 „ R8/(5-1)=R8/4是它原来按5份分时的总量 z 还要加1，才是它看到的原始量 „ R7 = R8 / 4 * 5 + 1 Š 其他依次类推

选择适当的枚举量 92.3质数方阵 递推关系式 右下图表示了一个方阵,沿 R0=RI/2*3+2 行、沿列及两个对角线的5个11351 ◆RI=R2 数字均组成一个5位的质数 33203 R2=R3/2*3+2 拥蕉互貧 对于行,自左向右读数;对于30323 R3=R4/4*5+1 列,自上向下读数;对于对角 R4=R5/4*5+1 线,两个对角线均自左向右读 33311 R5=R6/4*5+ 数 R6=R7/4*5+1 R7=R8/4*5+1 质数方阵 所有位置的可能取值情况 ◆现在给定两个数和A,编程 个确定矩阵中 按以下要求构成方阵 不能是11351 每个元素: 零,例如0000是位质数 33203 最左一列、最上一行元9101010 每个质数的各位之和均为s(右30323 14033 根据质数的限制,最右 ·方阵左上角中的数字为A(右图33311 不能是 数,也不能是5 个5位质数在同一方阵中可以 则每个位量的可能取值 被使用多次 的情况如右图 若存在多个解,必须全部给出 策略:选择适当的枚举顺序 质数的判断 ◆减少枚举次数 质数的判断:如何提高判断的效率? ·某些元囊可以由已知元素直 接确定〔和为S) ·方法1;sqrt(100000=316,小于316 适当选择每个元章确定的顺 的质数有65个,事先记录在数组中。 序,可以减少枚举次数 如果这个五位数不能被这65个质微中 的任何一个整除则必为质数 ·顺序确定原则:尽量由已知 元素确定未知元囊 方法2:事先求出所有和为s的所有五位 右图是一种枚举顺 进套教::6次质数判断用二分法

3 选择适当的枚举量 Š R0 = R1 / 2 * 3 + 2 Š R1 = R2 / 2 * 3 + 2 Š R2 = R3 / 2 * 3 + 2 Š R3 = R4 / 4 * 5 + 1 Š R4 = R5 / 4 * 5 + 1 Š R5 = R6 / 4 * 5 + 1 Š R6 = R7 / 4 * 5 + 1 Š R7 = R8 / 4 * 5 + 1 Š 递推关系式： R0> R1> …R7>R8 是一组相互依赖 的解向量，只需 枚举其中的一 个，应该选择哪 个量进行枚举？ 2.3 质数方阵 Š 右下图表示了一个方阵，沿 行、沿列及两个对角线的5个 数字均组成一个5位的质数。 Š 对于行，自左向右读数；对于 列，自上向下读数；对于对角 线，两个对角线均自左向右读 数。 1 1 3 5 1 3 3 2 0 3 3 0 3 2 3 1 4 0 3 3 3 3 3 1 1 质数方阵 Š 现在给定两个数S和A，编程 按以下要求构成方阵。 „ 5位质数中的第一个数字不能是 零，例如00003不是5位质数。 „ 每个质数的各位之和均为S（右 图中S = 11）。 „ 方阵左上角中的数字为A（右图 中A = 1）。 „ 一个5位质数在同一方阵中可以 被使用多次。 „ 若存在多个解，必须全部给出。 1 1 3 5 1 3 3 2 0 3 3 0 3 2 3 1 4 0 3 3 3 3 3 1 1 4 4 9 9 所有位置的可能取值情况 Š 枚举逐个确定矩阵中的 每个元素： „ 最左一列、最上一行元 素不为0。 „ 根据质数的限制，最右 一列、最下一行不能是 偶数，也不能是5。 „ 则每个位置的可能取值 的情况如右图： 9 9 10 9 10 10 10 10 10 4 4 4 9 10 10 9 10 9 4 4 4 4 策略：选择适当的枚举顺序 Š 减少枚举次数： „ 某些元素可以由已知元素直 接确定（和为S ）。 „ 适当选择每个元素确定的顺 序，可以减少枚举次数。 „ 顺序确定原则：尽量由已知 元素确定未知元素。 „ 右图是一种枚举顺序： a b c d e f m n l o g p k r s h j t v w i q u x y 质数的判断 Š 质数的判断：如何提高判断的效率？ Š 方法1：sqrt (100000) ＝ 316，小于316 的质数有65个，事先记录在数组中。 如果这个五位数不能被这65个质数中 的任何一个整除则必为质数。 Š 方法2：事先求出所有和为S的所有五位 质数（最多757个，S = 23时取到）， 记录在数组中。每次质数判断用二分法 进行查找即可

质数方阵题小结 24宴会上的彩灯☆ ◆算法效率分析 续址是全共物#2 在的方法需要枚举多少次? 置:姦券福廷堑爹灯巯绕 关灯游戏 Turnofflight swf 质数判断的两种优化方法各最多需要几次判断? 小试牛刀 http:/acm.pku.edu.cn/judgeOnline/showproblem?problemid 彩灯状态转换示意图 观察得到的结论 ◆每个开关最多被操作一次,因为操作两次 的结果相当于没有操作。 第i的灯的状态只能由第i-1,i计+1行的开 ◆如果第i-1,i开关状态已经确定,为了要 关上第i的灯,第i+1行开关的状态也就 被唯一确定 关灯策略:局部枚举 一个例子 枚举对第一行开关的操作 ·桔色:灯亮 蓝色:灯 ·按动第二行的开关,把第一行的 ·按忸:开关 灯都关 按动第三行的开关,把第二行的 的灯关上 输出结果是 100111 按动第五行的开关,看是否可以 ll0000 恰好第四行和第五行的灯的灯 000100 Il0101 101101

4 质数方阵题小结 Š 算法效率分析： http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=11 65 Š 小试牛刀 Š减少枚举次数 Š减少判断每种情况的时间 Š现在的方法需要枚举多少次？还能不能更快？ Š 质数判断的两种优化方法各最多需要几次判断？ 2.4 宴会上的彩灯 Š 在举行宴会的房间的一面墙上，30盏 彩灯排成5行6列，每盏灯带有1个开 关。按动某盏灯的开关，它和它上下 左右的灯都会转变状态。 Š 宴会之后，这些彩灯有开有关，愁煞 了管理员。如何才能将这些彩灯统统 关上呢？ Š 关灯游戏 TurnoffLight.swf 开关的状态 有230种可能 彩灯状态转换示意图 观察得到的结论 Š 每个开关最多被操作一次，因为操作两次 的结果相当于没有操作。 Š 第i行的灯的状态只能由第i-1, i, i+1行的开 关控制。 Š 如果第i-1, i行开关状态已经确定，为了要 关上第i行的灯，第i+1行开关的状态也就 被唯一确定。 关灯策略：局部枚举 Š 枚举对第一行开关的操作。 Š 按动第二行的开关，把第一行的 灯都关。 Š 按动第三行的开关，把第二行的 的灯关上。 Š …… Š 按动第五行的开关，看是否可以 恰好第四行和第五行的灯的灯。 一个例子 Š 桔色：灯亮 Š 蓝色：灯灭 Š 按钮：开关 1 0 0 1 1 1 1 1 0 0 0 0 0 0 0 1 0 0 1 1 0 1 0 1 1 0 1 1 0 1 输出结果是：

彩灯题小结 3、枚举vs.搜索 ◆效率比较: 枚举本质上属于搜索算法 ■行遍所有可能 合理的顺序和剪枝可以提高效率 结论: ·对阿题进行分析,你会发现需要枚举的东西 ◆枚举的适用范围 往往没有想象的那么多 1.可预先确定解的个数n 2.解变量A,A2,…,Aq的值的可能变 ◆小试牛刀 化(范围预先确定) http:/lacmpku.edu.cn/judgeonline/showproblemPRoblemide 结论 四皇后问题及其解空间树 枚举是一种非常基本的算法思想 实现简单 常用实现方法:多循环(fo循环,whil循环) 效率较低 对问题多加分析,减少循环数和次数 是否有其它更好的方法? 回测法、分支限定法是枚举法的推广 课堂讨论 枚举和字符串操作 ◆每个字母都有一个权值 http://acmpku.edu.cn/judgeOnline/showproblem?p ◆给定字母表,表中字符可以重复 roblem id=1171(Letter Game) 给定一个字典 字典的大小不超过4000 给定单词长度不超过7

5 彩灯题小结 http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id= 1222 26 230 Š 效率比较： Š 小试牛刀： Š 结论： VS Š 对问题进行分析，你会发现需要枚举的东西 往往没有想象的那么多。 3、枚举 vs. 搜索 Š 枚举本质上属于搜索算法 „ 行遍所有可能 „ 合理的顺序和剪枝可以提高效率 Š 枚举的适用范围 „ 1．可预先确定解的个数n „ 2．解变量Al，A 2， …，Aq的值的可能变 化（范围预先确定） 结论 Š 枚举是一种非常基本的算法思想 „ 实现简单 z 常用实现方法：多重循环（for循环，while循环） „ 效率较低 z 对问题多加分析，减少循环重数和次数 z 是否有其它更好的方法？ z 回溯法、分支限定法是枚举法的推广 四皇后问题及其解空间树 1 2 4 3 5 6 7 4 3 9 8 10 11 12 2 4 4 2 3 14 13 15 16 17 2 3 3 2 4 X1=1 18 20 19 21 22 23 3 4 4 3 1 25 24 26 27 28 1 4 4 1 3 30 29 31 32 33 1 3 3 1 4 2 34 36 35 37 38 39 2 4 4 2 1 41 40 42 43 44 1 4 4 1 2 46 45 47 48 49 1 2 2 1 4 3 50 52 51 53 54 55 2 3 3 2 1 57 56 58 59 60 1 3 3 1 2 62 61 63 64 65 1 2 2 1 3 4 X2=2 X3=3 X4=4 Q Q Q Q 课堂讨论 Š 一、枚举和字符串操作 http://acm.pku.edu.cn/JudgeOnline/showproblem?p roblem_id=1171 (Letter Game) Š 每个字母都有一个权值 Š 给定字母表，表中字符可以重复 Š 给定一个字典 „ 字典的大小不超过40000 „ 给定单词长度不超过7