第二章 算法实例(枚举算法)

1、小越中学信息技术组第二章 算法实例 2.1枚举算法一、作业回顾表扬：张娴雯孙莹、黄豪炳A、B两数交换问题：（借用第三者）方法一：CA：AB：BC（加减法）方法二：AA+B：BAB：AAB（非零乘除法）方法三：AA+B：BAB：AAB4、称盐问题1、左边放1、1、2、5法码，共9克2、右边放9克食盐3、拿掉法码，将食盐平分，即得5、判断构成三解形开始输入三边a,b,c11a+b=ca+c=bb+c0?负数sum2=sum2+nc2=c2+1YNYN想一想： 一天早上，数学课代表收好了数学练习本，他的同桌物理课代表收好了物理练习本，但是由于一些意外，两种练习本混在了一起。现在要把混在一起的74本练

2、习本区分开，假如你是数学课代表，你会怎么做？ 请讲出你的解决方案。C=74Y列举检验是否继续列举YNC=C+1打开一本作业是数学作业吗放在左边放在右边YNC=1N试一试： 请用自己的话试着总结什么是枚举法。这种列举出所有可能的情况并逐一进行检验，根据检验的结果执行相应操作的方法就是枚举法。枚举法的基本思想：是根据提出的问题枚举所有可能状态，并用问题给定的条件检验哪些是符合条件的，哪些是不符合条件的，去掉。能使命题成立，即为其解。其实质是一一列举所有可能，过滤掉不合要求，保留符合要求。枚举法的优点：由于枚举算法一般是现实生活中问题的“直译”，因此比较直观，易于理解；由于枚举算法建立在考察大量状态

3、、甚至是穷举所有状态的基础上，所以算法的正确性比较容易证明。枚举法的缺点： 枚举算法的效率取决于枚举状态的数量以及单个状态枚举的代价，因此效率比较低。练一练： 学校体育馆买进100个篮球，只有“斯伯丁”和“摩腾”两个牌子，为运输方便将它们混在了一起运来。请你设计一个算法，帮助器材保管员统计共有多少个“斯伯丁”篮球。 要求： 请将你解决问题的流程图绘制出来。 开始J=100C=0,J=1YNN输出C结束拿出一个篮球是斯伯丁吗C=C+1Y列举检验J=J+1研究范围列举检验是否继续列举YN枚举法的结构特点：逐一列举和检验，用逐一列举和检验，用循环结构实现循环结构实现。关键步骤：确定范围、列举、检验。

4、 检验就是对某个给定的条件进行判断，根据判断的不同结果执行不同操作，所以检验可用分支结构实现。是数学作业吗放在左边放在右边YN 若一个三位数X=100a+10b+c（a、b、c都是个位数），满足a3+b3+c3=X,则X称为水仙花数，请设计算法，找出所有的水仙花数。 列举检验研究范围100 = X = 999分别得到三位数的百位a、十位b、个位ca3+b3+c3=X开始结束X=100X=999分别得到三位数的百位a、十位b、个位ca3+b3+c3=X输出XX=X+1a=int(X/100)c=X % 10b=(X-100*a-c)/10YYNN枚举法的注意点：1、选定合适的研究对象的范围。2、

5、找到判断正确解的条件，列举。3、逐一检验范围内的所有研究对象。例1：涂抹数字一张单据上有一个一张单据上有一个5 5位数的编码，其千位数和百位数已经变得位数的编码，其千位数和百位数已经变得模糊不请。但是知道这个模糊不请。但是知道这个5 5位数是位数是5757或或6767的倍数。现在要设计的倍数。现在要设计一个算法，输出所有满足这些条件的一个算法，输出所有满足这些条件的5 5位数，并统计这样的数位数，并统计这样的数的个数。的个数。No.No.1 47分析分析:范范围围：首先首先，千位，千位数数和百位和百位数数 可以可以填填上上0000，0101，0202，9797，9898，9999；得到；得到1

6、004710047，1014710147，1994719947。建一。建一个个循循环变环变量量为为j j，从从0 0到到9999的一的一个个循循环环，每一，每一个个可能解可能解n n的的值为值为10047+j10047+j* *100100列列举举：其次其次，对对每一每一个个n n判判断断是否能被是否能被5757或或6767整除。若是，整除。若是，输输出一出一组组解，解的解，解的个数个数+1+1；若不是，；若不是，舍弃舍弃检验检验：n mod 57=0 or n mod 67=0 n mod 57=0 or n mod 67=0 ( (其他判其他判断断方法）方法）算法描述算法描述1、计数器c0

7、02 2、j0j03 3、判断、判断j100,j100,是转是转4 4，否转向，否转向 9 94 4、可能解、可能解 n10047+100n10047+100* *j 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、结束、结束j100YN开始开始c 0 j j+1结束结束c c+1输出输出 nn 10047+j*100 n mod 57=0或或n mod

8、67=0NYj 0 输出输出 j上虞区小越中学信息技术组编写程序深化思考题：一张单据上有一个5位数的编码，其千位数和十位数已经变得模糊不请。但是知道这个5位数是57或67的倍数。现在要设计一个算法，输出所有满足这些条件的5位数，并统计它们的个数。No.No.1 4 7范范围围：鸡翁列列举举：x=20YN开始开始x 0 x x+1结束结束y=33Ny y+1y 0 Yxyz0010001990298 0336720 3347z 100-x-y输出输出x,y,z5*x+3*y+z/3=100NY范范围围： 列列举举： 检验检验：x=74YN开始开始x 1 x x+1y=200Ny y+1y 1 结

9、束结束Yx*8+y*3=600?输出x,y值假如要求：1、大盒是偶数的呢？2、大盒数量要超过小盒的数量深化思考题思考题： 如果你是体育委员，假设为了教学的需要，要对总共60个篮球进行分组。要求如下： 1、A类组每组有4个球，B类组每组有6个球； 2、A类组和B类组的数量都不能为0。请设计一个算法，输出所有可能的分组方案。 开始A=1A=14B=1B=10A*4+B*6=50输出A,BB=B+1A=A+1结束NYYNYNP251、2、3题作业：分析：分析： 千位数和十位数上的数字只能是0-9中的一个。104071041710427104371044710457104671047710487104

10、97ij19407194171942719437194471945719467194771948719497iji 从从0变化到变化到9；j从从0变化变化到到9。因此，需要构造一。因此，需要构造一个双重循环。个双重循环。可能的解可能的解n 10407+1000*i+10*j双重循环的构造双重循环的构造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思考：思考：右面的流程右面的流程图有没有问图有没有问题题i=9YN开始开始i 0 i i+1结束结束j=9Nj j+1j 0 Y算法描述j+1；转向 410、i i+1；转向 2i=9YN开始开始i 0 i i+1j=9Nj j+