枚举法教案专业知识公开课一等奖优质课大赛微课获奖课件.pptx

第1页第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页第2页什么是枚举算法什么是枚举算法枚举算法就是按照问题本身性质，枚举算法就是按照问题本身性质，一一列举出该问题所有也许解一一列举出该问题所有也许解，并，并在逐一列举过程中，在逐一列举过程中，检查每个也许检查每个也许解是否是问题真正解解是否是问题真正解。若是，我们。若是，我们采纳这个解，不然抛弃它。在列举采纳这个解，不然抛弃它。在列举过程中，既不能漏掉也不应重复。过程中，既不能漏掉也不应重复。第3页第3页例题：例题：一张单据上有一个一张单据上有一个5位数编码，其千位位数编码，其千位数和百位数已经变得模糊不请。但是知数和百位数已经变得模糊不请。但是知道这个道这个5位数是位数是57或或67倍数。现在要设倍数。现在要设计一个算法，输出所有满足这些条件计一个算法，输出所有满足这些条件5位数，并统计这样数个数。位数，并统计这样数个数。No.1 47第4页第4页分析分析:首先，千位数和百位数首先，千位数和百位数 能够填上能够填上00，01，02，97，98，99；得到；得到10047，10147，19947。建一个循环变量为。建一个循环变量为j，从从0到到99一个循环，每一个也许解一个循环，每一个也许解n值为值为10047+j*100另一方面，对每一个另一方面，对每一个n判断是否能被判断是否能被57或或67整除。若是，输出一组解，解个数整除。若是，输出一组解，解个数+1；若；若不是，舍弃不是，舍弃第5页第5页算法描述算法描述1、计数器c002 2、j0j03 3、判断、判断j100,j100,是转是转4 4，否转向，否转向 9 94 4、也许解、也许解 n10047+100*jn10047+100*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、结束、结束第6页第6页j100YN开始开始c 0 j j+1结束结束c c+1输出输出 nn 10047+j*100 n%57=0或或n%67=0NYj 0 输出输出 j第7页第7页采用枚举算法条件采用枚举算法条件仅当问题仅当问题所有也许解所有也许解不太多不太多时候，才干够时候，才干够使用枚举法。使用枚举法。第8页第8页枚举法解题过程枚举法解题过程逐一列举也许解逐一列举也许解逐一检查也许解逐一检查也许解枚举法解题难点：枚举法解题难点：1、结构循环、结构循环2、拟定也许解、拟定也许解第9页第9页例题例题2：一张单据上有一个一张单据上有一个5位数编码，其千位数位数编码，其千位数和十位数已经变得模糊不请。但是知道和十位数已经变得模糊不请。但是知道这个这个5位数是位数是57或或67倍数。现在要设计一倍数。现在要设计一个算法，输出所有满足这些条件个算法，输出所有满足这些条件5位数，位数，并统计它们个数。并统计它们个数。No.1 4 7第10页第10页分析：分析：千位数和十位数上数字只能是0-9中一个。10407104171042710437104471045710467104771048710497ij第11页第11页19407194171942719437194471945719467194771948719497iji 从从0改变到改变到9；j从从0改变改变到到9。因此，需要结构一。因此，需要结构一个双重循环。个双重循环。也许解也许解n 10407+1000*i+10*j第12页第12页双重循环结构双重循环结构1、i 02、判断、判断i=9；是转向；是转向3，不然转向不然转向73、j 04、判断、判断j=9；是转向；是转向5，不然转向不然转向65、j j+1；转向转向46、i i+1；转向；转向27、结束、结束i=9YN开始开始i 0 i i+1结束结束j=9Nj j+1j 0 Y第13页第13页思考：思考：右面流程图右面流程图有无问题有无问题i=9YN开始开始i 0 i i+1结束结束j=9Nj j+1j 0 Y第14页第14页算法描述算法描述1 1、c c 0 0；i i 002 2、判断、判断、判断、判断i=9i=9；是转向；是转向；是转向；是转向 3 3，不然转向，不然转向，不然转向，不然转向 11113 3、j j 004 4、判断、判断、判断、判断j=9j=9；是转向；是转向；是转向；是转向 5 5，不然转向，不然转向，不然转向，不然转向 10105 5、n n 10407+1000*i+10*j10407+1000*i+10*j6 6、判断、判断、判断、判断n n是否是否是否是否5757或或或或6767倍数，是倍数，是倍数，是倍数，是转向转向转向转向 7 7；否转向；否转向；否转向；否转向 9 97 7 7 7、计数器、计数器、计数器、计数器 c c c+1c+1；8 8、输出一个真正解、输出一个真正解、输出一个真正解、输出一个真正解 n n9 9、j j j+1；转向；转向 410、i i+1；转向；转向 21111、输出解个数、输出解个数、输出解个数、输出解个数 c c1212、结束、结束、结束、结束第15页第15页i=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=0NY21第16页第16页例题例题3百鸡百钱问题百鸡百钱问题 “鸡翁一值钱鸡翁一值钱5，鸡母一值钱鸡母一值钱3，鸡雏三值钱鸡雏三值钱1”既有既有100钱，欲钱，欲买买100只鸡，问：只鸡，问：鸡翁、鸡母、鸡鸡翁、鸡母、鸡雏各买几只？雏各买几只？分析：分析：设设x，y，z分别为买鸡翁、分别为买鸡翁、鸡母、鸡雏个数鸡母、鸡雏个数则：则：x+y+z=100 5*x+3*y+z/3=100也许解也许解X:0-20Y:0-33Z:100-x-y第17页第17页建立一个双重循环建立一个双重循环,也许解下列：也许解下列：x=20YN开始开始x 0 x x+1结束结束y=33Ny y+1y 0 Y判断也许解判断也许解判断也许解判断也许解是否是真正解是否是真正解是否是真正解是否是真正解xyz0010001990298 0336720 3347第18页第18页检查也许解是检查也许解是否真正解否真正解判断：判断：判断：判断：5*x+3*y+z/3=1005*x+3*y+z/3=100若是，若是，若是，若是，x,y,zx,y,z就是一个真就是一个真就是一个真就是一个真正解正解正解正解z 100-x-y输出输出x,y,z5*x+3*y+z/3=100NY第19页第19页例题例题4包装问题：包装问题：600个变形金刚，包个变形金刚，包装规格为：大盒（装规格为：大盒（8个）个）、中盒（、中盒（5个）、小盒个）、小盒（2个）；每种规格盒个）；每种规格盒都不能为空。请设计都不能为空。请设计一个算法，输出所有一个算法，输出所有也许包装方案。也许包装方案。分析：分析：分析：分析：设大中小盒个数分别为设大中小盒个数分别为设大中小盒个数分别为设大中小盒个数分别为x,y,zx,y,z则：则：则：则：8*x+5*y+2*z=6008*x+5*y+2*z=600X X：1-741-74Y Y：1-1181-118Z Z：（：（：（：（600-8*x-5*y600-8*x-5*y）/2/2第20页第20页算法提醒算法提醒结构一个双重循环，循环变量分别为结构一个双重循环，循环变量分别为x（大（大盒数量）和盒数量）和y（中盒数量）。（中盒数量）。判断：判断：Z=(600-8*x-5*y)/2是否是整数是否是整数;若是，若是，则则x,y,z就是一个包装方案。就是一个包装方案。第21页第21页关于三重循环关于三重循环X:1-74Y:1-118Z:1-293x=74YN开始开始x 1 x x+1y=118Ny y+1y 1 Yz z+1 结束结束z=293z 1 判断真正解判断真正解 YN第22页第22页