算法实例(枚举算法).ppt

《算法实例(枚举算法).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章算法实例2.1枚举算法一、作业回顾表扬：张娴雯孙莹、黄豪炳A、B两数交换问题：（借用第三者）方法一：C＝A：A＝B：B＝C（加减法）方法二：A＝A+B：B＝A－B：A＝A－B（非零乘除法）方法三：A＝A+B：B＝A－B：A＝A－B4、称盐问题1、左边放1、1、2、5法码，共9克2、右边放9克食盐3、拿掉法码，将食盐平分，即得5、判断构成三解形开始输入三边a,b,c11a+b<=ca+c<=bb+c<=a输出可构成三角形输出不能构成三角形结束YYYNNN第6题：开始初始变量c1,c2,sum1,sum2为0输入一个数据到变量nn=0?正数s

2、um1=sum1+nc1=c1+1输出正数sum1/c1和负数sum2/c2结束N>0?负数sum2=sum2+nc2=c2+1YNYN想一想：一天早上，数学课代表收好了数学练习本，他的同桌物理课代表收好了物理练习本，但是由于一些意外，两种练习本混在了一起。现在要把混在一起的74本练习本区分开，假如你是数学课代表，你会怎么做？请讲出你的解决方案。C<=74Y列举检验是否继续列举YNC=C+1打开一本作业是数学作业吗放在左边放在右边YNC=1N试一试：请用自己的话试着总结什么是枚举法。这种列举出所有可能的情况并逐一进行检验，根据检验的结果执行相应

3、操作的方法就是枚举法。枚举法的基本思想：是根据提出的问题枚举所有可能状态，并用问题给定的条件检验哪些是符合条件的，哪些是不符合条件的，去掉。能使命题成立，即为其解。其实质是一一列举所有可能，过滤掉不合要求，保留符合要求。枚举法的优点：⑴由于枚举算法一般是现实生活中问题的“直译”，因此比较直观，易于理解；⑵由于枚举算法建立在考察大量状态、甚至是穷举所有状态的基础上，所以算法的正确性比较容易证明。枚举法的缺点：枚举算法的效率取决于枚举状态的数量以及单个状态枚举的代价，因此效率比较低。练一练：学校体育馆买进100个篮球，只有“斯伯丁”和“摩腾”两个牌

4、子，为运输方便将它们混在了一起运来。请你设计一个算法，帮助器材保管员统计共有多少个“斯伯丁”篮球。要求：请将你解决问题的流程图绘制出来。开始J<=100C=0,J=1YNN输出C结束拿出一个篮球是斯伯丁吗C=C+1Y列举检验J=J+1研究范围列举检验是否继续列举YN枚举法的结构特点：逐一列举和检验，用循环结构实现。关键步骤：确定范围、列举、检验。检验就是对某个给定的条件进行判断，根据判断的不同结果执行不同操作，所以检验可用分支结构实现。是数学作业吗放在左边放在右边YN若一个三位数X=100a+10b+c（a、b、c都是个位数），满足a3+b3+

5、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、找到判断正确解的条件，列举。3、逐一检验范围内的所有研究对象。例1：涂抹数字一张单据上有一个5位数的编码，其千位数和百位数已经变得模糊不请。但是知道这个5位数是57

6、或67的倍数。现在要设计一个算法，输出所有满足这些条件的5位数，并统计这样的数的个数。No.147分析:范围：首先，千位数和百位数可以填上00，01，02，……97，98，99；得到10047，10147，……19947。建一个循环变量为j，从0到99的一个循环，每一个可能解n的值为10047+j*100列举：其次，对每一个n判断是否能被57或67整除。若是，输出一组解，解的个数+1；若不是，舍弃检验：nmod57=0ornmod67=0(其他判断方法）算法描述1、计数器c←02、j←03、判断j<100,是转4，否转向94、可能解n←1004

7、7+100*j5、判断n是否57或67的倍数，是转向6；否转向86、计数器c←c+1；7、输出真正的解n8、j←j+1；转向39、输出解的个数C10、结束j<100YN开始c←0j←j+1结束c←c+1输出nn←10047+j*100nmod57=0或nmod67=0NYj←0输出j上虞区小越中学信息技术组编写程序深化思考题：一张单据上有一个5位数的编码，其千位数和十位数已经变得模糊不请。但是知道这个5位数是57或67的倍数。现在要设计一个算法，输出所有满足这些条件的5位数，并统计它们的个数。No.147例2百鸡百钱问题“鸡翁一值钱5，鸡母一值

8、钱3，鸡雏三值钱1”现有100钱，欲买100只鸡，问：鸡翁、鸡母、鸡雏各买几只？分析：设x，y，z分别为买的鸡翁、鸡母、鸡雏的个数则：x+y+z=10