实用的枚举算法(2)

1、想一想？想一想？ 一天早上，数学课代表收好了数学练一天早上，数学课代表收好了数学练习本，他的同桌物理课代表收好了物习本，他的同桌物理课代表收好了物理练习本，但是由于一些意外，两种理练习本，但是由于一些意外，两种练习本混在了一起。现在要把混在一练习本混在了一起。现在要把混在一起的起的7474本练习本区分开，假如你是数本练习本区分开，假如你是数学课代表，你会怎么做？学课代表，你会怎么做？ 实用的枚举算法实用的枚举算法1313计职计职 廖鹏飞廖鹏飞一、一、什么是枚举法？什么是枚举法？ 这种列举出所有可能的情况并逐一进行检验，这种列举出所有可能的情况并逐一进行检验，根据检验的结果执行相应操作的方法就是

2、根据检验的结果执行相应操作的方法就是枚举法枚举法。 枚举法的处理过程：枚举法的处理过程： 按问题本身的性质，一一归纳概括出该问题按问题本身的性质，一一归纳概括出该问题所有可能的解，在此范围内对所有可能的情况逐所有可能的解，在此范围内对所有可能的情况逐一验证。若某个情况符合条件，则为一个解；并一验证。若某个情况符合条件，则为一个解；并继续验证其他情况。若全部情况均不符合条件，继续验证其他情况。若全部情况均不符合条件，则问题无解。则问题无解。二、二、枚举算法的关键步骤枚举算法的关键步骤：1 1、确定列举范围确定列举范围 ( ( 注意点：枚举范围不遗漏、不注意点：枚举范围不遗漏、不重复重复 ) )2

3、 2、循环列举所有可能的解循环列举所有可能的解3 3、检验是否是问题的真正解检验是否是问题的真正解分析分析C=74Y列举检验是否继续列举YNC=C+1打开一本作业是数学作业吗放在左边放在右边YNC=1N例例1.1.水仙花数水仙花数水仙花数：是指一个三位正整数,它的每个位上的数字的3次幂之和 等于它本身（例如：13+53+33=153）（1 1）算法分析）算法分析v 水仙花数是三位数的整数，从水仙花数是三位数的整数，从100100到到999999共共900900种可能，罗列问题所有可种可能，罗列问题所有可能的解并判断每个位上数字的能的解并判断每个位上数字的3 3次方之次方之和是恰好等于它本身，使

4、用运算符和是恰好等于它本身，使用运算符MODMOD和、对每个整数进行分解，分别得到和、对每个整数进行分解，分别得到百位上的数字、十位上的数字和个位百位上的数字、十位上的数字和个位上的数字。上的数字。（1 1）算法分析）算法分析开始i=100i1000?处理数i，得到其百、十、各位上的数字分别放入变量a、b、c中a3+b3+c3=i？输出一个水仙花数ii=i+1结束YNYN列举检验（2 2）分析并编写程序代码）分析并编写程序代码vPrivate Sub Command1_Click()Private Sub Command1_Click()vDim sum As IntegerDim sum A

5、s IntegervDim i, a, b, c As IntegerDim i, a, b, c As IntegervFor i = 100 To 999For i = 100 To 999va = i 100a = i 100vb = i 10 Mod 10b = i 10 Mod 10vc = i Mod 10c = i Mod 10vIf a 3 + b 3 + c 3 = i ThenIf a 3 + b 3 + c 3 = i ThenvList1.AddItem (Str(i)List1.AddItem (Str(i)vsum = sum + 1sum = sum + 1vEn

6、d IfEnd IfvNext iNext ivLabel1.Caption = Label1.Caption = 个数个数: + Str(sum): + Str(sum)vEnd SubEnd Sub东北师大附中东北师大附中开始i=100i=100i1000?i1000?处理数处理数i i，得到其，得到其百、十、各位上百、十、各位上的数字分别放入的数字分别放入变量变量a a、b b、c c中中a3+b3a3+b3+c3=i+c3=i输出一个水输出一个水仙花数仙花数i ii=i+1i=i+1结束YNYN程序设计界面程序设计界面labellistcommand例例2.2.数数7 7问题问题v在联

7、欢会上，小明提议大家来玩数在联欢会上，小明提议大家来玩数7 7的的游戏。游戏。v游戏规则：从游戏规则：从1 1开始数起，每个人数一开始数起，每个人数一个数，凡是遇到个数，凡是遇到7 7的倍数就要喊的倍数就要喊“过过”，这样一直数到，这样一直数到100100为止。为止。v任务：帮小明找出任务：帮小明找出1-1001-100所有要喊所有要喊“过过”的数！的数！（2 2）算法分析）算法分析用变量用变量i i表示要列举的自然数表示要列举的自然数列举检验列举范围：1-100检验条件：i能否被7整除在列举过程中要既不遗漏，又不重复（2 2）算法分析）算法分析用变量用变量i i表示要列举的自然数表示要列举的

8、自然数列举检验列举范围：1-100检验条件：i能否被7整除i=1开始?输出ii=i+1N?Y结束YN(3)(3)编写程序代码编写程序代码Private Sub Command1_Click()Private Sub Command1_Click()Dim i As IntegerDim i As Integeri = 1i = 1Do While i = 100Do While i = 100If i Mod 7 = 0 ThenIf i Mod 7 = 0 ThenPrint iPrint iEnd IfEnd Ifi = i + 1i = i + 1LoopLoopEnd SubEnd S

9、ub例例3 3、钱币问题、钱币问题v小张现有面值为小张现有面值为1 1元、元、2 2元和元和5 5元的钞票元的钞票（假设每种钞票的数量都足够多），（假设每种钞票的数量都足够多），如果小张想从这些钞票中取出如果小张想从这些钞票中取出3030张用张用来换取小李的来换取小李的100100元，问有小张有多少元，问有小张有多少种取法？输出每种取法中各种面额钞种取法？输出每种取法中各种面额钞票的张数票的张数（1 1）分析问题）分析问题v本问题有本问题有3 3种面值的钞票，钞票的总张种面值的钞票，钞票的总张数是数是3030张，应当如何穷举呢？经分析张，应当如何穷举呢？经分析可以知道：当有两种面额的钞票数目可

10、以知道：当有两种面额的钞票数目确定了之后，可以从张数确定了之后，可以从张数3030确定第三确定第三种钞票的张数，然后由总面额是否种钞票的张数，然后由总面额是否100100元而判断这个组合是否合乎要求元而判断这个组合是否合乎要求. .（2 2）设计算法）设计算法v用用ONEONE、TWOTWO、FIVEFIVE分别表示分别表示1 1元，元，2 2元、元、5 5元元钞票的张数。变量钞票的张数。变量ANSWERANSWER记录符合条件的记录符合条件的解的数目、钞票的张数（用变量解的数目、钞票的张数（用变量P P表示）和表示）和面额的总数（用变量面额的总数（用变量T T表示）都通过输入框表示）都通过输

11、入框来输入。来输入。（2 2）设计算法）设计算法v 枚举枚举举过程如下举过程如下：v 让让ANSWERANSWER0 0，FIVEFIVE0 0；v TWO TWO0 0；v 让让ONEONEPiecesPiecesTWOTWOFIVEFIVEv 检查检查5 5FIVEFIVE2 2TWOTWOONEONE是否等于是否等于T T，若是，则得，若是，则得到一组解，这时让到一组解，这时让ANSWERANSWER增加增加1 1。并且输出解答；。并且输出解答；v 如果如果TWOTWOP P，那么让，那么让TWOTWO增加增加1 1，返回步骤；，返回步骤；v 如果如果FIVEFIVET/5T/5，那么让

12、，那么让FIVEFIVE增加增加1 1，返回步骤；，返回步骤；v 结束结束（2 2）设计算法）设计算法结束Answer=0five=0two=0One=30-five-two5*five+2*two+one=T?TwoPfiveT/5开始two=two+1Five=five+1Answer=answer+1输出答案YNNNYY（3 3）程序代码）程序代码vPrivate Sub Command1_Click()Private Sub Command1_Click()v Dim p, t, five, two, one As Integer Dim p, t, five, two, one As

13、 Integerv p = Val(InputBox( p = Val(InputBox(钱币张数：钱币张数：, , 30) , , 30) 钞票张数的默认值为钞票张数的默认值为3030v t = Val(InputBox( t = Val(InputBox(要求组成的总值：要求组成的总值：, , 100) , , 100) 总面值默认为总面值默认为100100v Answer = 0 Answer = 0v For five = 0 To t / 5 For five = 0 To t / 5v For two = 0 To p - five For two = 0 To p - fivev

14、 one = p - five - two one = p - five - twov k = 5 k = 5 * * five + 2 five + 2 * * two + one two + onev If k = t Then If k = t Thenv Answer = Answer + 1 Answer = Answer + 1v Print Print 解决方案解决方案; Answer; :; Answer; :v Print Tab(10); 5 Print Tab(10); 5元钞票元钞票; five; ; five; 张张;v Print Tab(25); 2 Print

15、Tab(25); 2元钞票元钞票; two; ; two; 张张;v Print Tab(40); 1 Print Tab(40); 1元钞票元钞票; one; ; one; 张张 v Print Printv End If End Ifv Next two, five Next two, fivevEnd SubEnd Sub三、三、枚举算法的结构特点枚举算法的结构特点v逐一列举和检验，用循环结构实现。逐一列举和检验，用循环结构实现。v关键步骤：确定列举范围、循环列举关键步骤：确定列举范围、循环列举、检验。、检验。v检验就是对某个给定的条件进行判断检验就是对某个给定的条件进行判断，根据判断的

16、不同结果执行不同操作，根据判断的不同结果执行不同操作，所以检验可用分支结构实现。，所以检验可用分支结构实现。 三、枚举算法的结构特点三、枚举算法的结构特点列举检验是否继续列举YN四、算法结构的优缺点四、算法结构的优缺点v优点：枚举算法充分利用了计算机快优点：枚举算法充分利用了计算机快速、高效、准确的优点。速、高效、准确的优点。v枚举算法的局限性：效率不高，它的枚举算法的局限性：效率不高，它的准确性和全面性是以消耗时间为代价准确性和全面性是以消耗时间为代价的。的。五、课后练习五、课后练习1.1.输出输出100200100200之间不能被之间不能被3 3整除的自然整除的自然数，请流程图并写出程序代

17、码。数，请流程图并写出程序代码。练习答案练习答案v Private Sub Command1_Click()Private Sub Command1_Click()v Dim i As IntegerDim i As Integerv Dim sum As IntegerDim sum As Integerv sum = 0sum = 0v For i = 100 To 200For i = 100 To 200v If i Mod 3 0 ThenIf i Mod 3 0 Thenv If sum = 10 ThenIf sum = 10 Thenv sum = 0sum = 0v ElseElsev sum = sum + i sum = sum + iv Label1.Caption = Label1.Caption + Str(i) + Label1.Caption = Label1.Caption + Str(i) + v End If End