枚举算法课件

枚举算法枚举算法1YN开始c←i%10i←i+1结束i<=999YN输出ii←100i=a3+b3+c3b←i/10%10a←i/100水仙花数问题:所谓水仙花数指的是这样一些数：他们的各个位置上的数字的立方的和等于它本身，如153=13+53+33，所以153是一个水仙花数。现在要求编程求100-999之间的水仙花数，并输出。解题过程:对于100-999之间的每一个数,按照水仙花数的条件逐一进行检验，找到一个就输出一个。YN开始c←i%10i←i+1结束i<=999YN2什么是枚举算法枚举算法就是按照问题本身的性质，一一列举出该问题所有可能的解，并在逐一列举的过程中，检验每个可能解是否是问题的真正解。若是，我们采纳这个解，否则抛弃它。在列举的过程中，既不能遗漏也不应重复。什么是枚举算法枚举算法就是按照问题本身的性质，一一列举出该问3例题：一张单据上有一个5位数的编码，其千位数和百位数已经变得模糊不请。但是知道这个5位数是57或67的倍数。现在要设计一个算法，输出所有满足这些条件的5位数，并统计这样的数的个数。No.147例题：一张单据上有一个5位数的编码，其千位数和百位数已经变得4分析:首先，千位数和百位数可以填上00，01，02，……97，98，99；得到10047，10147，……19947。建一个循环变量为j，从0到99的一个循环，每一个可能解n的值为10047+j*100其次，对每一个n判断是否能被57或67整除。若是，输出一组解，解的个数+1；若不是，舍弃分析:首先，千位数和百位数可以填上00，5算法描述1、计数器c←02、j←03、判断j<100,是转4，否转向94、可能解n←10047+100*j5、判断n是否57或67的倍数，是转向6；否转向86、计数器c←c+1；7、输出真正的解n8、j←j+1；转向39、输出解的个数C10、结束算法描述1、计数器c←06j<100YN开始c←0j←j+1结束c←c+1输出nn

←10047+j*100n%57==0或n%67==0NYj←0输出jj<100YN开始c←0j←j+1结束c←c+1输出7采用枚举算法的条件仅当问题的所有可能解不太多的时候，才可以使用枚举法。采用枚举算法的条件仅当问题的所有可能解不太多的时候，才可以使8枚举法解题过程逐一列举可能的解逐一检验可能的解枚举法解题的难点：1、构造循环2、确定可能的解枚举法解题过程逐一列举可能的解枚举法解题的难点：9例题2：一张单据上有一个5位数的编码，其千位数和十位数已经变得模糊不请。但是知道这个5位数是57或67的倍数。现在要设计一个算法，输出所有满足这些条件的5位数，并统计它们的个数。No.147例题2：一张单据上有一个5位数的编码，其千位数和十位数已经变10分析：千位数和十位数上的数字只能是0-9中的一个。10407104171042710437104471045710467104771048710497ij分析：千位数和十位数上的数字只能是0-9中的一个。101119407194171942719437194471945719467194771948719497iji从0变化到9；j从0变化到9。因此，需要构造一个双重循环。可能的解n←10407+1000*i+10*j19407194171942719437194471945712双重循环的构造1、i←02、判断i<=9；是转向3，否则转向73、j←04、判断j<=9；是转向5，否则转向65、j←j+1；转向46、i←i+1；转向27、结束i<=9YN开始i←0i←i+1结束j<=9Nj←j+1j←0Y双重循环的构造1、i←0i<=9YN开始i←0i←i13思考：

右面的流程图有没有问题i<=9YN开始i←0i←i+1结束j<=9Nj←j+1j←0Y思考：

右面的流程图有没有问题i<=9YN开始i←0i14算法描述1、c←0；i←02、判断i<=9；是转向3，否则转向113、j←04、判断j<=9；是转向5，否则转向105、n←10407+1000*i+10*j6、判断n是否57或67的倍数，是转向7；否转向97、计数器c←c+1；8、输出一个真正的解n9、j←j+1；转向410、i←i+1；转向211、输出解的个数c12、结束算法描述1、c←0；i←015i<=9YN开始i←0i←i+1j<=9Nj←j+1j←0Yc←0c结束12c←c+1输出nn

←10047+j*100nmod57=0或nmod67=0NY21i<=9YN开始i←0i←i+1j<=9Nj←j+116例题3百鸡百钱问题“鸡翁一值钱5，鸡母一值钱3，鸡雏三值钱1”现有100钱，欲买100只鸡，问：鸡翁、鸡母、鸡雏各买几只？分析：设x，y，z分别为买的鸡翁、鸡母、鸡雏的个数则：x+y+z=1005*x+3*y+z/3=100可能的解X:0-20Y:0-33Z:100-x-y例题3百鸡百钱问题分析：17建立一个双重循环,可能的解如下：x<=20YN开始x←0x←x+1结束y<=33Ny←y+1y←0Y判断可能的解是否是真正的解xyz0010001990298………03367………203347建立一个双重循环,可能的解如下：x<=20YN开始x←018检验可能的解是否真正的解判断：5*x+3*y+z/3=100若是，x,y,z就是一个真正的解z←100-x-y输出x,y,z5*x+3*y+z/3=100NY检验可能的解是否真正的解判断：5*x+3*y+z/3=10019例题4包装问题：600个变形金刚，包装的规格为：大盒（8个）、中盒（5个）、小盒（2个）；每种规格的盒都不能为空。请设计一个算法，输出所有可能的包装方案。分析：设大中小盒的个数分别为x,y,z则：8*x+5*y+2*z=600X：1-74Y：1-118Z：（600-8*x-5*y）/2例题4包装问题：分析：20算法提示构造一个双重循环，循环变量分别为x（大盒数量）和y（中盒数量）。判断：Z=(600-8*x-5*y)/2是否是整数;若是，则x,y,z就是一个包装方案。算法提示构造一个双重循环，循环变量分别为x（大盒数