第8章综合应用.ppt
《第8章综合应用.ppt》由会员分享,可在线阅读,更多相关《第8章综合应用.ppt(51页珍藏版)》请在三一文库上搜索。
1、第8章 综合应用,8.1 穷举法:打开问题的缺口,基本思想:,将所有可能的状态例举出来,然后逐一检验是否满足条件,从而判断哪些是需要的解,哪些不是。,问题1:求解11000之间所有的素数。,8.1.1 穷举法的基本思想,问题2:求解满足在11000之间的两个数之和等于1234的所有解。,问题3:求解满足在11000之间的三个数,它们是直角三角形的三条边的所有解。,第四章 串,对从2开始一直到1000的所有数去判断是否是素数,如果是则输出。,for(i=2;i1000;i+) if(IsPrime(i) printf(“%dt”,i);,问题2的解决方法:,for(a=1;a=1000;a+)
2、for(b=1;b=1000;b+) if(a+b=1234)printf(“a=%d,b=%dn”,a,b),问题1的解决方法:,两个数不妨设为a和b。该问题的就是求解满足1a 1000, 1 b 1000 而且a+b=1234的所有的a和b。,第四章 串,问题3的解答:,若设这三个数为a,b,c,那么问题的解满足: (1) 1a1000, 1b1000, 1c1000; (2) a2 = b2 + c2 或者 b2 =a2 +c2或者 c2 =a2 + b2,for(a=1;a=1000;a+) for(b=1;b=1000;b+) for(c=1;c=1000;c+) if(a*a=b*
3、b+c*c)|(b*b=a*a+c*c) |(c*c=a*a+b*b) printf(“a,b,c分别是%d,%d,%dn”,a,b,c);,第四章 串,解决问题的方式一般为:,for(a1=a1min; a1a1max;a1+) for(a2=a2min; a2a2max;a2+) for(an=anmin; ananmax ; an+) if(状态(a1,a2,an)满足检验条件) 输出问题的解,用穷举法的必备条件:,可以预先确定每种状态下的元素个数,2.每种状态下元素a1,ai,an的可能值是一个连续的值域。称ai为穷举变量,ai amin, amax。,例8-2 百钱买百鸡,鸡翁一值钱
4、五,鸡母一值钱三,鸡雏三值钱一。凡百钱买百鸡,问鸡翁、母、雏各几何?,1:确定穷举变量以及穷举范围,2:满足的条件,穷举变量:鸡翁(cock),鸡母(hen),鸡雏(chick),第四章 串,问题分析:,百钱:5*cock+3*hen+chick/3=100,穷举范围:,cock0,100/5,hen0,100/3,chick0, chick%3=0,99,百鸡:cock+hen+chick=100,程序实现:,#include void main( ) int cock , hen , chick ; for(cock=0;cock=20;cock+) for(hen=0;hen=33;he
5、n+) for(chick=0;chick=99;chich+=3) if(cock+hen+chick=100) ,第四章 串,上述的程序采用的是三重循环实现穷举,事实上,我们使用二重循环就可以完成任务了。因为这三个循环变量之间不是独立的,而是有关系的,我们可以通过它们之间的关系重新确定穷举变量的范围。,cock:0,1,20;,第四章 串,hen:0,1,(100-5*cock)/3;,chick:100-cock-hen,1.穷举变量的穷举范围:,2.满足的条件:,百钱:5*cock+3*hen+chick/3=100,小鸡数必须是3的倍数:chick%3=0,程序实现:,#includ
6、e void main() int cock,hen,chick; int maxhen; for(cock=0;cock=20;cock+) maxhen=(100-5*cock)/3; for(hen=0;hen=maxhen;hen+) chick=100-cock-hen; if(chick%3=0) ,第四章 串,第四章 串,百钱买百鸡的问题中利用各穷举变量之间的关系提高了效率,由三重循环变为二重循环。这个例子说明,如果在穷举前预先对数据做一下分析,就可以提高穷举的效率。 通过这种方法,我们可以将问题2转化为一重循环解决,问题3也可以转化为二重循环来解决了。,问题2求解:,for(a
7、=1;a=1000;a+) b=1234-a; if(b=1000) printf (“a=%d,b=%dn”,a,b) ,对于某些问题,穷举变量的取值范围并没有确切的给出,此时要能够将问题答案范围内的状态与自然数建立一一对应,从而确定穷举变量的取值范围。,例8-3 选人方案。班上要在A,B,C,D,E,F 6名同学中选派若干人去参加比赛,选择条件如下: E和F两人至少去一个; C和D两人去一个; D和E要么都去,要么都不去; A、B、F三人中要去两个; 若C不去,则B也不去; C和F不能一起去。 请仔细分析上述条件,找出参加比赛的人选,对于该问题,我们很快就可以确定有6个穷举变量,不妨就设为
8、a,b,c,d,e,f,而每个变量的变化范围如何确定呢?,问题中所说的6个条件(分别用c1,c2,c3,c4,c5,c6表示)表达如下: E和F两人至少去一个:c1=(e+f=1) C和D两人去一个: c2=(c+d=1) D和E要么都去,要么都不去:c3=(d+e=0|d+e=2) (或者c3=(d+e!=1) A、B、F三人中要去两个:c4=(a+b+f=2) 若C不去,则B也不去:c5=(c+b=0|c=1) C和F不能一起去:c6=(c+f=1),6名同学中的每一个同学都只会有“去”或“不去”两种选择,我们分别用自然数“ 1 ”和“ 0 ”来表示“去”和“不去”的状态,这样6个穷举变量
9、的变化范围就确定了。,选人时,上述的6个条件都要满足,即满足c1+c2+c3+c4+c5+c6=6的所有的a,b,c,d,e,f都是该问题的解。,程序实现:,#include void main() int a,b,c,d,e,f; int c1,c2,c3,c4,c5,c6; for(a=0;a=1; c2=c+d=1; c3=(d+e=0)|(d+e=2); c4=a+b+f=2; c5=(c+b=0)|(c=1); c6=c+f=1; if(c1+c2+c3+c4+c5+c6=6) printf(“a=%d,b=%d,c=%d,d=%d,e=%d,f=%dn“,a,b,c,d,e,f);
10、 ,第四章 串,课堂练习:,问题1:输出从1,2,3,4,5这5个数中选取3个数的所有无复排列。 问题2:输出从1,2,3,4,5这5个数中选取3个数的所有无复组合。 问题3:输出从1,2,3,4,5,6这6个数中选取4个数的所有无复排列,要求最后一位(个位数)是偶数。,第四章 串,由于穷举法是要将所有的解的状态一一例举,因此,如果解空间较大,穷举量就太大,程序运行的就会太慢。所以要尽可能的减少穷举状态。 如何减少穷举量呢?,8.1.2 减少穷举量,提高穷举效率,问题1:求解11000之间所有的素数。,前面我们已经利用穷举法将问题1解决了,实际上,经过分析我们会发现穷举的次数无需1000次,可
11、以减半,因为我们知道除了3,只要是偶数,就一定不会是素数。所以我们可以将所有大于2的偶数排除,在剩余的奇数中寻找素数。,第四章 串,解决方法如下:,for(i=3;i1000;i+=2) if(IsPrime(i)printf(“%dt”,i);,而对于素数2,单独处理即可。,?请大家再想想,看是否还可以减少穷举量?,通过上面的问题,我们可以看到,如果我们在穷举之前对问题先进性分析,挖掘出问题隐含的条件,排除不可能的条件,就可以减少穷举量了。,第四章 串,例8-4:寻找肇事汽车号码 一辆汽车肇事后逃逸了,目击者向交警描述了这个车号:这是一个4位的十进制完全数,并且这4个数字从左向右一个比一个大
12、。,分析问题:,1.确定穷举变量和穷举范围: 穷举变量只有1个,不妨设为n。而4位十进制的范围从1000到9999,但是由于题目中告知这个数是一个完全数,既是说n=i2。因为1000n9999,所以32i99。所以我们把对n的穷举转化为对i的穷举,此时,穷举量大大减少了,有原来的8999个减少到67个。,第四章 串,分析问题:,2.满足条件:四个数字从左到右一个比一个大。 如果找到n=i2,满足1000n9999,对组成n的4个数字分别用num0,num1,num2,num3表示,那么上述的条件就可表示为: (num0num1)&(num1num2)&(num2num3),8.1.3 局部穷举
13、,例8-5:五人合伙夜间捕鱼 问题分析: 设A、B、C、D、E这五个人分得的鱼分别是fish0fish4; 从题意中我们不难看出如下的关系式: fishi+1=(fishi-1)*4/5,i=0,1,2,3. 也就是说,只要我们知道了fish0,则其它的值我们就可以计算得出了。因此只让fish0作为枚举变量就可以了。,可是从问题中我们知道,fish0的枚举范围并不好确定,因为它是最大的一个数。那么我们看一看其余的变量fish1fish4中,哪一个作为枚举变量会更合适一些呢? 既然最大的那个数作为枚举变量不好确定枚举范围,我们来看一看让最小的那个数作为枚举变量行不行? 最小的数是fish4,根据
14、题意,容易知道,fish4=6. 既然如此,我们可以处理各人所得鱼数的关系如下: fishi=fishi+1*5/4+1 i=3,2,1,0,因此我们有: int fish5=0,0,0,0,6; do for(i=3;i=0;i-) if(fishi+1%4!=0)break; else fishi=fishi+1*5/4+1; if(i=0) fish4=fish4+5; while(i=0);,局部穷举的例子还可以回顾一下第三张习题3.15.我们可以只对张三做穷举即可。 类似的,习题3.16、3.17、3.18、3.19、3.20等都是可以用枚举解决的问题。 此外,著名的N皇后问题也可以
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 综合 应用
链接地址:https://www.31doc.com/p-2578810.html