枚举算法(课件)

1、（穷举算法）（穷举算法）找找 钥钥 匙匙自行车胎坏掉的时候，修车师傅检查坏掉的位置，自行车胎坏掉的时候，修车师傅检查坏掉的位置，他选定某一个位置为起始位置，然后按顺序一块块他选定某一个位置为起始位置，然后按顺序一块块的检查过来，直到找到坏掉的位置。的检查过来，直到找到坏掉的位置。找到一个坏掉的位置后，还要继续找吗？为了安全找到一个坏掉的位置后，还要继续找吗？为了安全起见，建议继续找起见，建议继续找讨讨 论：论：解决以上两个实际生活问题时，主要经过了哪解决以上两个实际生活问题时，主要经过了哪几个步骤？几个步骤？步骤一、一步骤一、一 一列举所有可能解一列举所有可能解步骤二、逐一检验，不重复，不遗漏

2、步骤二、逐一检验，不重复，不遗漏 按问题本身的性质，按问题本身的性质，一一列举该问题所一一列举该问题所有可能的解有可能的解，并在逐一列举的过程中，并在逐一列举的过程中，检验检验每个可能解是否是问题的真正解每个可能解是否是问题的真正解，如是，就，如是，就采纳这个解，否则就抛弃它不重复，不遗采纳这个解，否则就抛弃它不重复，不遗漏。漏。枚举法适合于解的候选者是有限、可列举的场合。枚举法适合于解的候选者是有限、可列举的场合。枚举法的算法一般都比较直观，容易理解。枚举法的算法一般都比较直观，容易理解。但由于要检查所有的候选解，因此时间性能较差。但由于要检查所有的候选解，因此时间性能较差。算一算：算一算：

3、 用用10元和元和50元两种纸币组成元两种纸币组成240元，元，共有几种组合方式？共有几种组合方式？（0张50元）24张10元（1张50元）19张10元（2张50元）14张10元（3张50元） 9张10元（4张50元） 4张10元在在1到到2008这些自然数中，找出所有是这些自然数中，找出所有是37倍数的自然数倍数的自然数开始开始初始初始i1i2008?结束结束i能被能被37整除？整除？输出输出iii+1NYNY以上提供的只是一种求被以上提供的只是一种求被37整除的数的算法，你有没有更整除的数的算法，你有没有更好的算法？好的算法？思思 考：考：枚枚 举举 算算 法法 举举 例例 问题：一张单据

4、上有一个5位数的编号，其百位数和十位数已经变得模糊不清，如下图所示，但是知道这个5位数是37或67的倍数，现在请你找出所有可能的五位数,并统计这样数的个数？枚枚 举举 算算 法法 举举 例例 算法：算法：25ab6ab是百位和十位上的数字，可能的取值是百位和十位上的数字，可能的取值五位数五位数(n)如何表示：如何表示：00-99,故从故从0开始列举到开始列举到99n能被能被37或者或者67整除时，就是一个真正解整除时，就是一个真正解n=25006+ab*10Dim j, n, c As Integer c = 0 List1.Clear For j = 0 To 99 n = 25006 +

5、j * 10 If Then List1.AddItem Str(n) c = c + 1 End If Next j List1.AddItem 总计有总计有 + Str(c) + 个五位数个五位数n Mod 37 = 0 Or n Mod 67 = 0小结：小结：确定范围确定范围情况罗列情况罗列条件判断条件判断得到真解得到真解循环语句循环语句选择语句选择语句用枚举算法解决问题一般过程用枚举算法解决问题一般过程:用枚举算法解决问题须注意以下两点用枚举算法解决问题须注意以下两点:（1）不能遗漏任何一个真正解。）不能遗漏任何一个真正解。（2）缩小搜索范围，提高效率。）缩小搜索范围，提高效率。枚举

6、算法的解题过程分两步枚举算法的解题过程分两步 逐一列举可能的解的范围。逐一列举可能的解的范围。这个过程用这个过程用循环结构循环结构实现实现 并对每一个列举可能的解进行检验，判断是否为真正并对每一个列举可能的解进行检验，判断是否为真正的解的解 。这个过程用这个过程用选择结构选择结构实现实现 枚举算法枚举算法=循环结构循环结构+选择结构选择结构 循环结构内嵌套选择结构循环结构内嵌套选择结构NO. 2 5 6思考：假如现在这张单据是千位和十位上的两个数字看不清，这张单据上的五位数还是37或67的倍数，现在要找出所有的可能解，并统计个数。如何解决这个问题？NO. 2 5 6两个数分别在千位和十位上。千

7、位上可能的数：09 (i)十位上可能数数：09 (j)所以需要两个循环变量：i 和jn=20506+i*1000+j*10Dim i, j, n, c As Integer c = 0 For i = 0 To 9 For j = 0 To 9 n = 20506 + i * 1000 + j * 10 If n Mod 37 = 0 Or n Mod 67 = 0 Then Print n c = c + 1 End If Next jNext i Label1.Caption = 总共可能有 & Str(c) & 个五位数人有了知识，就会具备各种分析能力，明辨是非的能力。所以我们要勤恳读书，广泛阅读，古人说“书中自有黄金屋。”通