第2讲 枚举和筛选2.doc

第二讲 枚 举 与 筛 选 （二） 【竞技搏击】 例1、下图中有6个点，9条线段。一只甲虫从A点出发要沿着某几条线段爬到F点，行进中同一个点或同一条线段上只能经过一次，这只甲虫最多有多少种不同的走法？ 分析与解： 为了不重不漏地把所有走法都数出来，可以利用画枝形图的方法来枚举。所谓枝形图就是画一个树枝形状的图，用它来表示每一步可能的走法，可以非常直观形象地得到问题的答案。 甲虫从A点出发，第一步可有三种不同的走法，即先到B点，先到E点，先到D点。由B点到F点，又有3种不同的走法；直接到F点；经C点到F点；经E点到F点。由D.E两点到F点，也有3种不同的走法，请你想一想可以怎样走，在括号内填上合适的字母。 通过画枝形图枚举，可直观看出一共有9种不同走法。利用这种方法考虑一些稍复杂的问题时，经常需要画出几组枝形图。 例2、乒乓球团体比赛，采取五盘三胜制，即两个队进行比赛，哪个队先胜了三盘就取得了比赛的胜利，现在A、B两队进行比赛，A队最终获胜，请问：各盘的胜负情况有多少种可能？ 分析与解： 两个队的总比分有3种情况，即：A队以3：0胜，A队以3：1胜，A队以3：2获胜。这样，我们就可以分三类，画枝形图枚举出各盘的胜负情况。 若A队以3：0胜，只能有一种情况，可以表示为（A-A-A）说明共比赛3盘，都A获胜。 若A队以3：1胜，说明共比赛4盘，所以有3种可能，可以这样画枝形图（如图1）。 图1 图2 若A队以3：2胜，说明共比赛5盘，B队胜了2盘。可能A队先胜第一盘，也可能有B队先胜第一盘。请你按这两类考虑后面4盘的胜负情况，在括号内填胜队字母，完成枝形图（如图2）。 所以各盘的胜负情况有1＋3＋6=10（种）可能。 这道题，我们先从整体上进行分类，然后画枝形图枚举出每一类中的可能情况，这种枚举方法可以帮助我们解答一些比较复杂的计数问题。 例3、用一元钱购买2分邮票或4分邮票或8分邮票若干张，没有剩余钱，一共可以有多少种不同的买法？ 分析与解： 根据题意，用1元钱也就是100分钱，可以买三种邮票，也可以买其中的两种，还可以只买一种，只要没有剩余钱就可以。所以不同的买法会很多，一一枚举出来会很困难。我们可以用列表的方法来枚举，因为8分邮票最多可以买12张，最少可以买0张，因此分类可以画出下表。 8分邮票张数 12 11 10 9 8 7 6 5 4 3 2 1 0 合计买法种数 4分邮票张数 1 0 3 0 5 0 7 0 9 0 11 0 13 0 15 0 17 0 19 0 21 0 23 0 25 0 买法种数 2 4 6 8 10 12 14 16 18 20 22 24 26 182 表中没有考虑买2分邮票的张数，因为买8分邮票的张数确定后，4分邮票有几种买法，2分邮票就有几种买法。 我们先来考虑第一类的买法种数，8分邮票买12张，还剩4分钱，4分邮票可以买1张，也可以买0张，有两种买法。再考虑第二类，8分邮票买11张，还剩12分钱，4分邮票最多可以买3张，最少可以买0张，共有4种买法，我们在3和0之间点上省略号，简单表示4分邮票买的张数。请你用这种方法考虑下面各类的买法种数，并算出合计买法种数填在表中。 所以一共有182种不同的买法。 通过解答这道题，我们知道了，如果考虑的情况比较多，就可以利用列表的方法来枚举。为了提高这种枚举方法的解题速度，我们要善于在列表过程中发现规律，利用这个规律，帮助我们解答问题。 例4、 对自然数列1、2、 3、 4、 5……进行淘汰。淘汰原则是：凡不能表示为两个合数之和的自然数均被淘汰。如：“1”应被淘汰，但12可以写成两个合数8与4的和，不应被淘汰。那么保留下来的数从小到大数下去，第2000个数是多少？ 分析与解： 根据题意，要想直接考虑第2000个数是多少，比较困难，我们可以从反面枚举出所有被淘汰的数，知道淘汰了几个数，就能求出剩下的第2000个数是多少了。 请你根据按从小到大的顺序找出三个偶合数，再找出最小的奇合数，填在下面括号内。偶合数：（4）、（6）、（8）…；最小的奇合数是（9） 因为4+4=8，4+6=10，4+8=12说明从8开始的偶数都能写成两个合数的和不能被淘汰。而4+9=13，6+9=15，8+9=17，说明从13开始的奇数也都不应被淘汰。所以被淘汰的数有（1、2、3、4、5、6、7、9、11）共有9个。 所以保留下的第2000个数是2000＋9=2009。 注：本题是从事物的反面枚举的。 例5、有一批长度分别为1、2、3、4………11厘米的细木条，它们的数量都是足够多，从中适当选取三根木条作为三条边，可围成一个三角形，如果规定底边长是11厘米，你能围成多少种不同的三角形？ 分析与解： 题中规定了三角