枚举法.ppt

1、枚举法,一、“枚举法”概念：在研究问题时，把所有可能发生的情况一一列举加以研究的方法叫做枚举法(也叫穷举法)。 二、“枚举法”特点：有条理、不重复、不遗漏，使人一目了然。,枚举法二,一、本节课重点：研究将一些东西分给三个人。 二、方法：先固定第一个人分到的东西的数量，然后再把剩下的东西分给两个人。在分好类的情况下，将每一类的情况有多少种方法枚举出来，最后将所有情况相加，就能得到整道题的答案。,例题,例题1：有一个三位数的各位数字都不是0，且各位数字之和是6，这样的三位数共有多少个？ 分析：从首位开始，依照从小到大的顺序依次来枚举出每一位。 首位不能为0，最小为1，最大为4。想一想为什么不能是5

2、，不能是6？,首位为1，有以下4种情况： 114，123,132,141. 首位为2，有以下3种情况： 213,222,231 首位为3，有以下2中情况： 312,321 首位为4，有以下1种情况： 411 则共有：4+3+2+1=10（种）情况,字典排列法：,从首位开始，按从小到大的顺序枚举第一位，对于每种情况再按从小到大的顺序枚举第二位，依次类推，这种方法称为字典排列法。 顾名思义，就是类似于字典中各个词条的排列方法。 在很多枚举问题中，我们都可以用字典排列法枚举，大家在熟练应用之后，会觉得这样枚举起来，非常方便。,例题2：汤姆、杰瑞和德鲁比都有蛀牙，所以他们一起去牙医诊所看病，医生发现他

3、们一共有8颗蛀牙，他们三人可能分别有几颗蛀牙？ 分析：都有蛀牙说明每个人的蛀牙数目不能为0， 每人至少有1颗，一共有8颗蛀牙，所以最多的蛀牙数是6，想想为什么不是7. 题中有三个人的名字，所以三个人是有次序的，我们将汤姆看成是首位，杰瑞看成第二位，德鲁比看成第三位，则可以运用字典排列法枚举。,汤姆有1颗，即首位为1，有以下6种情况 116,125,134,143, 152,161. 汤姆有2颗，即首位为2，有以下5种情况 215,224,233,242,251. 汤姆有3颗，即首位为3，有以下4种情况 314,323,332,341. 汤姆有4颗，即首位为4，有以下3种情况 413,422,4

4、31,汤姆有5颗，即首位为5，则有以下2种情况 512,521 汤姆有6颗，即首位为6，则有以下1种情况 611 则一共有1+2+3+4+5+6=21种情况。,有次序之分：上面两道例题都强调了不同位置地数代表不同的顺序含义，即有次序之分。 无次序之分：有些情况下，我们并不强调不同位置上的数代表不同的顺序含义，即无次序之分。 请看下面两道例题,例题3：老师让小明写出3个非零自然数，且3个数的和是9，如果数相同，顺序不同算同一种写法，例如1+2+6,2+1+6,6+1+2都算是同一种写法，那么小明一共有多少种不同的写法？ 分析： 1+2+6,2+1+6,6+1+2这三种都算是同一种写法，我们将它们

5、记作（1,2,6）。非零的自然数，说明最小为1，最大为7。 为了思路顺畅，方便解题，我们可以先假设是有次序的，然后再去掉重复的 当第一位为1时，有以下4种情况 （1,2,6）（1,3,5）（1,4,4）（1,5,3）（1,6,2）（1,7,1）,当第一位为2时，则有以下2种情况 （2,1,6）（2,2,5）（2,3,4）（2,4,3）（2,5,2）（2,6,1）（2,7，x ） 当第一位为3时，则有以下1种情况 （3,1,5）（3,2,4）（3,3,3）（3,4,2）（3（3,6，x ） 当第一位为4时，则有0种情况 （4,1,4）（4,2,3）（4,3,2）（4,4,1）（4,5，x） 当第

6、一位为5时，则有0种情况 （5,1,3）（5,2,2）（5,3,1）（5,4，x） 以此类推下去，发现都是重复的，所以一共有4+2+1=7（种）情况,例题4：生物老师让大家观察蚂蚁的习性，第二天小悦就在小区的广场上发现了12只黑蚂蚁，这12只蚂蚁恰好凑成了3堆，每堆至少有2只，请问：这3堆蚂蚁的只数有多少种可能？ 分析：在3堆蚂蚁中，每堆至少有2只，一共有12只，因此每堆蚂蚁至少有2只，至多有8只。同样为了方便解题，我们先假设是有次序的，然后再去掉重复的。 第一堆有2堆，则有以下4种情况 （2,2,8）（2,3,7）（2,4,6）（2,5,5）（2,6,4）（2,7,3）（2,8,2）,当第一

7、堆有3只，则有以下2种情况 （3,2,7）（3,3,6）（3,4,5）（3,5,4）（3,6,3）（3,7,2） 当第一堆有4只，则有以下1种情况 （4,2,6）（4,3,5）（4,4,4）（4,5,3）（4,6,2） 当第一堆有5只，则有0种情况 （5,2,5）（5,3,4）（5,4,3）（5,5,2） 当第一堆有6只，则有0种情况 （6,2,4）（6,3,3）（6,4,2） 当第一堆有7只，则有0种情况 （7,2,4）（7,3,2） 当第一堆有8只，则有0种情况 （8,2,2） 则一共有4+2+1=7（种）情况,练习题,1、有一些三位数的各位数字都不是0，且各位数字之和为7，这样的3位数有

8、多少个？ 分析：先看有无次序之分，因为是一个三位数，有个位、十位、百位之分，所以是有次序的，再确定范围，各位数字都不为0，各位数字之后为7，所以最小为1，最大为5，则应用字典排列法解题如下。 解：当首位为1时，有以下5种情况 115,124,133,142,151 当首位为2时，有以下4种情况 214,223,232,241,当首位为3时，有以下3种情况 313,322,331 当首位为4时，有以下2种情况 411,421 当首位为5时，有以下1种情况 511 5+4+3+2+1=15（个） 答：这样的三位数共有15个,2、费叔叔买来6个苹果，分给小悦、东东、阿奇三个人，每人至少一个，那么一共

9、至少有多少种分法。 分析：先确定是否有次序，题目中告诉了我们三个人的名字，说明是有次序的；再确定范围，每人至少一个，所以最小是1，最大是4.,解：当小悦分到1个苹果时，即首位为1，有以下4种情况，114,123,132,141. 当小悦分到2个苹果时，即首位为2，有以下3种情况，213,222,231. 当小悦分到3个苹果时，即首位为3，有以下2种情况，312,321. 当小悦分到4个苹果时，即首位为4，有以下1种情况，411 4+3+2+1=10（种） 答：一共有10种分法。,3：张奶奶从超市里买了10包果冻，分别装在3个塑料袋里，每袋至少一包，那么张奶奶一共有多少种不同的装果冻的方法？ 分析：先判断是否有序，没有说每袋分别分给谁，1+2+7，2+1+7,7+1+2这三种算是同一种分法，是无序的；再判断范围，每袋至少一包，所以最小是1，最大是8 解：根据题意可进行如下分配，（1,2,7）（1,3,6）（1,4,5）（2,2,6）（2,3,5）（2,4,4）（3,3,4） 答：一共有7种分法。,4、妈妈买了14个梨，打算把他们分成3堆，每堆至少有3个梨，请问：一共有多少种分法？ 分析：先看有无次序，分成3堆，没说分给谁，3+