[数学]枚举法.ppt

基本算法——枚举法 技术教研组 谷方明 1 示例 求满足表达式A+B=C的所有整数解，其中A，B，C为1~3之间的整数。 例题分析 本题非常简单，即枚举变量A,B,C的所有可能取值情况，对每种取值情况判断是否符合表达式即可。 算法如下 for(int A=1;A=3;A++) for(int B=1;B=3;B++) for(int B=1;B=3;B++) if(A+B==C) 输出A,B,C; 枚举法的定义 所谓枚举法，指的是从可能的解的集合中一一枚举各元素，用题目给定的检验条件判定哪些是无用的，哪些是有用的。能使命题成立的，即为解。 示例中的解变量有3个：A，B，C。其中 解变量A的可能取值范围A∈{1， … ，3} 解变量B的可能取值范围B∈{1， … ，3} 解变量C的可能取值范围C∈{1， … ，3} 从而问题的可能解有3*3*3=27个，可能解集： （A，B，C）∈{（1，1，1），（1，1，2），（1，1，3），…，（3，3，1），（3，3，2），（3，3，3）} 在上述可能解集中，满足题目给定的检验条件（A+B==C）的解元素，即为问题的解。 枚举法的适用条件 对于可能确定解的值域又一时找不到其他更好的算法时可以考虑枚举法。 用枚举法求解的问题须满足两个条件 能确定解变量（枚举变量）的个数 n ； 每个解变量Ai（1 = i = n）的可能值能确定范围且能连续取得。 枚举法算法框架 设解变量的个数是n,Ai1—解变量Ai的最小值；Aik—解变量Ai的最大值(1≤i≤n)，即A11≤A1≤A1k，Ai1≤Ai≤Aik，……，An1≤An≤Ank 算法框架如下（伪代码）： for A1←A11 to A1k do for A2←A21 to A2k do …………………… for Ai←Ai1 to Aik do …………………… for An←An1 to Ank do if 状态(A1，…，Ai，…，An)满足检验条件 then 输出问题的解； 枚举算法的特点及优化 枚举法的特点是算法简单，但有时运算量大。 优化枚举算法（考察重点） 枚举算法的时间复杂度=状态总数*考察单个状态的耗时 排除明显不属于解集的元素 减少状态总数（即减少枚举变量和枚举变量的值域） 降低单个状态的考察代价 示例算法显然可以修改如下: for(int A=1;A=3;A++) for(int B=1;B=3;B++) { C=A+B; if(C=1)(C=3) 输出A,B,C; } 通过变量的依赖关系减少了解变量的个数(局部枚举)，优化了枚举算法，n^3 - n^2。 枚举法解题的一般思路 对命题建立正确的数学模型； 根据命题确定的数学模型中各变量的变化范围（即可能解集）； 利用循环语句、条件判断语句逐步求解或证明； 每一步都可以考虑优化 2 例1 巧妙填数 将1～9这九个数字填入九个空格中。每一横行的三个数字组成一个三位数。如果要使第二行的三位数是第一行的两倍, 第三行的三位数是第一行的三倍, 应怎样填数。（一共4组解，一组如下图) 本题目有9个格子，要求填数，如果不考虑问题给出的条件，共有9！=362880种方案，在这些方案中符合问题条件的即为解。因此可以采用枚举法。 但仔细分析问题，显然第一行的数不会超过400，实际上只要确定第一行的数就可以根据条件算出其他两行的数了。这样仅需枚举400次。（优化：解变量的依赖关系，也叫局部枚举） 例2 谁是第几名 在某次数学竞赛中, A、B、C、D、E五名学生被取为前五名。请据下列说法判断出他们的具体名次, 即谁是第几名？ 条件1: 你如果认为A, B, C, D, E 就是这些人的第一至第五名的名次排列, 便大错。因为: 没猜对任何一个优胜者的名次。 也没猜对任何一对名次相邻的学生。 条件2: 你如果按D, A , E , C , B 来排列五人名次的话, 其结果是: 说对了其中两个人的名次。 还猜中了两对名次相邻的学生的名次顺序。 分析：本题是一个逻辑判断题，一般的逻辑判断题或推理题都采用枚举法进行解决。5个人的名次分别可以有5！=120种排列可能，因为120比较小，因此我们对每种情况进行枚举，然后根据条件判断哪些符合问题的要求。 根据已知条件，A1,B2,C3,D4,E5,因此排除了一种可能性，只有4！=24种情况了。（优化：减少了解变量的取值范围） 例3 古纸残篇 在一位数学家