枚举法(课堂PPT).ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,枚举法,一、“枚举法”概念,：在研究问题时，把所有可能发生的情况一一列举加以研究的方法叫做枚举法(也叫穷举法)。,二、“枚举法”特点：,有条理、不重复、不遗漏，使人一目了然。,1,枚举法二,一、本节课,重点,：研究将一些东西分给,三,个人。,二、,方法,：先固定第一个人分到的东西的数量，然后再把剩下的东西分给两个人。在分好类的情况下，将每一类的情况有多少种方法枚举出来，最后将所有情况相加，就能得到整道题的答案。,2,例题,例题1：,有一个三位数的各位数字都不是0，且各位数字之和是6，这样的三位数共有多少个？,分析：从首位开始，依照从小到大的顺序依次来枚举出每一位。,首位不能为0，最小为1，最大为4。想一想为什么不能是5，不能是6？,3,首位为1，有以下4种情况：,114，123,132,141.,首位为2，有以下3种情况：,213,222,231,首位为3，有以下2中情况：,312,321,首位为4，有以下1种情况：,411,则共有：4+3+2+1=10（种）情况,4,字典排列法：,从首位开始，按从小到大的顺序枚举第一位，对于每种情况再按从小到大的顺序枚举第二位，依次类推，这种方法称为,字典排列法。,顾名思义，就是类似于字典中各个词条的排列方法。,在很多枚举问题中，我们都可以用字典排列法枚举，大家在熟练应用之后，会觉得这样枚举起来，非常方便。,5,例题2：,汤姆、杰瑞和德鲁比都有蛀牙，所以他们一起去牙医诊所看病，医生发现他们一共有8颗蛀牙，他们三人可能分别有几颗蛀牙？,分析：都有蛀牙说明每个人的蛀牙数目不能为0，每人至少有1颗，一共有8颗蛀牙，所以最多的蛀牙数是6，想想为什么不是7.,题中有三个人的名字，所以三个人是有次序的，我们将汤姆看成是首位，杰瑞看成第二位，德鲁比看成第三位，则可以运用字典排列法枚举。,6,汤姆有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,7,汤姆有5颗，即首位为5，则有以下2种情况,512,521,汤姆有6颗，即首位为6，则有以下1种情况,611,则一共有1+2+3+4+5+6=21种情况。,8,有次序之分,：上面两道例题都强调了不同位置地数代表不同的顺序含义，即有次序之分。,无次序之分：,有些情况下，我们并不强调不同位置上的数代表不同的顺序含义，即无次序之分。,请看下面两道例题,9,例题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）,10,当第,一,位为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（种）情况,11,例题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,）,12,当第一堆有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（种）情况,13,练习题,1、有一些三位数的各位数字都不是0，且各位数字之和为7，这样的3位数有多少个？,分析：先看有无次序之分，因为是一个三位数，有个位、十位、百位之分，所以是有次序的，再确定范围，各位数字都不为0，各位数字之后为7，所以最小为1，最大为5，则应用字典排列法解题如下。,解：当首位为1时，有以下5种情况,115,124,133,142,151,当首位为2时，有以下4种情况,214,223,232,241,14,当首位为3时，有以下3种情况,313,322,331,当首位为4时，有以下2种情况,411,421,当首位为5时，有以下1种情况,511,5+4+3+2+1=15（个）,答：这样的三位数共有15个,15,2、,费叔叔买来6个苹果，分给小悦、东东、阿奇三个人，每人至少一个，那么一共至少有多少种分法。,分析：先确定是否有次序，题目中告诉了我们三个人的名字，说明是有次序的；再确定范围，每人至少一个，所以最小是1，最大是4.,16,解：当小悦分到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种分法。,17,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种分法。,18,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种分法。,19,