期末复习网协串讲穷举篇

1、枚举法- Dr. Meyerby 阿基里斯何为枚举？枚举是指从可能的集合中一一枚举各个元素，用题目给定的约束条件判定哪些是无用的，哪些是有用的。能使命题成立者，即为问题的解。枚举法的基本思路确定枚举对象、枚举范围和判定条件。一一枚举可能的解，验证是否是问题的解。例题：平方和的解求 的正整数解。问题分析ConceptGameTestExam 这道题显然是一道枚举题，因此我们可设定两个变量X、Y，令它们进行循环，当它们平方和为2000时输出结果即可。枚举范围如何定？ConceptGameTestExam 我们可以算出45*452000，因此我们可以得到X、Y的范围都是145。再开二重循环即可。#i

2、ncludestdio.h#includestdlib.hint main( ) int X , Y ; for( X = 1 ; X 45 ; X + ) /X从1开始循环 for( Y = 1 ; Y 2000 ) break ; system(pause) ; return 0 ;代码实现：例题：整数分解例如：1998 =10000，是一个累加和等于N的连续的自然数段。输出每个累加和等于N的连续的自然数段的第一个数和最后一个数，两个数之间用符号隔开，每段一行，所有行按每行的第一个数从小到大升序排列。如果没有符合条件的自然数段，输出None。问题分析ConceptGameTestExam

3、采用枚举法解决此题的时候，很容易想到的一种方法是：设两个变量（枚举对象），一个是数段的始端left，另一个数是数段的尾端right。进行循环时，先将始端定下来，再让尾端进行移动。当数段之和为输入的整数时，输出当前结果。枚举范围如何定？ConceptGameTestExam 因为我们使用的是int型变量，当N为偶数时，N/2+N/2+1=N+1；N为奇数时，N/2+N/2+ 1=N。left从1开始，最多不能超过N/2。right从left+1开始，最多不能超过N/2+1。#includestdio.h#includestdlib.hint main( ) int N ; int left ,

4、right , flag = 0 ; /left为数段始端的数，right为数段尾端的数，flag为是否有解的标志 scanf(%d,&N) ; for( left = 1 ; left = N / 2 ; left + ) /left从1开始循环 for( right = left + 1 ; right = ( N / 2 + 1 ) ; right + ) /right从left+1开始循环 if( N = ( left + right ) * ( right - left + 1 ) / 2 ) /数列段之和为N flag = 1 ; printf(%d%dn,left,right)

5、; break ; if( flag = 0 ) printf(Nonen) ; system(pause) ; return 0 ;代码实现：问题优化在上面的代码中，电脑进行了很多次不必要的计算，例如：输入10000，当left=2000，right从2001开始循环，循环至2003时，数列段之和为2000 =8006,循环至2004时，数列之和为2000 =10010。此时right再往后的循环已经没必要计算了。因此我们可以在循坏内加入一个判断条件，当数列段之和大于N时，跳出小循环，进行下一次大循环。#includestdio.h#includestdlib.hint main( ) in

6、t N ; int left , right , flag = 0 ; /left为数段始端的数，right为数段尾端的数，flag为是否有解的标志 scanf(%d,&N) ; for( left = 1 ; left = N / 2 ; left + ) /left从1开始循环 for( right = left + 1 ; right = ( N / 2 + 1 ) ; right + ) /right从left+1开始循环 if( N = ( left + right ) * ( right - left + 1 ) / 2 ) /数列段之和为n flag = 1 ; printf(%

7、d%dn,left,right) ; break ; if( N =N的最小整数解。解二元一次方程得： 因为Length为整数解，在此将它放缩为N/2+1，N等于3时两者相等。 left的最小值为1，left后面的数一定大于left，因此left的最大值一定小于等于N/Length,N=3时两者相等，可将它放缩为N/Length。#includestdio.h#includestdlib.hint main( ) int N ; int Length , left , flag = 0 ; /Length为数列段长度，left为数段始端的数，flag为是否有解的标志 scanf(%d,&N) ; for( Length = ( 1 +N / 2 ) ; Length = 2 ; Length - ) /Length从(1+N/2)开始循环 for( left = 1 ; left = N / Length ; left + ) /left从1开始循环 if( N = ( ( 2 * left + Length - 1 ) * Length / 2 ) /数列段之和为n flag = 1 ; printf(%d%dn