枚举法

枚举法一、“枚举法”概念：在研究问题时，把所有可能发生的情况一一列举加以研究的方法叫做枚举法(也叫穷举法)。二、“枚举法”特点：有条理、不重复、不遗漏，使人一目了然。枚举法二•一、本节课重点：研究将一些东西分给三个人。•二、方法：先固定第一个人分到的东西的数量，然后再把剩下的东西分给两个人。在分好类的情况下，将每一类的情况有多少种方法枚举出来，最后将所有情况相加，就能得到整道题的答案。例题•例题1：有一个三位数的各位数字都不是0，且各位数字之和是6，这样的三位数共有多少个？•分析：从首位开始，依照从小到大的顺序依次来枚举出每一位。首位不能为0，最小为1，最大为4。想一想为什么不能是5，不能是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：汤姆、杰瑞和德鲁比都有蛀牙，所以他们一起去牙医诊所看病，医生发现他们一共有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,431汤姆有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这三种都算是同一种写法，我们将它们记作（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）当第一位为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）当第一堆有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位数有多少个？•分析：先看有无次序之分，因为是一个三位数，有个位、十位、百位之分，所以是有次序的，再确定范围，各位数字都不为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种情况5115+4+3+2+1=15（个）答：这样的三位数共有15个•2、费叔叔买来6个苹果，分给小悦、东东、阿奇三个人，每人至少一个，那么一共至少有多少种分法。•分析：先确定是否有次序，题目中告诉了我们三个人的名字，说明是有次序的；再确定范围，每人至少一个，所以最小是1，最大是4.解：当小悦分到1个苹果时，即首位为1，有以下4种情况，114,123,132,141.当小悦分到2个苹果时，即首位为2，有以下3种情况，213,222,231.当小悦分到3个苹果时，即首位为3，有以下2种情况，312,321.当小悦分到4个苹果时，即首位为4，有以下1种情况，4114+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+4+7,4+7+3,7+4+3是没有分别的，都是一堆是3个，一堆是4个，一堆是7个，可以表示为（3,4,7）；再确定范围，至少有3个，一共有14个，则最多有8个。•解：根具题意进行分配，一共有以下几种分法（3,3,8）（3,4,7）（3,5,6）（4,4,6）（4,5,5）答：根据题意一共有5种分法。