第1讲 枚举与筛选1.doc

第一讲 枚 举 与 筛 选 （一）【主题策划】1、从2、3、4、5、6、10、11这七个数中，任意取出两个数作分子、分母，就可以组成一个分数，在组成的若干个分数中，最简真分数有几个？ 分析与解:最简真分数就是分子、分母互质，且分子小于分母的分数。满足要求的最简真分数的分母只能是3、4、5、6、10、11这六个数， 分母是3的最简真分数是_，有（ ）个，； 分母是4的最简真分数是_，有（ ）个， 分母是5的最简真分数是_，有（ ）个， 分母是6的最简真分数是_，有（ ）个， 分母是10的最简真分数是_，有（ ）个， 分母是11的最简真分数是_，有（ ）个。 满足要求的最简真分数共有（ ）个。 这道题，我们通过把符合要求的最简真分数一一列举出来，而得到了问题的答案。这种解答问题的方法叫做“枚举法”，通常也称为“穷举法”，在解答很多有趣的数学问题时，经常用到这种方法。在这一讲中，我们就共同研究一些用“枚举法”解答的问题。 2、数一数，下图中共有多少个三角形？分析与解：这是一个梯形，被四条线段分成了九部分，其中的三角形大小不同、形状各异，位置也比较复杂，要不重不漏的数出一共有多少个很不容易。我们可以用“枚举法”来解答。为了便于枚举，我们将九部分分别用A、B、C、D、E、F、G、H、I九个字母来表示。其中的三角形最少由一部分组成，最多由五部分组成，请你按要求完成填空。在横线上填三角形可以用字母相加的形式来表示。如：由ABI三部分组成的三角形，在横线上用A+B+I来表示。1、由一部分组成的三角形有_，共（ ）个； 由两部分组成的三角形有_，共（ ）个； 由三部分组成的三角形有_，共（ ）个； 由四部分组成的三角形有_，共（ ）个； 由五部分组成的三角形有_，共（ ）个。2、共有（ ）个三角形。这道题我们是根据组成三角形“部分”的多少，分五种情况，把所有三角形列举出来。运用这种方法解题能否准确分类是很关键的，在下面几个例题的研究中，我们就来学习几种常用的分类枚举法。【五环旗下】例1、一本书共有560页，编页码时共用了多少个数字？分析与解：按页码位数不同可以把这些页数分为三类：1、一位数 有（9 ）个，共用数字19=9（个）。2、两位数 有（90 ）个，共用数字290=180（个）。3、三位数 有（461 ）个，共用数字3461=1383（个）。所以编页码时共用数字91801383=1572（个）。注：本题是按自然数位数不同情况进行分类。这是计算数字问题时常用的方法，其中一位数有9个，共用9个数字；两位数有90个，共用180个数字；三位数有900个，共用2700个数字；，这些知识是解答这类问题的基础知识，希望同学们能熟练掌握。例2、小红和小明都从1开始写连续自然数123456789101112，他们各自写到某个自然数后就不写了，已知小红比小明多写了65个自然数，这样小红共比小明多写了251个数字，小明共写了多少个数字？分析与解：因为小红比小明多写了65个自然数，这样共比小明多写了251个数字，251=45639，所以小红比小明多写的65个自然数中，有56个四位数，9个三位数。小明写的最后一个数是9999=990。小明写的数中一位数有9个，用9个数字；两位数有90个，用180个数字；三位数有891个，用2673个数字。所以小明共写了91802673=2862（个）数字。注：本题也是按自然数位数不同情况分类。例3、在大于100的整数中，被15除后，商和余数相同的数有多少个？分别是多少？分析与解：一个整数除以15的余数可以是014，在大于100的整数中，被15除后，商和余数相同的最小数是商7余7，最大是商14余14，所以可以分八类来考虑。商7余7的数是（112 ）， 商8余8的数是（128 ），商9余9的数是（144 ）， 商10余10的数是（160 ），商11余11的数是（176 ）， 商12余12的数是（192 ），商13余13的数是（208 ）， 商14余14的数是（224 ），注：这道题是按余数的不同来分类的。例4、小明手中有长度分别为1、2、3、4、5、6、7、8、9、10厘米小棒各一根，他想从中选出若干根摆成一个正方形。请你帮他计算一下共有多少种不同的选法？分析与解：用这些小棒摆出正方形的边长可以是13厘米、12厘米、11厘米、10厘米、9厘米、8厘米、7厘米，有七种情况：1、摆出边长是13厘米的正方形，有（ 1 ）种选法；2、摆出边长是12厘米的正方形，有（ 1 ）种选法；3、摆出边长是11厘米的正方形，有（ 5 ）种选法；4、摆出边长是10厘米的正方形，有（ 5 ）种选法；5、摆出边长是9厘米的正方形， 有（ 5 ）种选法；6、摆出边长是8厘米的正方形， 有（ 1 ）种选法；7、摆出边长是7厘米的正方形， 有（ 1 ）种选法；共有1+1+5+5+5+1+1=19（种）不同的选法。注：本题是按正方形的边长不同来分类的。例5、有25本书，把这些书分成6份，如果每份至少有一本，且每份的本数都不同，那么这25本书共有多少种不同的分法？分析与解：把25分成6个不同自然数相加的形式，共有多少种不同的分法。因为2至7六个数的和是27，比25大，所以这六个数中肯定有1。这样就可以按每种分法中，从1开始的连续自然数有几个来分类，可以分如下四类来考虑：（1）从1开始连续五个数，25=12345_ ( 1 )种（2）从1开始连续四个数，25=1234_ _ ( 2 )种（3）从1开始连续三个数，25=123_ _ ( 1 )种（4）从1开始连续二个数，25=12_ ( 1 )种共有1211=5（种）不同分法。注：这道题我们按从1开始的连续数的个数分类。这种分类方法，在解答把一个数分成若干个不相等的数的问题时，经常用到。例6、两个自然数a与b，它们的最小公倍数是60。那么这两个数的差有多少种不同的数值？（第十届迎春杯决赛试题）分析与解：60的约数有：1、2、3、4、5、6、10、12、15、20、30、60。设ab，按a的大小可以分为下面五类：（1）当a=60时，b可以是 1、2、3、4、5、6、10、12、15、20、30、60；（2）当a=30时，b可以是 4、12、20 ；（3）当a=20时，b可以是 3、6、12、15 ；（4）当a=15时，b可以是 4、12 。（5）当a=12时，b可以是 5、10 。两个数的差共有123422=23（种）不同的数值。注：本题是按较大数的不同情况来分类的。练习题：1、把150这50个数的平方数从小到大排成一个多位数149162536，请问这个多位数共有多少位数字？2、一部长篇小说分为上、下两卷，上卷比下卷多20页。在给这两卷书编页码时，上卷比下卷多用了79个数字，请问给这两卷书编页码共用了多少个数字？3、从1985到4891的整数中，十位数字与个位数字相同的数有多少个？4、在不大于100的自然数中，被13除后商和余数相同的数有多少个，分别是多少？答案与提示：本题按余数不同分类，余数和商可以是1、2、3、4、5、6、7共七类。所以符合要求的数有7个，分别是14、28、42、56、70、84、98。5、一个自然数除以9得到的商加上这个数除以10的余数，其和为12。请写出所有满足条件的自然数。6、从1、2、3、100这一百个自然数中，取两个数相加的结果是9的倍数，有多少种不同的取法？7、有一块画有33方格网的木板钉了16颗钉子（如下图），相邻两颗钉子之间的距离都是1厘米。以这些钉子为顶点，你能用橡皮筋围成多少个正方形？8、把27 个玻璃球放入六个盒子内（如下图），要求每盒内都有球，且球数都不相等，并按从左到右，球数从少