第09讲 枚举法分析和总结.pdf

第09讲 计数问题第01讲 枚举法 例 1 如图9—1，有八张卡片，上面写着自然数1至8．从中取出三张，要使三张卡片 上的数字之和为9．问有多少种不同的取法? 答案 3 种． 分析 三个数之和为9，则这三个数中任两个数之和必小于9，依据这个原则进行枚举 就可以．而且三个数中不能写有7、8，否则三数和必大于9． 详解 由于三个数和为9，且最小二个数可取1 和2，所以最大的数只可为6．这样依 据最大的数从6 不断往下取来枚举： 6、2、1；5、3、1；4、3、2． 共有3 种不同取法，所以答案为3． 评注 通常解题时，应从条件推出一些基本结论，这样可以减少枚举的范围，得出结论． 例2 现有1 分、2 分和5 分的硬币各四枚，用其中的一些硬币付2 角3 分钱，一共有 多少种不同的支付方法? 答案 5 种． 分析 由于要付2 角3 分钱，而其中1 分、2 分的硬币加起来共3×4=12分，因此必须 用上 5 分硬币，而且至少要3 枚5 分硬币，否则最多只能付2 角2 分钱(因为 12+2×5=22 分)． 详解 由于所有1 分、2 分硬币加起来共1 角2 分，因而至少要另外付3 个5 分硬币．所 以分用去4 个5 分硬币和3 个5 分硬币两种情况枚举： ①先付3 个5 分便币，再用 1 分、2 分币付剩下的8 分钱．这时有用4 个2 分、3 个2 分和2 个1 分、2 个2 分及4 个 1 分共3 种情形． ②先付4 个5 分硬币，再用1 分、2 分付剩下的3 分钱．这时有用1个2 分 1个 1 分、 3 个 1 分共2 种情形． 所以，一共有5 种不同的支付方法． 例3 有3 个工厂共订300 份《吉林日报》，每个工厂最少订99 份，最多101 份．问： 一共有多少种不同的订法? 答案 7 种． 分析 3 个工厂共订300 份，最少订99 份，这里先把99 份作为基本订数，因而相当于 把剩下的3 份在3 个工厂间分配一下．又由于最多 101份，也即是一个工厂最多再分配2 份．这样再按0、1、2 枚举即可． 详解 先考虑用每个工厂订99 份为基数，剩下的3 份报纸分配在3 个工厂中可以有以 下几种方式：0、1,2；0、2、1；1、0、2；1、2,0；1、1、1；2、0、1；2、1、0．共7 种 的订法．对应实际份数为：99、100、101；99、101、100；100、99、101；100、101、99； 100、100、100；101、99、100；101、100、99．一共有7 种不同的订法． ’ 例4 有25 本书，分成6 份，每份至少 1 本，且每份的本数都不相同．问有多少种分 法7 ． 答案 5 种分法． 分析 这里每份至少1 本且每份的本数都不相同，这样6 份至少有1+2+3+4+5+6=21 本书； 若最少一份为2 本，则至少有2+3+4+5+6+7=27 本书．因此最少1 份至多是1 本书．这样可 以从第二少的份数入手． 详解 从上面分析知，把6 份的书数从小到大排列，最少一份为1 本，因此下面的枚举 应从第二小的本数来入手．若第二小的本数是3 本，则6 份本数至少有1+3+4+5+6+7=26 本， 因此第二小的本数应为2 本．这样再枚举如下：1+2+3+4+5+10；1+2+3+4+6+9，1+2+3+4+7+ 8；1+2+3 十5+6+8；1+2+4+5+6+7．上面枚举是按第三本的本数从3 到4 枚举的．因此一共 5 种不同分法． 说明 在枚举时关键是从题意分析找出一个枚举的顺序，有了顺序才能不重不漏． 例5 甲、乙、丙、丁四个同学排成一行，从左到右数，如果甲不排在第一位置上，乙 不排在第二位置上，丙不排在第三个位置上，丁不排在第四个位置上，那么不同的排法共有 多少种? 答案 9 种． 分析 根据题意，由于甲不在第一位置上，这样甲只能在二、三、四位置上，从而第一 位上必能放乙、丙、丁这三种情形。然后再根据第二位置上的条件来进行枚举即可． 详解 按第一位置上放乙、丙、丁三种情形．若乙在第一位置上，则有乙甲丁丙、乙丁 甲丙、乙丙丁甲三种情形．若丙在第一位置上，则有丙甲丁乙、丙丁甲乙、丙丁乙甲，共三 种情