第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+) 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*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);,例8-2 百钱买百鸡,鸡翁一值钱五，鸡母一值钱三，鸡雏三值钱一。凡百钱买百鸡，问鸡翁、母、雏各几何？,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;hen+) 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,程序实现：,#include 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=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个穷举变量，不妨就设为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个穷举变量的变化范围就确定了。,选人时，上述的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); ,第四章 串,课堂练习：,问题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次，可以减半，因为我们知道除了3，只要是偶数，就一定不会是素数。所以我们可以将所有大于2的偶数排除，在剩余的奇数中寻找素数。,第四章 串,解决方法如下：,for(i=3;i1000;i+=2) if(IsPrime(i)printf(“%dt”,i);,而对于素数2，单独处理即可。,？请大家再想想，看是否还可以减少穷举量？,通过上面的问题，我们可以看到，如果我们在穷举之前对问题先进性分析，挖掘出问题隐含的条件，排除不可能的条件，就可以减少穷举量了。,第四章 串,例8-4：寻找肇事汽车号码 一辆汽车肇事后逃逸了，目击者向交警描述了这个车号：这是一个4位的十进制完全数，并且这4个数字从左向右一个比一个大。,分析问题：,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) 从题意中我们不难看出如下的关系式： fishi+1=(fishi-1)*4/5，i=0,1,2,3. 也就是说，只要我们知道了fish0,则其它的值我们就可以计算得出了。因此只让fish0作为枚举变量就可以了。,可是从问题中我们知道，fish0的枚举范围并不好确定，因为它是最大的一个数。那么我们看一看其余的变量fish1fish4中，哪一个作为枚举变量会更合适一些呢？ 既然最大的那个数作为枚举变量不好确定枚举范围，我们来看一看让最小的那个数作为枚举变量行不行？ 最小的数是fish4,根据题意，容易知道，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皇后问题也可以用枚举的方法求解。,N皇后问题。,将N个皇后分别放置在一张N*N的棋盘上，要求她们之间互不攻击，即任意两个皇后不同行、不同列、不同一对角线。 比如，当N=4时的一种方法如表所示：,i=1 i=2 i=3 i=4,j=1 j=2 j=3 j=4,问题分析： 我们可以使用穷举法解决N皇后问题。（先看N=4的情形。） 1.穷举变量：i,j,k,l; 2.穷举范围：1=i,j,k,m=4 3.穷举条件： 我们可以将皇后1放置在二维数组的位置a1i,皇后2放置在a2j,皇后3放置在a3k,皇后4放置在a4m.所以不妨假设一种放置的方法为：那么，不同行就已经解决了，接下来要描述的就是不同列和不同对角线： 不同列：（j!=i） int i,j,k,m; int x,y,t=0; for(i=1;i=4;i+) for(j=1;j=4;j+) for(k=1;k=4;k+) for(m=1;m=4;m+) if(j!=i ,8.2 回溯法,N皇后问题： 如果每行放置1个皇后，则行就不会出项冲突的现象。因此解决的主要问题在于如何判断同列、同对角线的问题。 设皇后放置的位置数组为aN。则很容易根据ai与aj的值是否相等来判定皇后i和皇后j是否同列。 而对于对角线的判断，与前面我们曾经讨论的一样，看是否满足等式：j-i=|aj-ai|.如果满足，则同对角线，否则，就不同对角线。 如果已经放置好了i-1个皇后，在放置第i个皇后的时候要与这前i-1个皇后去判断是否同列和同对角线，如果有位置k，使得皇后i与前i-1个皇后既不同行，也不同对角线，则令ai=k即可。但是如果没有位置k满足条件，那么就要回溯了。回到第i-1个皇后，重新放置第i-1个皇后的位置，如果也没有位置放置第i-1个皇后，则继续回溯到前一个皇后。当回溯到第0个皇后的时候，无法回溯，则算法终止。,非递归实现N皇后问题,void NQueen(int n) int i,j,k; int g; /安全标志变量 int a20; /各皇后存放位置数组 int x; /判定是否同列或对角线的变量 int s; /统计个数的变量 i=1;s=0;a1=1; /初始状态 while(1) g=1; /初始时认为安全 for