《数学]枚举法》PPT课件

《《数学]枚举法》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、基本算法——枚举法技术教研组谷方明1示例求满足表达式A+B=C的所有整数解，其中A，B，C为1~3之间的整数。东北师大附中例题分析本题非常简单，即枚举变量A,B,C的所有可能取值情况，对每种取值情况判断是否符合表达式即可。算法如下for(intA=1;A<=3;A++)for(intB=1;B<=3;B++)for(intB=1;B<=3;B++)if(A+B==C)输出A,B,C;东北师大附中枚举法的定义所谓枚举法，指的是从可能的解的集合中一一枚举各元素，用题目给定的检验条件判定哪些是无用的，哪些是有用的。能使命题成立的

2、，即为解。东北师大附中示例中的解变量有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）的解元素，即为问题的解。东北师大附中枚举法的适用条件对于可能确定解的值域又一时找不到其他更好的算法时可以考虑枚举法。用枚举法求

3、解的问题须满足两个条件能确定解变量（枚举变量）的个数n；每个解变量Ai（1<=i<=n）的可能值能确定范围且能连续取得。东北师大附中枚举法算法框架设解变量的个数是n,Ai1—解变量Ai的最小值；Aik—解变量Ai的最大值(1≤i≤n)，即A11≤A1≤A1k，Ai1≤Ai≤Aik，……，An1≤An≤Ank算法框架如下（伪代码）：forA1←A11toA1kdoforA2←A21toA2kdo……………………forAi←Ai1toAikdo……………………forAn←An1toAnkdoif状态(A1，…，Ai，…，An)

4、满足检验条件then输出问题的解；东北师大附中枚举算法的特点及优化枚举法的特点是算法简单，但有时运算量大。优化枚举算法（考察重点）枚举算法的时间复杂度=状态总数*考察单个状态的耗时排除明显不属于解集的元素减少状态总数（即减少枚举变量和枚举变量的值域）降低单个状态的考察代价东北师大附中示例算法显然可以修改如下:for(intA=1;A<=3;A++)for(intB=1;B<=3;B++){C=A+B;if(C>=1)&&(C<=3)输出A,B,C;}通过变量的依赖关系减少了解变量的个数(局部枚举)，优化了枚举算法，n^3-

5、>n^2。东北师大附中枚举法解题的一般思路对命题建立正确的数学模型；根据命题确定的数学模型中各变量的变化范围（即可能解集）；利用循环语句、条件判断语句逐步求解或证明；每一步都可以考虑优化东北师大附中2例1巧妙填数将1～9这九个数字填入九个空格中。每一横行的三个数字组成一个三位数。如果要使第二行的三位数是第一行的两倍,第三行的三位数是第一行的三倍,应怎样填数。（一共4组解，一组如下图)192384576东北师大附中本题目有9个格子，要求填数，如果不考虑问题给出的条件，共有9！=362880种方案，在这些方案中符合问题条件的即

6、为解。因此可以采用枚举法。但仔细分析问题，显然第一行的数不会超过400，实际上只要确定第一行的数就可以根据条件算出其他两行的数了。这样仅需枚举400次。（优化：解变量的依赖关系，也叫局部枚举）东北师大附中例2谁是第几名在某次数学竞赛中,A、B、C、D、E五名学生被取为前五名。请据下列说法判断出他们的具体名次,即谁是第几名？条件1:你如果认为A,B,C,D,E就是这些人的第一至第五名的名次排列,便大错。因为:没猜对任何一个优胜者的名次。也没猜对任何一对名次相邻的学生。条件2:你如果按D,A,E,C,B来排列五人名次的话,其结

7、果是:说对了其中两个人的名次。还猜中了两对名次相邻的学生的名次顺序。东北师大附中分析：本题是一个逻辑判断题，一般的逻辑判断题或推理题都采用枚举法进行解决。5个人的名次分别可以有5！=120种排列可能，因为120比较小，因此我们对每种情况进行枚举，然后根据条件判断哪些符合问题的要求。根据已知条件，A<>1,B<>2,C<>3,D<>4,E<>5,因此排除了一种可能性，只有4！=24种情况了。（优化：减少了解变量的取值范围）东北师大附中例3古纸残篇在一位数学家的藏书中夹有一张古旧的纸片。纸片上的字早已模糊不清了,只留下曾经写过

8、字的痕迹,依稀还可以看出它是一个乘法算式,如图7所示。这个算式上原来的数字是什么呢？夹着这张纸片的书页上,“素数”两个字被醒目的划了出来。难道说,这个算式与素数有什么关系吗？有人对此作了深入的研究,果然发现这个算式中的每一个数字都是素数,而且这样的算式是唯一的。请你也研究一番,并把这个算式写出来。***