枚举法教案专业知识市公开课获奖课件

1、枚举算法第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页什么是枚举算法枚举算法就是按照问题本身性质，一一列举出该问题所有也许解，并在逐一列举过程中，检查每个也许解是否是问题真正解。若是，我们采纳这个解，不

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、计数器c02、j03、判断j100,是转

3、4，否转向 94、也许解 n10047+100*j5、判断n是否57或67倍数，是转向6；否转向86、计数器cc+1；7、输出真正解n8、jj+1；转向 39、输出解个数 C10、结束第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位数编码，其千位数和十位数已经变得模糊不请。但是知道这个

4、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、转向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、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

6、5页第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

7、Y判断也许解是否是真正解xyz0010001990298 0336720 3347第18页第18页检查也许解是否真正解判断：5*x+3*y+z/3=100若是，x,y,z就是一个真正解z 100-x-y输出x,y,z5*x+3*y+z/3=100NY第19页第19页例题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第20页第20页算法提醒结构一个双重循环，循环变量分别为x（大盒数量）和y（中盒数量）。判断：Z=(600-8*x-5*y)/2是否是整数; 若是，则x,y,