第4讲第四讲枚举法进阶知识站牌五年级秋季五年级秋季几何计数进阶排列组合进阶五年级暑假枚举法进阶四年级春季排列组合初步四年级寒假几何计数初步用枚举法计算较复杂的几何，数论等问题漫画释义第9级上优秀A版教师版1\n课堂引入枚举法虽然是一种最简单，最基本的计数方法，但在生活中有很多的应用．例如，破译电脑密码.破译密码最简单的原理，就是尝试所有可能的密码组合，直到得到正确的密码．只要有足够的时间和存储空间，枚举密码原则上是可行的.教学目标1.掌握枚举法不重不漏的方法：分类，有序2.灵活运用枚举法解决各种计数问题．经典精讲枚举常用的方法有列表法、树形图、标数法、找规律及公式法．（1）列表法例：有一张伍拾元，4张贰拾元，8张拾元．要拿出80元，可以有多少种不同的拿法？取的张数4376548伍拾元1100000贰拾元0112340拾元3164208（2）树形图例：暑假里，一个学生在A、B、C三个城市游览．他今天在这个城市，明天就到另一个城市．假如他第一天在A市，第五天又回到A市，问他有几种不同的游览方案？2第9级上优秀A版教师版\n第4讲第一天第二天第三天第四天第五天BAACABACBAABAACACABBA（3）标数法例：如图，从A到B的最短路线有多少条？BA（4）找规律:适用于规律性强，情形较多的题．例：从1到100的自然数中，每次取出两个数，要使它们的和大于100，共有多少种取法？（5）公式法:此法比较适合于题目涉及的对象比较富有规律性，且情形繁多，数目很大，不宜用逐一列举来解．但通过适当的分类，逐一分析后，可利用公式解答．例题思路模块1：例1-2，树形图，标数法；模块2：例3-4，分类，定序枚举；模块3：例5，较复杂的枚举.例1如图,从起点走到终点,要求取出每个站点上的旗子,并且每个站点只允许通过一次,有种不同的走法。第9级上优秀A版教师版3\n起点终点【分析】给这些点依次标上字母（如左图）,然后采用枚举法（如右图）：cedcefafbdefcaedfbdcbdef共4种不同的走法。例2如图为一幅街道图，从A出发经过十字路口B，但不经过C走到D的不同的最短路线有条.DD61218666BC136BC123AA11【分析】到各点的走法数如右图所示.所以最短路径有18条.想想练练：一只兔子沿着方格的边从A到B,规定上只能往上或往右走，但是必须经过一座独木桥MN,这只兔子有_____种不同的走法.61218BM666N136123A111【分析】标数法，如右图．4第9级上优秀A版教师版\n第4讲【铺垫】如图所示，沿线段从A到B有多少条最短路线？13610ECBB1234FD111AAG【分析】图中B在A的右上方，因此从A出发，只能向上或者向右才能使路线最短，那么反过来想，如果到达了某一个点，也只有两种可能：要么是从这个点左边的点来的，要么是从这个点下边的点来的．那么，如果最后到达了B，只有两种可能：或者经过C来到B点，或者经D来到B点，因此，到达B的走法数目就应该是到达C点的走法数和到达D点的走法数之和，而对于到达C的走法，又等于到达E和到达F的走法之和，到达D的走法也等于到达F和到达G的走法之和，这样我们就归纳出：到达任何一点的走法都等于到它左侧点走法数与到它下侧点走法数之和，根据加法原理，我们可以从A点开始，向右向上逐步求出到达各点的走法数．如图所示，使用标数法得到从A到B共有10种不同的走法．【铺垫】如图，从A点到B点的最近路线有多少条？41020B1B361012341A111A【分析】使用标数法得出到B点的最近路线有20条．【拓展】小强从A点出发，到达B点的最短路线有________条．BB4213214429051428482591420123456AA11111【分析】标数法，如右图，132条．第9级上优秀A版教师版5\n穷举法与密码破译穷举法是一种针对于密码的破译方法。这种方法很像数学上的“完全归纳法”，并在密码破译方面得到了广泛的应用。简单来说就是将密码进行逐个推算，直到找出真正的密码为止。比如一个全部由数字组成的四位密码共有10000种组合，也就是说最多我们会尝试9999次才能找到真正的密码。利用这种方法我们可以运用计算机来进行逐个推算，也就是说我们破解任何一个密码也都只是一个时间问题。当然如果破译一个有8位而且可能拥有大小写字母、数字以及符号的密码用普通的家用电脑可能会用掉几个月甚至更多的时间去计算，其组合方法可能有几千万亿种组合。这样长的时间显然是不能接受的。其解决办法就是运用字典，所谓“字典”就是给密码锁定某个范围，比如英文单词以及生日的数字组合等，所有的英文单词不过10万个左右，这样可以大大缩小密码范围，很大程度上缩短了破译时间。例3数一数图中共有多少个正方形？【分析】按照面积大小分类枚举，设最小的正方形面积为1，则面积为1的正方形有4个；面积为2的正方形有4个；面积为4的正方形有5个；面积为8的正方形有1个；面积为16的正方形有1个；综上，图中共有4451115个正方形．想想练练：数一数图中共有多少个三角形？【分析】把图中最小三角形作为基数，然后按含有几个基数的三角形分类进行枚举．含一个基数的三角形共有8个；含两个基数的三角形共有4个；含四个基数的三角形共有4个；综上，整个图形中共有三角形84416个．6第9级上优秀A版教师版\n第4讲例4三条边的边长均为整数,且最长边的边长是8厘米,这样的三角形共有多少种？(提示：三角形两边边长之和大于第三边)【分析】由三角形两边之和大于第三边（由于是整数,至少是9）,两边之差小于第三边（至多是7）,其余两条边长至少是1,至多是8,枚举得满足要求的另外两条边之长的组合可以是：（1,8）（2,7）（2,8）（3,6）（3,7）（3,8）（4,5）（4,6）（4,7）（4,8）（5,5）（5,6）（5,7）（5,8）（6,6）（6,7）（6,8）（7,7）（7,8）（8,8）共1+2+3+4+4+3+2+1=20种.例5(学生版中仅有1-4)(1)从1～10中每次取两个不同的整数相加,和大于10的共有多少种取法？(2)从1～100中每次取两个不同的整数相加,和大于100的共有多少种取法？(3)从1～10中每次取两个不同的整数相加,和大于11的共有多少种取法？(4)从1～100中每次取两个不同的整数相加,和大于101的共有多少种取法？(5)从1～100中每次取两个不同的偶数相加,和大于101的共有多少种取法？(6)从1～100中每次取两个不同的奇数相加,和大于101的共有多少种取法？(7)从1～100中每次取两个不同的整数相加,和不超过150的共有多少种取法？【分析】(1)设第一个数较小,将和大于10的取法分为9类,枚举如下：因此,根据加法原理,共有：1+2+3+4+5+4+3+2+1=25种取法使和大于10．通过枚举也要能发现其中的规律,可以看出来此题的取法成等差数列,并在中间“拐弯”．(2)由(1)题的规律可知：“拐弯”的地方为第一个数为50,第二个数为51～100,共50种选择．因此此题答案为1+2+3+…+49+50+49+…+3+2+1=2500.第9级上优秀A版教师版7\n(3)同(1)题的方法,枚举如下：第一个数第二个数有几种第1类2101第2类39,102第3类48,9,103第4类57,8,9,104第5类67,8,9,104第6类78,9,103第7类89,102第8类9101共有1+2+3+4+4+3+2+1=20种取法．此题中间的“拐弯”数有两个,需要注意．(4)同(3)题,答案为1+2+3+…+49+49+…+3+2+1=2450.(5)枚举找规律．第一个数第二个数有几种第1类21001第2类498,1002第3类696,98,1003第…类………第24类4854,56,…,10024第25类5052,54,…,10025第26类5254,…,10024第…类………第49类981001因此答案为1+2+3+…+24+25+24+…+3+2+1=625(6)枚举找规律．第一个数第二个数有几种第1类3991第2类597,992第3类795,97,993第…类………第24类4953,55,…,9924第25类5153,55,…,9924第…类………第48类97991因此答案为1+2+3+…+24+24+…+3+2+1=600(7)枚举找规律．第一个数第二个数有几种第1类12--10099第2类23--10098第3类34--10097第…类………第49类4950--100518第9级上优秀A版教师版\n第4讲第50类5051--10050第51类5152--9948第52类5253--9846第53类5354--9744第…类………第74类7475,762因此答案为(99+98+97+…+51)+(50+48+…+4+2)=3675+650=4325想想练练：从1～10中每次取两个不同的整数相加,和小于12的共有多少种取法？【分析】设第一个数小于第二个数．枚举如下：第一个数第二个数有几种第1类12--109第2类23--97第3类34--85第4类45--73第5类561共9+7+5+3+1=25种．Q先生和S先生、P先生在一起做游戏.Q先生用两张小纸片，各写一个数.这两个数都是正整数，差数是1.他把一张纸片贴在S先生额头上，另一张贴在P先生额头上.于是，两个人只能看见对方额头上的数.Q先生不断地问：你们谁能猜到自己头上的数吗?S先生说：“我猜不到.”P先生说：“我也猜不到.”S先生又说：“我还是猜不到.”P先生又说：“我也猜不到.”S先生仍然猜不到；P先生也猜不到.S先生和P先生都已经三次猜不到了.可是，到了第四次，S先生喊起来：“我知道了!”P先生也喊道：“我也知道了!”问：S先生和P先生头上各是什么数?答案：S头上是8，P头上是7知识点总结第9级上优秀A版教师版9\n枚举法的核心是：分类，有序；枚举常用的方法：列表法、树形图、标数法、找规律、公式法．杯赛提高有长度分别为2,3,4,5,6,7,8,9的线段各一条,从中选出三条来组成三角形．那么有多少种不同的选法？(提示：三角形两边边长之和大于第三边)【分析】三角形两边之和大于第三边．分类如下：(2，3，4)，(2，4，5)，(2，5，6)，(2，6，7)，(2，7，8)，(2，8，9)；(3，4，5)，(3，4，6)，(3，5，6)，(3，5，7)，(3，6，7)，(3，6，8)，(3，7，8)，(3，7，9)；(4，5，6)，(4，5，7)，(4，5，8)，(4，6，7)，(4，6，8)，(4，6，9)，(4，7，8)，(4，7，9)，(4，8，9)(5，6，7)，(5，6，8)，(5，6，9)，(5，7，8)，(5，7，9)，(5，8，9)；(6，7，8)，(6，7，9)，(6，8，9)(7，8，9)共计：6+8+9+6+3+1=33种．附加题1.1995的数字和是1＋9＋9＋5=24，问：小于2000的四位数中数字和等于26的数共有多少个?【分析】小于2000的四位数千位数字是1，要它数字和为26，只需其余三位数字和是25．因为十位、个位数字和最多为9＋9=18，因此，百位数字至少是7．于是百位为7时，只有1799，一个；百位为8时，只有1889，1898，二个；百位为9时，只有1979，1997，1988，三个；总计共1＋2＋3=6个．2.1995的数字和是1＋9＋9＋5=24，问：小于2000的四位数中数字和等于24的数共有多少个?【分析】小于2000的四位数千位数字是1，要它数字和为24，只需其余三位数字和是23．因为十位、个位数字和最多为9918，因此，百位数字至少是5．于是百位为5时，只有1599一个；百位为6时，只有1689，1698两个；百位为7时，只有1779，1788，1797三个；百位为8时，只有1869，1878，1887，1896四个；百位为9时，只有1959，1968，1977，1986，1995五个；根据加法原理，总计共1234515个．3.小明用25元钱买了甲、乙、丙、丁4种书,共10册．已知甲、乙、丙、丁这4种书每本价格分10第9级上优秀A版教师版\n第4讲别为1元、2元、3元、4元,而且每种书至少买了一本．那么,共有多少种不同的购买方法？【分析】先从25元中各买四种书1册，这样还剩下25-1-2-3-4=15元钱，用15元钱买6本书，可以有书不买．列表如下：1元/本2元/本3元/本4元/本332112132231122141111433共有8种购买方式．4.小明用24元钱买了甲、乙、丙3种书,共8册．已知甲、乙、丙这3种书每本价格分别为1元、3元、4元,而且每种书至少买了一本．那么,共有多少种不同的购买方法？【分析】先每种书各买一本，这样还剩下24-1-3-4=16元，5本书共16元，可以有书不买．列表如下：1元／本3元／本4元／本11341共2种．5.明明带8元钱去商店买冰激凌．有三种冰激凌,售价分别是5元一支、2元一支和1元一支．如果这8元钱全部用于买这三种冰激凌,共有多少种不同的买法？【分析】有顺序地思考买法,如下表：5元／支2元／支1元／支总价8元1支1支1支5218(元)1支/3支5138(元)/4支/248(元)/3支2支23128(元)/2支4支22148(元)/1支6支2168(元)//8支188(元)所以,共有7种不同的买法．6.巍巍给他的四个小伙伴每人写了一张贺卡，并且装在信封里，结果粗心的巍巍把每一封信都装错了信封，问一共有多少种错装信封的可能？【分析】设巍巍的四个小伙伴分别为A,B,C,D，他们得到的贺卡编号分别为1,2,3,4第9级上优秀A版教师版11\nA234B1341413C441412212D313221321所以，共有9种可能．注：也可只分析A拿到2号的情况，共3种，由地位的对等性，A拿到3，4号也都是3种情况，因此共有3×3=9种可能．7.在下图中，用水平或者垂直的线段连接相邻的字母，当沿着这些线段行走时，正好拼出“APPLE”的路线共有多少条？A1||A—P—A1—3—1||||||A—P—P—P—A1—2—7—2—1||||||||||A—P—P—L—P—P—A1—2—4—15—4—2—1||||||||||||||A—P—P—L—E—L—P—P—A1—2—4—8—31—8—4—2—1【分析】要想拼出英语“APPLE”的单词，必须按照“A→P→P→L→E”的次序拼写．在图中的每一种拼写方式都对应着一条最短路径．如右图所示，用标数法得出共有31种不同的路径．8.把等边三角形的每一条边都5等分，过各分点作边的平行线，然后再擦掉一条线段，得到如下图形．数一数图中共有多少个三角形？【分析】法1：分类枚举按三角形的边长分类枚举，设最小的等边三角形边长为1，则边长为1的三角形有12335122423个（按照尖朝上与尖朝下分类）；边长为2的三角形有122319个；边长为3的三角形有1225个；边长为4的三角形有123个；边长为5的三角形有1个；综上，共有23953141个．12第9级上优秀A版教师版\n第4讲法2：排除法如果把这条线段补上，共有48个三角形；擦掉线段后，三角形减少241007个，所以图中共有48741个三角形．9.有长度分别为1,2,3,4,5,6,7,8,9的线段各一条,从中选出若干条来组成正方形．那么有多少种不同的选法？12394n【分析】设每边长度为n,解得7n11.25,如下分类：123n4n边长为11：2+9=3+8=4+7=5+6共1种；边长为10：1+9=2+8=3+7=4+6共1种；边长为9：9=1+8=2+7=3+6=4+5,从5个中去掉1个,共有5种选择；边长为8：8=1+7=2+6=3+5,共1种；边长为7：7=1+6=2+5=3+4,共1种；共1+1+5+1+1=9种选法．家庭作业1.一个学生假期往A、B、C三个城市游览．他今天在这个城市，明天就到另一个城市．假如他第一天在A市，第五天又回到A市．问他的游览路线共有几种不同的方案？第一天A第二天BC第三天ACAB第四天BCABBCAC第五天AAAAAA【分析】可见他第五天回到A市的不同游览路线共有6种.2.在下图的街道示意图中，C处因施工不能通行，从A到B的最短路线有多少条？3BB16220C13C12213A11A1【分析】因为B在A的右上方，由标数法可知，从A到B的最短路径上，到达任何一点的走法数都等于到它左侧点的走法数与到它下侧点的走法数之和．而C是一个特殊的点，因为不能通行，所以不可能有路线经过C，可以认为到达C点的走法数是0．接下来，可以从左下角开始，按照加法原理，依次向上向右填上到各点的走法数．如图，从A到B的最短路线有6条．第9级上优秀A版教师版13\n3.把等边三角形的每一条边都4等分，过各分点作边的平行线，得到如下图形．数一数图中共有多少个三角形？【分析】按三角形的边长分类枚举，设最小的等边三角形边长为1，则边长为1的三角形有123412316个（按照尖朝上与尖朝下分类）；边长为2的三角形有12317个；边长为3的三角形有123个；边长为4的三角形有1个；综上，共有1673127个．4.有长度分别为2,3,4,5,6的线段各一条,从中选出三条来组成三角形．那么有多少种不同的选法？【分析】三角形两边之和大于第三边．分类如下：(2,3,4)(2,4,5)(2,5,6);(3,4,5)(3,4,6)(3,5,6);(4,5,6).共有7种不同的选法．5.从1～8中每次取两个不同的数相加，和大于10的共有多少种取法？【分析】两个数和为11的一共有3种取法；两个数和为12的一共有2种取法；两个数和为13的一共有2种取法；两个数和为14的一共有1种取法；两个数和为15的一共有1种取法；一共有3+2+2+1+1=9种取法．6.袋中有3个红球，4个黄球和5个白球，小明从中任意拿出6个球，他拿出球的情况共有________种可能．【分析】白球的数最多，红球的数最少，可以通过红球分类，最后用白球的数来补充剩下的．枚举如下(注：当其他球确定后，白球也就定下来了．此表中白球并未写出)：红球(不超过3)黄球(不超过4)白球(不超过5)共几种01，2，3，4410，1，2，3，4520，1，2，3，4530，1，2，3414第9级上优秀A版教师版\n第4讲可见他拿出球的情况共有：4+5+5+4=18（种）．A版学案【学案1】A、B、C三个小朋友互相传球，先从A开始发球(作为第一次传球)，这样经过了5次传球后，球恰巧又回到A手中，那么不同的传球方式共多少种？【分析】如图，A第一次传给B，到第五次传回A有5种不同方式．同理，A第一次传给C，也有5种不同方式．所以，不同的传球方式共有55=10种．BCACBABABACCBC【学案2】小君家到学校的道路如图所示。从小君家到学校有_________种不同的走法。（只能沿图中向右向下的方向走）小君家小君家11112112322413710学校学校【分析】如右图，标数法．共10种．【学案3】把等边三角形的每一条边都4等分，过各分点作边的平行线，然后再擦掉一条线段，得到如下图形．数一数图中共有多少个三角形？【分析】法1：分类枚举按三角形的边长分类枚举，设最小的等边三角形边长为1，则边长为1的三角形有122411314个（按照尖朝上与尖朝下分类）；边长为2的三角形有11215个；第9级上优秀A版教师版15\n边长为3的三角形有112个；边长为4的三角形有1个；综上，共有1452122个．法2：排除法如果把这条线段补上，共有27个三角形；擦掉线段后，三角形减少22105个，所以图中共有27522个三角形．【学案4】有一批长度分别为1、2、3、4、5、6、7、8、9、10与11厘米的细木条,它们的数量都足够多,从中适当选取3根木条作为三条边,可围成一个三角形．如果规定其中一边是11厘米长,你能围成多少个不同的三角形?(提示：三角形两边边长之和大于第三边,两边边长之差小于第三边.)【分析】一个三角形,任何两条边的长度之和,比余下的一条边长．在本题中,设底边是11厘米的三角形其余二边分别是a及b,则必有11<a+b．此外,为确切起见,可设a≤b,于是(a,b)的可能的值便有：(11,11)；(10,10),(10,11)；(9,9),(9,10),(9,11)；(8,8),(8,9),(8,10),(8,11)；(7,7),(7,8),(7,9),(7,10),(7,11)；(6,6),(6,7),(6,8),(6,9),(6,10),(6,11)；(5,7),(5,8),(5,9),(5,10)(5,11)；(4,8),(4,9),(4,10),(4,11)；(3,9),(3,10),(3,11)；(2,10),(2,11)；(1,11)．共1+2+3+4+5+6+5+4+3+2+1=36种.16第9级上优秀A版教师版