《穷举法》由会员分享，可在线阅读，更多相关《穷举法（13页珍藏版）》请在金锄头文库上搜索。
1、穷举法,在程序设计中，我们经常需要根据给定的一组条件求满足条件的解。如果问题的解可以用公式，或者按一定的规则、规律求出，那么就可以很容易地写出相应的程序。但是对于许多问题，我们都难以找到明确的公式和计算规则，在这种情况下，我们可以利用计算机高速运算的特点，用穷举法来解。,穷举法的基本思想: 穷举也叫枚举，它的基本思想是先依据题目的部分条件来确定答案的大致范围（可能解），然后在此范围内用其余的条件对所有可能解进行一一验证，删去那些不符合条件的解，剩下符合条件的解就是整个问题的解,例1找完全数 古希腊人认为因子的和等于它本身的数是一个完全数（自身因子除外）。例如28的因子是1、2、4、7、14，且
2、1+2+4+7+14=28，则28是一个完全数。编写一个程序求210000内的所有完全数。,分析： 1.本题只需一个枚举变量a即可，它的范围是210000； 2.验证完全数的条件是：所有因子的和等于该数据本身； 3.找出所有因子、并求出因子和是关键的一步，可采用循环完成分解因子和求因子和。,main() int a,b,s; for( a=2;a=10000;a+) s=0; for(b=1; b=a/2;b+) if (a % b=0) s=s+b; if (a=s) printf(“%d”, a); 运行结果： 6 28 496 8128,/*枚举a，范围210000*/,/*分解因子并求
3、出因子和*/,/*验证，如果数a满足条件，则输出*/,从上例可知，穷举法是一种比较笨拙的算法，因为它需要列举出许多个可能解来一一验证，程序往往需要运行很长时间，效率较低。但是，穷举法也有自己的优点，它思路简单，容易编写程序，只要时间足够，穷举法能够很容易地求出问题的全部正确解。 针对穷举法效率较低的缺点，在设计穷举算法时，我们必须注意以下二点： 考虑枚举变量一定要慎重，枚举变量应尽量少，尽量通过计算而不是枚举来确定变量。 枚举前应尽可能多地将不符合条件的情况预先排除，以缩小枚举范围。,例2除法运算（NOIP1995初中组复赛第一题） 设有下列的除法算式： 请根据上述算式中的信息求出被除数和除数
4、。,分析：设除数为x，被除数为y，由算式信息可知：10=100。因此，我们可选择枚举除数，而被除数则可按公式y=809*x+1计算得出。,main() int x,y; for (x=10;x9999) break; if (_) printf (“%d,%d”,y,x); 运行结果： 9709 12,/*枚举除数x，范围是1099*/,/*计算出被除数y*/,/*验证，如果满足要求，则输出*/,y=1000 & 8*x=100,main() int k,i,j,x; k=0; for(_) x=_; y=_; j=x*10+y; if (_) k=k+1; printf(“%4d”,i);
5、if (_) printf(“n”); ,练习：1求出所有满足下列条件的二位数：将此二位数的个位数字与十位数字进行交换，可得到一个新的二位数，要求新数与原数之和小于100。 程序要求：每行输出6个满足条件的数。 算法提要：分解每一个二位数，然后重新组成一个新数，当满足条件时，用计数器来统计个数。,i=10;i=99;i+,i % 10,i /10,i +j 100,k %6=0,例5方格填数 如下图所示的八个格子中填入1至8八个数字，使得相邻的和对角线的数字之差不为1。编程找出所有放法。,分析：由题意可知，放入b3，b6这两个格子中的数，必须和六个数不连续，仅可以和一个数是连续的，这样的数只能
6、是1和8。因此，b1，b3，b6，b8这四个格子中数的放法可以先确定下来：2，8，1，7或7，1，8，2。接着，我们只需枚举b2、b4、b5三个变量，范围都是3至6，而b7可通过计算来得到。,int link6,2=1,2,1,4,2,5,4,7,5,8,7,8; int b9; main() b1=2;b3=8;b6=1;b8=7; try; b1=7;b2=1;b6=8;b8=2; try; ,void print; printf(“%4dn”,b1); printf(“%2d,%2d%2dn”,b2,b3,b4); printf(“%2d%2d%2dn”,b5,b6,b7); print
7、f(“%4dn”,b8); ,void try for (b2=2;b2=6;b+) for(b4=3;b4=6;b+) if (b2!=b4) for(b5=3;b5=6;b+;) if (b5!=b2 ,int choose int i,x; x=0; for (i=0;i=5;i+) if (abs(blinki,0-blinki,1)=1) return(x); return(1); ,link6,2=1,2,1,4,2,5,4,7,5,8,7,8;,练习：2将n个整数分成k组(kn,要求每组不能为空),显然这k个部分均可得到一个各自的和s1,s2,sk,定义整数P为: P=(S1-S
8、2)2+(S1一S3)2+(S1-Sk)2+(s2-s3)2+(Sk-1-Sk)2 问题求解:求出一种分法,使P为最小(若有多种方案仅记一种),程序说明: 数组: a1,a2,.an存放原数 s1,s2,.,sk存放每个部分的和 b1,b2,.,bn穷举用临时空间 d1,d2,.,dn存放最佳方案,main() int i,j,n,k,sum,a101,b100,s31; scanf(“%d,%d”,si =0;,sbi=sbi+ai;,j=i+1;j=k;j+,if (_) cmin=sum; for (i=1;i=n;i+) di=bi; j=n; while( _ ) j=j-1; bj=bj+1; for(i=j+1;j=n;j+) _; printf(“%40d”,cmin); for(i=1;i=n;i+) printf(“%d”,di); ,cminsum,bj=k,bi=1;,
