枚举算法(精)课件.ppt

1、YN开始开始c i % 10 i i+1结束结束i=999YN输出输出 ii 100 i=a3+b3+c3b i / 10 % 10 a i / 100 水仙花数问题水仙花数问题: 所谓水仙花数指的是这样一些数：他们的各个位置上的数字的立方的和等于它本身，如153=13+53+33，所以153是一个水仙花数。现在要求编程求100-999之间的水仙花数，并输出。解题过程解题过程: 对于对于100-999之间的之间的每一个数每一个数, 按照水仙按照水仙花数的条件逐一进花数的条件逐一进行检验，找到一个行检验，找到一个就输出一个。就输出一个。什么是枚举算法什么是枚举算法 枚举算法就是按照问题本身的性枚

2、举算法就是按照问题本身的性质，质，一一列举出该问题所有可能一一列举出该问题所有可能的解的解，并在逐一列举的过程中，并在逐一列举的过程中，检验每个可能解是否是问题的真检验每个可能解是否是问题的真正解正解。若是，我们采纳这个解，。若是，我们采纳这个解，否则抛弃它。在列举的过程中，否则抛弃它。在列举的过程中，既不能遗漏也不应重复。既不能遗漏也不应重复。例题：例题： 一张单据上有一个一张单据上有一个5位数的编码，其千位数的编码，其千位数和百位数已经变得模糊不请。但是位数和百位数已经变得模糊不请。但是知道这个知道这个5位数是位数是57或或67的倍数。现在的倍数。现在要设计一个算法，输出所有满足这些条要设

3、计一个算法，输出所有满足这些条件的件的5位数，并统计这样的数的个数。位数，并统计这样的数的个数。No.1 47分析分析: 首先，千位数和百位数首先，千位数和百位数 可以填上可以填上00，01，02，97，98，99；得到；得到10047，10147，19947。建一个循环变量为。建一个循环变量为j，从从0到到99的一个循环，每一个可能解的一个循环，每一个可能解n的值的值为为10047+j*100 其次，对每一个其次，对每一个n判断是否能被判断是否能被57或或67整除。整除。若是，输出一组解，解的个数若是，输出一组解，解的个数+1；若不是，；若不是，舍弃舍弃算法描述算法描述1、计数器c002 2

4、、j0j03 3、判断、判断j100,j100,是转是转4 4，否转向，否转向 9 94 4、可能解、可能解 n10047+100n10047+100* *j j5 5、判断、判断n n是否是否5757或或6767的倍数，是转向的倍数，是转向6 6；否转向；否转向8 86 6、计数器、计数器c cc+1c+1；7 7、输出真正的解、输出真正的解n n8 8、j jj+1j+1；转向；转向 3 39 9、输出解的个数、输出解的个数 C C1010、结束、结束j100YN开始开始c 0 j j+1结束结束c c+1输出输出 nn 10047+j*100 n % 57=0或或n % 67=0NYj

5、0 输出输出 j采用枚举算法的条件采用枚举算法的条件仅当问题的仅当问题的所有可能所有可能解不太多解不太多的时候，才的时候，才可以使用枚举法。可以使用枚举法。枚举法解题过程枚举法解题过程例题例题2： 一张单据上有一个一张单据上有一个5位数的编码，其千位位数的编码，其千位数和十位数已经变得模糊不请。但是知数和十位数已经变得模糊不请。但是知道这个道这个5位数是位数是57或或67的倍数。现在要设的倍数。现在要设计一个算法，输出所有满足这些条件的计一个算法，输出所有满足这些条件的5位数，并统计它们的个数。位数，并统计它们的个数。No.1 4 7分析：分析： 千位数和十位数上的数字只能是0-9中的一个。1

6、0407104171042710437104471045710467104771048710497ij19407194171942719437194471945719467194771948719497iji 从从0变化到变化到9；j从从0变化变化到到9。因此，需要构造一。因此，需要构造一个双重循环。个双重循环。可能的解可能的解n 10407+1000*i+10*j双重循环的构造双重循环的构造1、i 02、判断、判断i=9；是转向；是转向3，否则转向否则转向73、j 04、判断、判断j=9；是转向；是转向5，否则转向否则转向65、j j+1； 转向转向46、i i+1；转向；转向27、结束、结

7、束i=9YN开始开始i 0 i i+1结束结束j=9Nj j+1j 0 Y思考：思考：右面的流程右面的流程图有没有问图有没有问题题i=9YN开始开始i 0 i i+1结束结束j=9Nj j+1j 0 Y算法描述算法描述j+1；转向；转向 410、i i+1；转向；转向 2i=9YN开始开始i 0 i i+1j=9Nj j+1j 0 Yc 0 c结束结束12c c+1输出输出 nn 10047+j*100 n mod 57=0或或n mod 67=0NY21x=20YN开始开始x 0 x x+1结束结束y=33Ny y+1y 0 Yxyz0010001990298 0336720 3347z 100-x-y输出输出x,y,z5*x+3*y+z/3=100NY X: 1-74 Y: 1-118 Z: 1-293x=74YN开始开始x 1 x x+1y=118Ny y+1y 1 Yz z+1 结束结束z=293z 1 判断真正的解判断真正的解 YN