第一讲枚举策略可编辑

1、枚举策略一、枚举策略的基本思想枚举法，又称穷举法，指在一个有穷的可能的解的集合屮，一一枚举出集合屮的每一个 元素，用题目给定的检验条件來判断该元素是否符合条件，若满足条件，则该元索即为问题 的一个解；否则，该元素就不是该问题的解。枚举方法也是一种搜索算法，即对问题的所冇可能解的状态集合进行一次扫描或遍历。 在具休的程序实现过程中，可以通过循坏和条件判断语句來完成。枚举法常用于解决“是否存在”或“有多少种可能”等类型的问题。虽然枚举法木质上属于搜索策略，但是它与回溯法冇所不同。因为适用枚举法求解的问 题必须满足两个条件：可预先确定每个状态的元素个数n；状态元bal, a2,，an的可能值为一个连

2、续的值域。 设ail状态元素ai的最小值；aik状态元素ai的最人值(lwiwn),即allwalwalk, a21wa2wa2k, ailwaiwaik, , anlwanwank for al-al 1 to alk do fo a2-a21 to a2k do for aiail to aik do for an*-anl to ank do if状态(al,，a/,，an)满足检验条件 then输出问题的解；枚举法的特点是算法比较简单，在用枚举法设计算法时，重点注意优化，减少运算工作 量。将与问题有关的知识条理化、完备化、系统化，从中找出规律，减少枚举量。例题1:邮局发行一套票而有四种

3、不同值的邮票，如來每封信所贴邮票张数不超过三枚, 存在整数r,使得用不超过三枚的邮票，可以贴出连续的整数1、2、3、r来，找出这 四种面值数，使得值最人。分析：木题知道每封倍邮票数的范围(v = 3),邮票的四利|类型，编程找出能使而值最大邮 票。算法：而值不同的四种邮票，每封信所贴邮票不超过3张；%1 用这四种邮票贴出连续的整数，并且使r值最大；%1 用枚举找出所有符合条件的解；%1 本题用集合的方法统计邮票的而值，提髙判重的速度。程序优化设四种邮票的面值分别为：a, b, c, d,根据题意设：avbvcvd,因此a=1,用循环语句完成搜索。var a,b,c,d: integer; x,

4、x0,x1 ,x2,x3,x4: integer; st1: set of 1 .100;function number(a,b,c,d: integer): integer;var n 1,n2,n3,n4,sum: integer;begi nst1 : = ;for n 1 : = 0 to 3 dofor n2: = 0 to 3-n1 dofor n3: = 0 to 3-n1 -n2 dofor n4: = 0 to 3-n1 -n2-n3 dobeginif n1 + n2+ n3+n4v = 3 thenbeginsum : = n1 * a+ n2* b+ n3* c+ n4

5、* d; st 1: = st 1 + sum;end;end;sum := 1;while sum in st1 do sum: = sum+ 1;nu mber: = sum-1;end;begina:= 1; x0: = 0;for b: = a+ 1 to 3* a+ 1 dofor c: = b+ 1 to 3* b+ 1 dofor d: = c+ 1 to 3*c+ 1 do begin x: = number(a,b,c,d); if x> xo then beginx0: = x; x1 : = a; x2: = b; x3: = c; x4: = d; writeln

6、(x1), ,x2； ',x3,' ',x4, x0=*,x0); end;end;end,程序运行后，其输出结果是：解答结果有11 2 3 4 x0=121 2 3 5 x0= 1313 6 10 x0=231 4 7 8 x0=24例题2:模式识别的“中心”问题实数矩阵rtlm行n列组成（k=ni, n<=100）,现给定实数矩阵，求其中心，若有多个“中 心”，给出任意一个“中心”即可。中心（i, j）是使第i行上边元素（不包括第i行）的总和 与第i行下边元素（不包括第i行）的总和之差的绝对值最小，而且第j列左边元素（不包括 第j列）的总和与第j列右边元索（不

7、包括第j列）的总和之差的绝对值最小。分析：求矩阵的中心，即确定矩阵中心的行和列处标，考虑到矩阵的对性，行坐标和列处标的 求法是类同的。下而是求矩阵中心行坐标的算法。求行坐标采用枚举法，枚举出所有可能的行坐标line,计算岀line行上边元素和与下 边元索和之差的绝对值difference, difference最小的行即为小心所在行。枚举过程可以描述为：min: =+8 ；for line:=l to m dobegin求出line行上、卜元素绝对值z差difference;if min difference the nbeginmin:二difference;保存line作为矩阵中心所在行；

8、end；end；仮lj题3:圆桌骑丄(t0t98)在一个8*8的棋盘上，有一个国王和若干个武士。其中，国王走一字步，骑士走马步。 若国王与骑士相会在同一点上，国王可以选择让骑士背他走。求一个点，使所冇的骑士和国 王相距在这个点上的所走的步数最少。分析：此题可从3个方而考虑：分治、枚举、数学方法。由于无法将这个问题划分为各自独立的小问题来解决，分治显然是不行的。又因武士和 国王位置的不固定性和其走法的差异，推导不出一个数学公式。因此考虑使用枚举，盂要枚 举的三个姿点：1、最后的汇聚点。2、国王与背他的骑士的汇聚点。3、国王与背他的骑士。国王最多只会与一个骑士结合，因为骑丄的最终目标也是最终汇聚点

9、，一口国王与某个 骑士汇合后，即马上可与其结合，剩下的只需耍将所有的骑士汇合就可以了。更没有必耍在 中途中有将国王托付给其他的骑士。这样我们估算-下时间为：0 (8*8*8*8*63) =0 (36*10"4)完全可以承受。另外，我们需要预先将2点之间走马字步的距离计算出来。可以使用floyd或是bfs。 算法流程：disxl, yl, x2, y2- (xl, yl) (x2, y2)之间的距离。for i： =1 to 8 do枚举汇合点for j： =1 to 8 do beginall :二所有骑士到这一点的和；best :=min (best, al 1+国王到汇聚点的步数

10、)for x： =1 to 8 do 枚举武士国干-的相会点for y： =1 to 8 do beginfor kk： =1 to k do 枚举与国王结合的武士if disk night kk. x, knight kk. y, x, y5in then beg inmin:二 disknightkk. x, knihtkk. y, x, y;mink:二kk;end;end；now- all-mink武士走到汇合点的距离+ mink武士走到汇聚点的距离+国王走到汇聚 点的距离+从汇聚点到汇合点的距离；best： =min (best, now)end；二、枚举方法的优化枚举算法的时间复杂

11、度：状态总数*单个状态的耗时主要优化方法：(1) 减少状态总数降低单个状态的考察代价优化过程从以下几个方面考虑：（1）枚举対象的选取（2）枚举方法的确定（3）采用局部枚举或引进其他算法例4：巧妙填数将19这九个数字填入九个空格中。每一横行的三个数字组成一个三位数。如果要使 第二行的三位数是第一行的两倍，第三行的三位数是第一行的三倍，应怎样填数。如图：192384576分析：木题目有9个格子，要求填数，如果不考虑问题给出的条件，共有9! =362880种方案, 在这些方案中符合问题条件的即为解c因此可以采用枚举法。但仔细分析问题，显然第一行的数不会超过400,实际上只耍确定第一行的数就可以根 据

12、条件算出其他两行的数了。这样仅需枚举400次。彳列题5:设有下列的算式：2 0 8 ) 1要求：求出中的数字，并打印出完整的算式。分析：此题找不到很好的方法，于是考虑枚举法。木题中，待填数字的空格共有14个，每个格子中都可填0.9这10个数字。若对14 个格子都进行0.9十个数字逐一枚举，枚举量是1014,不可能在指定的吋间内得出结果。优化方法：减少枚举最，找出适当的元素进行枚举。由数学知识知道，在除法中只要知 道被除数、除数、一商和余数中的任意三部分就町以求得第四部分。木题已知商和余数，只要 知道被除数或除数，整个算式也就确定下来了。而被除数和除数，分别是4位数和2位数。 我们只需枚举除数。

13、枚举量降为102=100,这个吋间复朵度是完全可以承受的。小结枚举方法是最简单的一种解题策略，也是最容易想到的一种方法，利用枚举法解题需耍 枚举出问题的解的所冇状态，英致命的弱点便在于枚举虽太大，从而导致算法效率i 分低下。习题:1、二进制数的分类若将一个正整数转化为二进制数后，1的个数多于0的个数的这类数称为a类数，否则称为b类数。例如：(13) 10= (1101) 2,(10) 10= (1010) 2(24) 10= (11000) 213为a类数;10为b类数；24为b类数;程序要求：求出11000之中(包括1与1000),全部a、b两类数的个数。2、方格填数问题。如图所示形状的八个

14、方格中填入卜8这八个数字，使得相邻的和对角线上的数字之差不 为1,编程求解所有的填法方案和总数。b1b2b3b4b5b6b7b83、语言交流(ianguage.pas)来自不同国家的四位留学生a、b、c、d在一起交谈，他们只会中、英、法、h四种 语言中的2种，情况是：没有人既会li语又会法语；a会口语，但d不会，a和d能互相 交谈，b不会英语，但a和c交谈时却要b当翻译，b、c、d三个想互相交谈，但找不到 共同的语言，只有一种语言3人都会。编程确定a、b、c、d四位留学生各会哪两种语言。提示：将中、法、l1、英四种语言分别定义为chn、frh、jpn、eng,则四种语言 屮取两利|共有(chn

15、,eng) , (chn,frh) , (chn,jpn) , (eng,frh) , (eng,jpn), (frh,jpn)六种组合,分别定义为1、2、3、4、5、6。【输出】输出文件language.out中冇四行，每行为一位留学生会的两种语言。【输出示例】a:chn jpn4、跳远如图7. 1一个小孩想站在某个三角形i的顶端，跳到三角形j的顶端上(i<j)o他总是朝着斜向45°的方向起跳，且初始水平速度v不超过一个给定值畑 在跳跃过程屮，由于受重力作用（忽略空气阻力），小孩将沿着抛物线行进，水平运动方程为x=xo+vt,竖直运动方程为 y=yo+vt-o. 5gt2,运

16、动轨迹是一条上凸的抛物线。取g=10. 0, （x0, yo）是起跳点坐标。请编程求出他从每个位置起跳能到达的最远三角形的编号。注意：跳跃过程中不许碰到 非起点和终点的具他三角形。输入：第行为两个正整数n, vo （3wnw10, 1w voloo）,表示三角形的个数和最大 水平初速度。第行有n个整数h（l whw20）,表示从左到右各个三角形的边长。输出：输岀仅一行，包括叶1个数，表示从三角形1, 2, 3,n-1的顶点出发能到达的最右边的三角形编号。如果从某三角形出发无法达到任何三角形，相应的数为0。5、立方体问题现冇一个凌长为n的立方体，可以分成代个ix ix 1的单位立方体。每个单位立

17、方体 都有一个整数值。个单位立方体的数和不会超过longint范围。现在要求在这个立方体屮 找到一个包含完整单位立方体的长方体，使得该长方体内所有单位立方体的数和最大。输入：nu wnw20）n个nxn的数字矩阵，每个数字矩阵代表一层，每个数字代表一个单位立方体的整 数值，-999w单位立方体的整数值w999输出：长方体的数和。6、围巾裁剪（n0i98）将一个边长为n（n<=100）大的正三角形均匀的分成n*n的小三角形，某些小三角形已 经损坏。求岀2个面积最大的（即包含小三角形个数最多的）2个子正三角形，要求这两个 了正三角形中没有损坏的小三角形。扩展试题1、multiples求min

18、, max有多少个整数是n的整数倍。l<=n<=1000, -106<=min<=max<=1062、workshop给出n个1到10000 z间的整数，以它们为边长（每个整数最多选一次）能组成多少个 不同的三角形？ lvn=50。3 obtainingdigitk给一个最多50位的正整数n,至少加几（非负整数），使得和包含数字k（0、9）4> stairs你需要设计以垂直部分开始和结束的阶梯。每段水平距离均相同且为不小于minwidth 的正整数，每段垂直距离也相同且为不大于maxheight的正整数。给岀总水平距离w和高度求满足条件的阶梯总数。例maxheight=22, minwidth=25, w=h=100,则只有一种方案：每段垂直距离为20,每 段水平距离255 reppity给字符串s,找出至少出现两次（不重叠）的、尽量长的