5.1 枚举算法的程序实现 课件（17张PPT）

课件17张PPT。知识小结温故知新课堂演练算法思想情景导入枚举算法的程序实现自修课时，班干部小明约了几个同学一起到选修教室召开班委会，可是粗心的小明从老师那儿拿到钥匙的时候，却忘记了到底哪一把才是教室的钥匙(配套的钥匙有若干把)。问题：怎样才能找到正确的钥匙来开门？配套钥匙共有多少把？ 找钥匙的过程2.拿出第二把钥匙， 试验第二把钥匙能否开门；1.拿出第一把钥匙， 试验第一把钥匙能否开门；3.拿出第三把钥匙， 试验第三把钥匙能否开门；6.拿出第七把钥匙， 试验第七把钥匙能否开门。······列举检验枚举法　　枚举算法就是根据问题本身的性质，一一列举出该问题所有可能的解，并根据问题的条件对各解进行逐个检验，从中挑选出符合条件的解，舍弃不符合条件的解。一一列举，逐个检验在联欢会上，小明提议大家来玩数8的游戏。 游戏规则：从1开始数起，每个人数一个数，凡是遇 到8的倍数就要喊“过”这样一直数到100为止。问题:帮小明找出1—100所有要喊“过”的数？任务一列举检验分析：用变量i表示要列举的自然数。列举范围：1———100检验条件：i 能否被8整除注意：在列举过程中要既不遗漏，又不重复。 NNYYi<=100 i mod 8=0 i=i+1 i=1 输出i 列举范围：1———100检验条件：i能否被8整除用变量i表示要列举的自然数。开始结束一一列举逐个检验（循环结构）（分支结构）循环中嵌套分支 NNYYi<=100 i mod 8=0 i=i+1 i=1 输出i 开始结束 NNYYi<=100 i mod 8=0 i=i+1 i=1 输出i 开始结束程序代码1: i=1 Do while i<=100 if i mod 8=0 then print i end if i=i+1 loop程序代码2: For i=1 to 100 step 1 if i mod 8=0 then print i Next i 确定列举范围 明确检验条件 确定循环控制方式和列举方式注意： 为提高算法效率，应尽可能缩小解的列举范围。设计步骤：水仙花数：（任务二） 　　如果一个三位正整数等于它的每个数字的立方和，则此数称为“水仙花”数。（例如：1^3 + 5^3 + 3^3 = 153）问题：请找出三位数的中所有的水仙花数 下列程序用于求出100—999之间的所有“水仙花”数，请将方框内的语句补充完整。Private sub Command1 Click() Dim m As Integer ,n As Integer Dim a As Integer,b As Integer Dim c As Integer For m=100 to 999 a = m100 b = m10 mod 10 c = n = a^3+b^3+c^3 if 　　then list1.AddItem str(m) End if Next m答案１答案２ m mod 10 m = n武器装箱： 　　共有100件武器需要装箱。现有大、小两种箱子，小箱每个可装10件武器，大箱每个可装20件武器。 问题：求出所有可能的装箱方案拓展提升：1.枚举算法的概念2.枚举算法的结构特征4.枚举算法的注意点3.枚举算法的设计步骤一一列举；逐个检验循环结构中嵌套分支结构确定列举范围；明确检验条件尽可能缩小解的列举范围习题巩固：１、假定公鸡每只５元，母鸡每只３元，小鸡每只５角，每种鸡都要买。现有100元，要买100只鸡，问有多少种方案（百钱买百鸡）。求解这个问题，最适合的算法是（　　　　）Ａ、枚举Ｂ、解析Ｃ、排序Ｄ、查找２、若用枚举法来求解，母鸡数量的枚举范围应为（　　　　）Ａ、[0，100]Ｂ、[1，33]Ｃ、[0， 33]Ｄ、[1，25]答案答案自我评价： ... ...