枚举法.docx

枚举法.docx

《枚举法.docx》由会员分享，可在线阅读，更多相关《枚举法.docx（4页珍藏版）》请在冰点文库上搜索。

枚举法

枚举法

在进行归纳推理时，如果逐个考察了某类事件的所有可能情况，因而得出一般结论，那么这结论是可靠的，这种归纳方法叫做枚举法．

　　特点：

将问题的所有可能的答案一一列举，然后根据条件判断此答案是否合适，合适就保留，不合适就丢弃。

　　枚举算法因为要列举问题的所有可能的答案，所有它具备以下几个特点：

　　1、得到的结果肯定是正确的；

　　2、可能做了很多的无用功，浪费了宝贵的时间，效率低下。

　　3、通常会涉及到求极值（如最大，最小，最重等）。

　　　枚举法，常常称之为穷举法，是指从可能的集合中一一枚举各个元素，用题目给定的约束条件判定哪些是无用的，哪些是有用的。

能使命题成立者，即为问题的解。

　　采用枚举法解题的基本思路：

（1）确定枚举对象、枚举范围和判定条件；

（2）一一枚举可能的解，验证是否是问题的解

　　下面我们就从枚举算法的的优化、枚举对象的选择以及判定条件的确定，这三个方面来探讨如何用枚举法解题。

　　例1：

百钱买百鸡问题：

有一个人有一百块钱，打算买一百只鸡。

到市场一看，大鸡三块钱一只，小鸡一块钱三只，不大不小的鸡两块钱一只。

现在，请你编一程序，帮他计划一下，怎么样买法，才能刚好用一百块钱买一百只鸡？

　　算法分析：

此题很显然是用枚举法，我们以三种鸡的个数为枚举对象（分别设为x,y,z）,以三种鸡的总数（x+y+z）和买鸡用去的钱的总数（x*3+y*2+z/3）为判定条件，穷举各种鸡的个数。

　上面的条件还有优化的空间，三种鸡的和是固定的，我们只要枚举二种鸡（x,y），第三种鸡就可以根据约束条件求得（z=100-x-y），这样就缩小了枚举范围，　在枚举算法中，枚举对象的选择也是非常重要的，它直接影响着算法的时间复杂度，选择适当的枚举对象可以获得更高的效率。

如下例：

　　例2、将1,2...9共9个数分成三组,分别组成三个三位数,且使这三个三位数构成1:

2:

3的比例,试求出所有满足条件的三个三位数.

　　例如:

三个三位数192,384,576满足以上条件.

　　算法分析：

这是1998年全国分区联赛普及组试题（简称NOIP1998pj，以下同）。

此题数据规模不大，可以进行枚举，如果我们不加思地以每一个数位为枚举对象，一位一位地去枚举：

　　　在枚举法解题中，判定条件的确定也是很重要的，如果约束条件不对或者不全面，就穷举不出正确的结果，我们再看看下面的例子。

习题

1、从1到100这一百个数中，每次取2个，要它们的和大于100，有多少种取法？

2、证明任何六个人的聚会上，至少存在三个人相互认识或者相互不认识。

3、一个木制的立方体，棱长为n个单位n（为大于2的整数），表面涂上黑色，用刀平行于立方体的各个面，将它切成n*n*n个棱长为单位长度的小立方体，若有一个面涂黑色的小立方体的个数等于没有一面涂黑色的小立方体的个数，求n的值。

4、比较a与1/a的大小。

习题答案

1、当较大数取100时，另一数有99种取法；

当较大数取99时，另一数有97种取法；

当较大数取98时，另一数有95种取法；

。

。

。

。

。

。

当较大数取51时，另一数有1种取法；

当较大数小于或等于50时，另一数不存在。

即50以下的数不符合条件。

故共有99+97+95+…….+3+1=2500种取法。

2、证明：

先从六个人中任意找出一个a，剩下五个人分成两类：

一类是与相互认识的，记为M；另一类是与不认识的，记为N。

由抽屉原理可知,M、N中至少有一个有3个人。

一、若M至少含有3人，设为b，c，d。

（1）b，c，d相互不认识，则结论成立；

（2）b，c，d至少有2人相互认识，不妨设b，c认识，则b、c、a相互认识，结论成立

二、若N至少含有3人，设为e，f，g。

（1）e，f，g相互不认识，则结论成立；

（2）e，f，g至少有2人相互不认识，不妨设e，f不认识，则e、f、a相互不认识，结论成立。

综上所述，结论成立。

3、解：

这n*n*n个棱长为单位长度的小立方体可分成下面四类：

（1）、三面涂黑色的小立方体的个数为8；

（2）、二面涂黑色的小立方体的个数为12（n-2）；

（3）、一面涂黑色的小立方体的个数为6（n-2）（n-2）；

（4）、没有一面涂黑色的小立方体的个数为（n-2）（n-2）（n-2）；

故有6（n-2）（n-2）=（n-2）（n-2）（n-2）

所以n=8

4、提示：

分7种情况，再综合。