北京大学：《数据结构与算法》实习实验教程（PPT课件讲稿）算法之一：穷举法

数据结构与算法实习 算法之一:穷举法 北京大学信息科学技术学院 张铭、郝丹 zhang lat net. pku. edu.cn http://www.jpkpku.edu.cn/pkuipk/course/sjjg/shixi/ 2011.8 张铭赵海燕王腾蛟宋国杰;《数据结构与算法实验教 程》(国家十一五规划教材),高教社20111月

数据结构与算法实习 ——算法之一：穷举法 北京大学信息科学技术学院 张 铭、郝 丹 mzhang [at] net.pku.edu.cn http://www.jpk.pku.edu.cn/pkujpk/course/sjjg/shixi/ 2011.8 张铭 赵海燕 王腾蛟 宋国杰，《数据结构与算法实验教 程》（国家十一五规划教材），高教社2011年1月

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

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

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

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

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

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

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

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

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

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

21百钱买百鸡☆ ◆鸡翁一,值钱五,鸡母一,值钱三,鸡 雏三,值钱一。百钱买百鸡,问鸡翁、母、 雏各几何? ◆根据题意列方程: 5X+3y+z/3=100 X+y+z=100 (x,y2z>=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=100-X- if(z%3=0 &&15*x+9y+z=300) cout<<x<<<<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次

另解 ◆x=0;3整除z) 个未知数z 7X+4y=100 x+y+z=100 (x,y2z>=0;3整除z)

另解 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  x <= =20  y<= =33   100/5     100/3  

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

穷举次数大大减少  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  x <= =14  y<= =25   100/ 7     100/ 4  