研究生课程-算法设计与分析之枚举算法课件.ppt

1、算法设计与分析算法设计与分析北京交通大学计算机与信息技术学院 李清勇李清勇E-mail:Tel:51688603主校区:9号楼 北314课前面试o 找出找出“水仙花数水仙花数”“水仙花数”是一个神奇的3位数，其各位数字立方和等于该数本身。例如，153就是一水仙花数。怎样找出所有的“水仙花数”？3位数（100999）各位数字立方和等于该数本身课前面试p 猴子分桃猴子分桃五只猴子一起摘了一堆桃子，因为太累了，它们商量决定，先睡一觉再分。一会其中的一只猴子来了，它见别的猴子没来，便将这堆桃子平均分成5份，结果多了一个，就将多的这个吃了，并拿走其中的一份。一会儿，第2只猴子来了，他不知道已经有一个同伴

2、来过，还以为自己是第一个到的呢，于是将地上的桃子堆起来，再一次平均分成5份，发现也多了一个，同样吃了这1个，并拿走其中一份。接着来的第3、第4、第5只猴子都是这样做的根据上面的条件，问这5只猴子至少摘了多少个桃子?第5只猴子走后还剩下多少个桃子?枚举算法基本思想o 枚举算法枚举算法 也称之为穷举算法，就是按照问题本身的性质，一一一一列举出该问题所有可能的解列举出该问题所有可能的解，并在列举的过程中，逐一逐一检验每个可能解是否是问题的真正解检验每个可能解是否是问题的真正解。若是，则采纳这个解；否则抛弃它。不能遗漏不能遗漏 不要重复不要重复枚举算法基本思想o 枚举算法枚举算法 也称之为穷举算法，就

3、是按照问题本身的性质，一一一一列举出该问题所有可能的解列举出该问题所有可能的解，并在列举的过程中，逐一逐一检验每个可能解是否是问题的真正解检验每个可能解是否是问题的真正解。若是，则采纳这个解；否则抛弃它。解的高准确性和全面性解的高准确性和全面性 实现简单，枚举算法通过循环来逐一列举和验证可能解实现简单，枚举算法通过循环来逐一列举和验证可能解 效率提升空间比较大效率提升空间比较大 枚举三步1.确定枚举对象确定枚举对象 枚举对象也可以理解为是问题解的表达形式，一般需要用若干参数来描述一般需要用若干参数来描述o参数之间需要相互独立，而且，参数数目越少，问题解的搜索空间的维度也相应地小；o每个参数的取

4、值范围越小，问题解的搜索空间也越小。2.逐一列举可能解逐一列举可能解 根据枚举对象的参数构造循环构造循环，一一列举其表达式的每一种取值情况。3.逐一验证可能解逐一验证可能解 根据问题解的要求，一一验证一一验证枚举对象表达式的每一个取值，如果满足条件，则采纳它，否则，抛弃之。模糊数字任务描述任务描述：一张单据上有一个5位数的编码，因为保管不善，其百位数已经变得模糊不请。但是知道这个5位数是57和67的倍数。现在要设计一个算法，输出所有满足这些条件的5位数，并统计这样的数的个数。输入：输入：每一行对应一个测试样例，每一行包含4个数字，依次是万位数，千位数，十位数和个位数。最后一行包含4个-1，表示

5、输入结束。输出：输出：每组测试样例的结果输出占一行，第一个数字表示满足条件的编码个数，后面按升序输出所有满足条件的编码，数字与数字之间用空格隔开。19？95模糊数字o 枚举对象 Obj(h)：记h百位数数字，h=09o 逐一列举 for(h=0;h10;h+)o 逐一验证 19h95能否整除57和67模糊数字续o 任务描述：任务描述：一张单据上有一个5位数的编码，因为保管不善，其万位数字和百位数已经变得模糊不请。但是知道这个5位数是57和67的倍数。现在要设计一个算法，输出所有满足这些条件的5位数，并统计这样的数的个数。o 输入：输入：每一行对应一个测试样例，每一行包含3个数字，依次是千位数，

6、十位数和个位数。最后一行包含3个-1，表示输入结束。o 输出：输出：每组测试样例的结果输出占一行，第一个数字表示满足条件的编码个数，后面按升序输出所有满足条件的编码，数字与数字之间用空格隔开。？9？95模糊数字续o 枚举对象obj(d1,d2)万位数数字，记为d1，d1=19百位数数字，记为d2，d2=09o 逐一列举 for(d1=1;d110;d1+)for(d2=0;d210;d2+)o 逐一验证 d1 9 d2 95能否整除57和67模糊数字再续o 任务描述：任务描述：一张单据上有一个5位数的编码，因为保管不善，其万位数字万位数字和千位数千位数已经变得模糊不请。但是知道这个5位数是57

7、和67的倍数。现在要设计一个算法，输出所有满足这些条件的5位数，并统计这样的数的个数。o 输入：输入：每一行对应一个测试样例，每一行包含3个数字，依次是百位数，十位数和个位数。最后一行包含3个-1，表示输入结束。o 输出：输出：每组测试样例的结果输出占一行，第一个数字表示满足条件的编码个数，后面按升序输出所有满足条件的编码，数字与数字之间用空格隔开。？095m钱n鸡o 任务描述任务描述：我国古代数学家张丘建在算经中出了一道题“鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一。百钱买百鸡，问鸡翁、鸡母、鸡雏各几何？”，现在假定各鸡种的价格不变，拥有的钱数为m，需要购买的鸡数为n，试求出所有可能的购

8、买方案总数。o 输入输入：每行对应一个测试样例，每一行包含2个数字，分别为n 和m。最后一行包含2个-1，表示输入结束。o 输出输出：每组测试样例的结果输出占一行，输出可能购买方案总数。m钱n鸡o 枚举对象obj(n1，n2，n3)鸡翁数，记为n1，n1=0n鸡母数，记为n2，n2=0n鸡雏数，记为n3，n3=0no 逐一列举 三层for循环嵌套o 逐一验证 n1+n2+n3=n,5n1+3n2+n3/3=mm钱n鸡-改进o 枚举对象obj(n1，n2)鸡翁数，记为n1，n1=0m/5鸡母数，记为n2，n2=0m/3鸡雏数，记为n3，n3=n-n1-n2o 逐一列举 二层for循环嵌套o 逐一

9、验证 5n1+3n2+n3/3=m算法复杂度O(m2)真假银币o任务描述：任务描述：张三有12枚银币，其中有11枚真币和1枚假币。假币看起来和真币完全一样，但是他们的重量不一样。很遗憾的是，张三不知道假币比真币轻还是重。但是他办公室有一架天平，还有一个聪明的助手。经过精心安排每次的称重，助手保证在称3次后确定发现假币。助手想跟张三开一个小小的玩笑，只告诉他每次称重的方案和天平的状态，但是不告诉他哪个是假币，假币比真币轻还是重。请设计一个算法帮张三辨别真假银币。o输入：输入：第一行包含一个正整数，表示测试数据的组数。每组测试数据有三行，每行表示一次称重的结果。张三和助手事先把银币标号为AL。每次

10、称重的结果用3个以空格隔开的字符串表示：天平左边放置的银币标号，天平右边放置的银币标号，以及平衡状态。其中平衡状态用“up”、“down”和“even”表示，分别表示右端高、右端低和平衡。另外，每次称重天平左右的银币数总是相等的。o输出：输出：每组测试数据的输出占一行，输出假银币的标号，并指明它比真币轻还是重，请则输出 light，重则输出 heavy。真假银币o 输入样例：输入样例：1ABCD EFGH evenABCI EFJK upABIJ EFGH eveno 输出样例：输出样例：K light真假银币o 枚举对象obj(c,s)c 为银币标号，c=ALs 为银币性质，s=轻，重，真o

11、 逐一列举o 逐一验证“Even”状态,天平任意一端出现s,则s不可能为轻的假币；“Up”状态,天平右端没有出现右端没有出现s s,则s不可能为轻的假币；“Down”状态,天平左端没有出现左端没有出现s s,则s不可能为轻的假币；“Even”状态,天平任意一端出现s,则s不可能为重的假币；“Up”状态,天平左端没有出现左端没有出现s s,则s不可能为重的假币；“Down”状态,天平右端没有出现右端没有出现s s,则s不可能为重的假币；判断比真币轻判断比真币重课后思考题题一：题一：给一个很长的数字串S：123456891011121314，它是由所有的自然数从小到大依次排列起来的。任意给一个数字串S1(其长度不大于10)，求出S1在S中第一次出现的位置。比如：输入101，输出为10考虑：2132课后思考题题二：题二：形如ax3+bx2+cx+d=0 的一个一元三次方程。给出该方程中各项的系数(a，b，c，d 均为实数)，并约定该方程存在三个不同实根(根的范围在-100至100之间)，且根与根之差的绝对值大于或等于1。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后2位。提示：提示：记方程f(x)=0，若存在2个数x1和x2，且x1x2，f(x1)*(x2)0，则在(x1,x2)之间一定有一个根。