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

第二章算法实例,2.1枚举算法,一、作业回顾,4、称盐问题,1、左边放1、1、2、5法码，共9克2、右边放9克食盐3、拿掉法码，将食盐平分，即得,5、判断构成三解形,开始,输入三边a,b,c,1,1,a+b=c,a+c=b,b+c0?,负数sum2=sum2+n,c2=c2+1,Y,N,Y,N,想一想：,一天早上，数学课代表收好了数学练习本，他的同桌物理课代表收好了物理练习本，但是由于一些意外，两种练习本混在了一起。现在要把混在一起的74本练习本区分开，假如你是数学课代表，你会怎么做？请讲出你的解决方案。,列举,检验,C=C+1,C=1,试一试：,请用自己的话试着总结什么是枚举法。,这种列举出所有可能的情况并逐一进行检验，根据检验的结果执行相应操作的方法就是枚举法。,枚举法的基本思想：是根据提出的问题枚举所有可能状态，并用问题给定的条件检验哪些是符合条件的，哪些是不符合条件的，去掉。能使命题成立，即为其解。其实质是一一列举所有可能，过滤掉不合要求，保留符合要求。枚举法的优点：由于枚举算法一般是现实生活中问题的“直译”，因此比较直观，易于理解；由于枚举算法建立在考察大量状态、甚至是穷举所有状态的基础上，所以算法的正确性比较容易证明。枚举法的缺点：枚举算法的效率取决于枚举状态的数量以及单个状态枚举的代价，因此效率比较低。,练一练：,学校体育馆买进100个篮球，只有“斯伯丁”和“摩腾”两个牌子，为运输方便将它们混在了一起运来。请你设计一个算法，帮助器材保管员统计共有多少个“斯伯丁”篮球。要求：请将你解决问题的流程图绘制出来。,开始,J=100,C=0,J=1,Y,N,N,输出C,结束,拿出一个篮球,列举,检验,J=J+1,研究范围,枚举法的结构特点：逐一列举和检验，用循环结构实现。关键步骤：确定范围、列举、检验。检验就是对某个给定的条件进行判断，根据判断的不同结果执行不同操作，所以检验可用分支结构实现。,若一个三位数X=100a+10b+c（a、b、c都是个位数），满足a3+b3+c3=X,则X称为水仙花数，请设计算法，找出所有的水仙花数。,列举,检验,研究范围,100=X=999,分别得到三位数的百位a、十位b、个位c,a3+b3+c3=X,开始,结束,X=100,X=999,分别得到三位数的百位a、十位b、个位c,a3+b3+c3=X,输出X,X=X+1,a=int(X/100)c=X%10b=(X-100*a-c)/10,Y,Y,N,N,枚举法的注意点：1、选定合适的研究对象的范围。2、找到判断正确解的条件，列举。3、逐一检验范围内的所有研究对象。,例1：涂抹数字,一张单据上有一个5位数的编码，其千位数和百位数已经变得模糊不请。但是知道这个5位数是57或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、计数器c02、j03、判断j100,是转4，否转向94、可能解n10047+100*j5、判断n是否57或67的倍数，是转向6；否转向86、计数器cc+1；7、输出真正的解n8、jj+1；转向39、输出解的个数C10、结束,.,编写程序,深化思考题：一张单据上有一个5位数的编码，其千位数和十位数已经变得模糊不请。但是知道这个5位数是57或67的倍数。现在要设计一个算法，输出所有满足这些条件的5位数，并统计它们的个数。,No.147,例2百鸡百钱问题,“鸡翁一值钱5，鸡母一值钱3，鸡雏三值钱1”现有100钱，欲买100只鸡，问：鸡翁、鸡母、鸡雏各买几只？,分析：设x，y，z分别为买的鸡翁、鸡母、鸡雏的个数则：x+y+z=1005*x+3*y+z/3=100可能的解X:0-20Y:0-33Z:100-x-y,范围：鸡翁X:0-20，鸡母Y:0-33鸡雏Z:100-x-y,列举：建立一个双重循环,可能的解如下：,检验可能的解是否真正的解,判断：5*x+3*y+z/3=100若是，x,y,z就是一个真正的解,z100-x-y,输出x,y,z,5*x+3*y+z/3=100,N,Y,包装问题：,600个变形金刚，包装的规格为：大盒（8个）、小盒（3个）；每种规格的盒都不能为空。请设计一个算法，输出所有可能的包装方案。,分析：设大小盒的个数分别为x,y则：8*x+3*y=600X：1-74Y：1-200,范围：X：1-74Y：1-200问X为什么到74，Y到200,算法提示,列举：构造一个双重循环，循环变量分别为x（大盒数量）和y（小盒数量）。检验：判断：8*x+3*y=600是否成立;若是，则x,y就是一个包装方案。,流程图,x*8+y*3=600?,输出x,y值,假如要求：1、大盒是偶数的呢？2、大盒数量要超过小盒的数量,600个变形金刚，包装的规格为：大盒（8个）、中盒（5个）、小盒（2个）；每种规格的盒都不能为空。请设计一个算法，输出所有可能的包装方案。,深化思考题,思考题：,如果你是体育委员，假设为了教学的需要，要对总共60个篮球进行分组。要求如下：1、A类组每组有4个球，B类组每组有6个球；2、A类组和B类组的数量都不能为0。请设计一个算法，输出所有可能的分组方案。,P251、2、3题,作业：,分析：,千位数和十位数上的数字只能是0-9中的一个。,i,j,i,j,i从0变化到9；j从0变化到9。因此，需要构造一个双重循环。可能的解n10407+1000*i+10*j,双重循环的构造,1、i02、判断i=9；是转向3，否则转向73、j04、判断j=9；是转向5，否则转向65、jj+1；转向46、ii+1；转向27、结束,思考：右面的流程图有没有问题,算法描述,1、c0；i02、判断i=9；是转向3，否则转向113、j04、判断j=9；是转向5，否则转向105、n10407+1000*i+10*j6、判断n是否57或67的倍数，是转向7；否转向97、计数器cc+1；8、输出一个真正的解n9、jj+1；转向410、ii+1；转向211、输出解的个数c12、结束,包装问题：600个变形金刚，包装的规格为：大盒（8个）、中盒（5个）、小盒（2个）；每种规格的盒都不能为空。请设计一个算法，输出所有可能的包装方案。,分析：设大中小盒的个数分别为x,y,z则：8*x+5*y+2*