第25讲 递推、对应法计数（知识梳理+例题讲解+考点练习）-六年级奥数培优讲义

第25讲 递推、对应法计数 （知识梳理+例题讲解+考点练习） 【学习目标】 1.掌握递推思想的核心： 理解通过已知初始条件，利用规律逐步推导出后续状态或结果的思想方法。 2.学会建立递推关系式： 能够分析问题，找到相邻状态（如第n项与第n-1项、第n项）之间的数量关系，并用数学式子表达出来。 3.熟练运用递推方法解决问题： 能够运用递推关系解决涉及序列、计数、图形排列、路径选择等典型问题。 4.理解对应法的基本思想： 认识到通过建立两个集合元素间的一一对应关系，可以简化复杂计数问题。 5.掌握常见对应技巧： 学会运用图形对应、模型对应、函数对应等方法，将不易直接计数的问题转化为容易计数的问题。 知识梳理 知识点一、递推法计数 核心思想： 将一个复杂的大问题，分解成一系列相似的、规模较小的子问题。通过已知的初始状态（边界条件），利用问题本身蕴含的规律（递推关系），逐步推导出后续状态，最终解决整个问题。特别适用于具有重复结构或过程的问题。 常见题型与解题步骤： 1.数列递推问题： (1)题型： 找规律填数（如斐波那契数列），求序列的第n项。 (2)步骤： ①观察前几项（初始条件）。 ②寻找相邻项（如第n项与第n-1项、第n-2项）之间的关系（递推公式）。 ③利用递推公式逐步计算出所求项。 ④(进阶：尝试求解通项公式) 2.图形计数递推： (1)题型： 数三角形、数线段、数长方形、数正方形、数点阵中的图形个数（如n×n网格）。 (2)步骤： ①考虑较小规模图形（如1×1, 2×2网格）的计数结果（初始条件）。 ②思考当规模增加一级（如从(n-1)×(n-1)到n×n）时，新增的图形数量与之前图形数量的关系（递推关系）。 ③建立递推公式。 ④利用递推公式计算目标规模下的图形数量。 3.路径计数递推： (1) 题型： 从网格图的A点到B点，只能向右或向上走，求最短路径条数（经典问题）。爬楼梯问题（每次走1级或2级）。 (2) 步骤： ①确定起点状态（到达起点有1种方式）。 ②分析到达图中任意一点P的方式：只能从其左邻点或下邻点走过来。 ③因此，到达P点的路径数 = 到达其左邻点的路径数 + 到达其下邻点的路径数（递推关系）。 ④利用此关系，从起点开始，逐步向右上角递推计算。 4.分步完成任务的递推： (1)题型： 汉诺塔问题移动步数、信封错装问题（错位排列）、特定要求的排队方式计数。 (2)步骤： ①定义状态（如n个盘子从A移到C的步数f(n)）。 ②思考完成最终任务的关键一步依赖于前一个状态（如移动n个盘子，必须先移动上面n-1个盘子）。 ③找到f(n)与f(n-1) (或更早状态) 的关系（递推公式）。 ④利用初始条件（如f(1)=1）递推求解。 关键： 找准初始条件，分析清楚递推关系（状态转移方程）。 知识点二、对应法计数 核心思想： 当直接计数一个集合A的元素个数比较困难时，可以设法建立集合A与另一个易于计数的集合B之间的一一对应关系。因为两个集合元素一一对应，所以集合A的元素个数就等于集合B的元素个数。关键在于找到合适的对应方式。 常见题型与技巧： 1.图形对应（模型对应）： (1)题型： 求特定图形（如特定长度的线段、特定大小的三角形）的个数。 (2)技巧： 通过添加辅助线、分割图形或构造辅助模型，使要数的对象与一个标准、易数的对象（如点、基本线段、基本格子）建立一一对应关系。 (3)例子： 数平行四边形个数 ↔ 对应数两条相交线段的对数。 2.函数对应（映射）： (1)题型： 计算满足特定条件的组合数（如选取若干元素）。 (2)技巧： 构造一个从待计数集合到另一个易计数集合的双射函数（一一映射）。 (3)经典例子： 证明组合数公式 C(n, k) = C(n, n-k) 时，可建立“选k个元素”与“不选n-k个元素”的一一对应关系。 3.分组对应： (1)题型： 计算特定分组的个数。 (2)技巧： 将分组方式与某种易于计数的排列或选择方式建立对应。 (3)例子： 计算将n个相同的球放入k个不同的盒子（允许空盒）的方法数 ↔ 对应在n个球和k-1个隔板中进行排列的方式数（隔板法）。 4.利用对称性： (1)题型： 求对称图形中满足条件的元素个数。 (2)技巧： 利用图形的对称性，将不同部分的元素建立对应关系，从而简化计数。 5.转化问题： (1)题型： 原问题直接计数困难。 (2)技巧： 通过改变视角或重新定义对象，将原问题转化为一个已知的、可以用公式或简单方法计数的等价问题，建立对应关系。 (3)例子： 计算网格图中非降路径条数 ↔ 对应选择向右和向上步数的组合数。 关键： 发挥想象力，找到那个“易于计数”的集合B，并建立清晰、无遗漏、无重复的一一对应关系。 知识点三、综合应用与思维提升 1.递推与对应的结合： 很多复杂问题需要同时运用递推法和对应法。例如，在路径计数中，递推公式的推导本身可能就利用了某种对应思想。 2.模型化思维： 将实际问题抽象为递推模型或寻找对应关系，是解决此类问题的核心能力。 3.从特殊到一般： 通常从简单情况（初始条件）入手，观察规律，再推广到一般情况。 4.枚举验证： 对于小规模问题，枚举所有情况是验证递推关系或对应关系正确性的好方法。 例题讲解 一、递推法计数 【例题1】如图，用水平线或竖直线连结相邻汉字，沿着这些线读下去，正好可以读成“我爱学而思”，那么可读成“我爱学而思”的路线有( )条。 【例题2】如图所示，沿线段从A到B有多少条最短路线？ 【例题3】如下表，请读出“我们学习好玩的数学”这9个字，要求你选择的9个字里能连续（即相邻的字在表中也是左右相邻或上下相邻），这里共有多少种完整的“我们学习好玩的数学”的读法。 二、对应法计数 【例题1】在下图中，不包含☆的长方形有 个。 【例题2】有多少个四位数，满足个位上的数字比千位数字大，千位数字比百位大，百位数字比十位数字大？ 【例题3】用一张如图所示的纸片盖住方格表中的四个小方格，共有多少种不同的放置方法？ 考点练习 一、递推法计数 1．如图，8个单位正方体拼成大正方体，沿着面上的格线，从A到B的最短路线共有( )条。 2．如图所示，一个花坛的道路由3个圆和5条线段组成，小兔要从A处做到B处，如果它在圆上只能顺时针方向走，在线段上只能从小圆走向大圆，且每条道路最多走一次，那么小兔可以选择的不同路线有( )条。 3．如图所示，科学家“爱因斯坦”的英文名拼写为“Einstein”，按图中箭头所示方向有( )种不同的方法拼出英文单词“Einstein”。 4．下图中的“我爱希望杯”有 种不同的读法。 5．如图，用水平线或竖直线连结相邻汉字，沿着这些线读下去，正好可以读成“祖国明天更美好”，那么可读成“祖国明天更美好”的路线有( )条。 6．如图为一幅街道图，从出发经过十字路口，但不经过走到的不同的最短路线有( )条。 7．如图，某城市的街道由5条东西向马路和7条南北向马路组成，现在要从西南角的处沿最短的路线走到东北角出，由于修路，十字路口不能通过，那么共有( )种不同走法。 8．有6个木箱，编号为1，2，3，…，6，每个箱子有一把钥匙，6把钥匙各不相同，每个箱子放进一把钥匙锁好。先挖开1，2号箱子，可以取出钥匙去开箱子上的锁，如果最终能把6把锁都打开，则说这是一种放钥匙的“好”的方法，那么“好”的方法共有( )种。 9．设、为正八边形的相对顶点，顶点处有一只青蛙，除顶点外青蛙可以从正八边形的任一顶点跳到其相邻两个顶点中任意一个，落到顶点时青蛙就停止跳动，则青蛙从顶点出发恰好跳次后落到的方法总数为( )种。 10．在下图的街道示意图中，C处因施工不能通行，从A到B的最短路线有多少条？ 11．在下图中，用水平或者垂直的线段连接相邻的字母，当沿着这些线段行走是，正好拼出“APPLE”的路线共有多少条？ 12．图中有10个编好号码的房间，你可以从小号码房间走到相邻的大号码房间，但不能从大号码走到小号码，从1号房间走到10号房间共有多少种不同的走法？ 13．如下图，一只蜜蜂从处出发，回到家里处，每次只能从一个蜂房爬向右侧邻近的蜂房而不准逆行，共有多少种回家的方法？ 二、对应法计数 1．如图，其中同时包括两个☆的长方形有( )个。 2．学学和思思一起洗个互不相同的碗（顺序固定），思思洗好的碗一个一个往上摞，学学再从最上面一个一个地拿走放入碗柜摞成一摞，思思一边洗，学学一边拿，问学学摞好的碗一共有( )种不同的摞法。 3．由20个边长为1的小正方形拼成一个长方形中有一格有“☆”图中含有“☆”的所有长方形（含正方形）共有 个，它们的面积总和是 。 ☆ 4．数3可以用4种方法表示为一个或几个正整数的和，如3，，，。问：1999表示为一个或几个正整数的和的方法有多少种？ 5．圆周上有12个点，其中一个点涂红，还有一个点涂了蓝色，其余10个点没有涂色，以这些点为顶点的凸多边形中，其顶点包含了红点及蓝点的多边形称为双色多边形；只包含红点（蓝点）的多边形称为红色（蓝色）多边形。不包含红点及蓝点的称无色多边形。试问，以这12个点为顶点的所有凸多边形（边数可以从三角形到12边形）中，双色多边形的个数与无色多边形的个数，哪一种较多？多多少个？ 6．用1元，2元，5元，10元四种面值的纸币若干张（不一定要求每种都有），组成99元有 种方法，组成101元有种方法，则( )。 7．有一类各位数字各不相同的五位数，它的千位数字比左右两个数字大，十位数字也比左右两位数字大。另有一类各位数字各不相同的五位数，它的千位数字比左右两个数字小，十位数字也比左右两位数字小。请问符合要求的数与，哪一类的个数多？多多少？ 8．游乐园的门票1元1张，每人限购1张。现在有10个小朋友排队购票，其中5个小朋友只有1元的钞票，另外5个小朋友只有2元的钞票，售票员没有准备零钱。问有多少种排队方法，使售票员总能找得开零钱？ 9．如图，其中的每条线段都是水平的或竖直的，边界上各条线段的长度依次为5厘米、7厘米、9厘米、2厘米和4厘米、6厘米、5厘米、1厘米。求图中长方形的个数，以及所有长方形面积的和。 10．将1～12这12个数填入到2行6列的方格表中，使得每行右边比左边的大，每一列上面比下面的大，共有多少种填法？ 11．在8×8的方格棋盘中，取出一个由三个小方格组成的“L”形（如图），一共有多少种不同的方法？    试卷第1页，共3页 第 1 页 共 20 页 学科网（北京）股份有限公司 $ 第25讲 递推、对应法计数 （知识梳理+例题讲解+考点练习） 【学习目标】 1.掌握递推思想的核心： 理解通过已知初始条件，利用规律逐步推导出后续状态或结果的思想方法。 2.学会建立递推关系式： 能够分析问题，找到相邻状态（如第n项与第n-1项、第n项）之间的数量关系，并用数学式子表达出来。 3.熟练运用递推方法解决问题： 能够运用递推关系解决涉及序列、计数、图形排列、路径选择等典型问题。 4.理解对应法的基本思想： 认识到通过建立两个集合元素间的一一对应关系，可以简化复杂计数问题。 5.掌握常见对应技巧： 学会运用图形对应、模型对应、函数对应等方法，将不易直接计数的问题转化为容易计数的问题。 知识梳理 知识点一、递推法计数 核心思想： 将一个复杂的大问题，分解成一系列相似的、规模较小的子问题。通过已知的初始状态（边界条件），利用问题本身蕴含的规律（递推关系），逐步推导出后续状态，最终解决整个问题。特别适用于具有重复结构或过程的问题。 常见题型与解题步骤： 1.数列递推问题： (1)题型： 找规律填数（如斐波那契数列），求序列的第n项。 (2)步骤： ①观察前几项（初始条件）。 ②寻找相邻项（如第n项与第n-1项、第n-2项）之间的关系（递推公式）。 ③利用递推公式逐步计算出所求项。 ④(进阶：尝试求解通项公式) 2.图形计数递推： (1)题型： 数三角形、数线段、数长方形、数正方形、数点阵中的图形个数（如n×n网格）。 (2)步骤： ①考虑较小规模图形（如1×1, 2×2网格）的计数结果（初始条件）。 ②思考当规模增加一级（如从(n-1)×(n-1)到n×n）时，新增的图形数量与之前图形数量的关系（递推关系）。 ③建立递推公式。 ④利用递推公式计算目标规模下的图形数量。 3.路径计数递推： (1) 题型： 从网格图的A点到B点，只能向右或向上走，求最短路径条数（经典问题）。爬楼梯问题（每次走1级或2级）。 (2) 步骤： ①确定起点状态（到达起点有1种方式）。 ②分析到达图中任意一点P的方式：只能从其左邻点或下邻点走过来。 ③因此，到达P点的路径数 = 到达其左邻点的路径数 + 到达其下邻点的路径数（递推关系）。 ④利用此关系，从起点开始，逐步向右上角递推计算。 4.分步完成任务的递推： (1)题型： 汉诺塔问题移动步数、信封错装问题（错位排列）、特定要求的排队方式计数。 (2)步骤： ①定义状态（如n个盘子从A移到C的步数f(n)）。 ②思考完成最终任务的关键一步依赖于前一个状态（如移动n个盘子，必须先移动上面n-1个盘子）。 ③找到f(n)与f(n-1) (或更早状态) 的关系（递推公式）。 ④利用初始条件（如f(1)=1）递推求解。 关键： 找准初始条件，分析清楚递推关系（状态转移方程）。 知识点二、对应法计数 核心思想： 当直接计数一个集合A的元素个数比较困难时，可以设法建立集合A与另一个易于计数的集合B之间的一一对应关系。因为两个集合元素一一对应，所以集合A的元素个数就等于集合B的元素个数。关键在于找到合适的对应方式。 常见题型与技巧： 1.图形对应（模型对应）： (1)题型： 求特定图形（如特定长度的线段、特定大小的三角形）的个数。 (2)技巧： 通过添加辅助线、分割图形或构造辅助模型，使要数的对象与一个标准、易数的对象（如点、基本线段、基本格子）建立一一对应关系。 (3)例子： 数平行四边形个数 ↔ 对应数两条相交线段的对数。 2.函数对应（映射）： (1)题型： 计算满足特定条件的组合数（如选取若干元素）。 (2)技巧： 构造一个从待计数集合到另一个易计数集合的双射函数（一一映射）。 (3)经典例子： 证明组合数公式 C(n, k) = C(n, n-k) 时，可建立“选k个元素”与“不选n-k个元素”的一一对应关系。 3.分组对应： (1)题型： 计算特定分组的个数。 (2)技巧： 将分组方式与某种易于计数的排列或选择方式建立对应。 (3)例子： 计算将n个相同的球放入k个不同的盒子（允许空盒）的方法数 ↔ 对应在n个球和k-1个隔板中进行排列的方式数（隔板法）。 4.利用对称性： (1)题型： 求对称图形中满足条件的元素个数。 (2)技巧： 利用图形的对称性，将不同部分的元素建立对应关系，从而简化计数。 5.转化问题： (1)题型： 原问题直接计数困难。 (2)技巧： 通过改变视角或重新定义对象，将原问题转化为一个已知的、可以用公式或简单方法计数的等价问题，建立对应关系。 (3)例子： 计算网格图中非降路径条数 ↔ 对应选择向右和向上步数的组合数。 关键： 发挥想象力，找到那个“易于计数”的集合B，并建立清晰、无遗漏、无重复的一一对应关系。 知识点三、综合应用与思维提升 1.递推与对应的结合： 很多复杂问题需要同时运用递推法和对应法。例如，在路径计数中，递推公式的推导本身可能就利用了某种对应思想。 2.模型化思维： 将实际问题抽象为递推模型或寻找对应关系，是解决此类问题的核心能力。 3.从特殊到一般： 通常从简单情况（初始条件）入手，观察规律，再推广到一般情况。 4.枚举验证： 对于小规模问题，枚举所有情况是验证递推关系或对应关系正确性的好方法。 例题讲解 一、递推法计数 【例题1】如图，用水平线或竖直线连结相邻汉字，沿着这些线读下去，正好可以读成“我爱学而思”，那么可读成“我爱学而思”的路线有( )条。 【答案】31 【分析】只有一个思，可以从后向前考虑，也就是“我爱学而思”和“思而学爱我”的方法数是一样的，然后按照思→而→学→爱→我的顺序进行标数。 【详解】如图所示： 共有种。 【点睛】本题考查的是最短路径的问题，标数法是求解此类问题最常用的方法。 【例题2】如图所示，沿线段从A到B有多少条最短路线？ 【答案】10条 【分析】图中B在A的右上方，因此从A出发，只能向上或者向右才能使路线最短，那么反过来想，如果到达了某一个点，也只有两种可能：要么是从这个点左边的点来的，要么是从这个点下边的点来的。从A开始，依次标数，然后确定从A到B的最短路径的条数。 【详解】如图所示： 答：沿线段从A到B有10条最短路线。 【点睛】最短路线需要5步，所以最短路线的条数相当于是从5个元素中选出2个元素的方法数。 【例题3】如下表，请读出“我们学习好玩的数学”这9个字，要求你选择的9个字里能连续（即相邻的字在表中也是左右相邻或上下相邻），这里共有多少种完整的“我们学习好玩的数学”的读法。 【答案】70种 【分析】第一个字只能选位于左上角的“我”，以后每一个字都只能选择前面那个字的下方或右方的字，从左上角开始，依次标数求解。 【详解】如图所示： 答：这里共有70种完整的“我们学习好玩的数学”的读法。 【点睛】本题考查的是标数法计数问题，首先要确定标数的方向，然后再从起点开始依次标数。 二、对应法计数 【例题1】在下图中，不包含☆的长方形有 个。 【答案】297 【分析】求出长方形的总数，以及包含☆的长方形的数量，用长方形的总数减去包含☆的长方形的数量，得到不包含☆的长方形的数量。 【详解】所有长方形总数： （1＋2＋3＋4＋5＋6）×（1＋2＋3＋4＋5＋6）＝441（个） 包含☆的长方形： 3×3×4×4＝144（个） 不包含☆的长方形： 441－144＝297 （个） 【点睛】在考虑问题的时候，如果从正面考虑不方便，可以从反面进行分析。 【例题2】有多少个四位数，满足个位上的数字比千位数字大，千位数字比百位大，百位数字比十位数字大？ 【答案】个 【分析】由于四位数的四个数位上的数的大小关系已经非常明确，而对于从0～9中任意选取的4个数字，它们的大小关系也是明确的，那么由这4个数字只能组成1个符合条件的四位数（题目中要求千位比百位大，所以千位不能为0，本身已符合四位数的首位不能为0的要求，所以进行选择时可以把0包含在内），也就是说满足条件的四位数的个数与从0～9中选取4个数字的选法是一一对应的关系。 【详解】满足条件的四位数有个； 答：满足条件的四位数有210个。 【点睛】本题考查的是对应法计数问题，解题的关键在于寻找其中的对应关系。 【例题3】用一张如图所示的纸片盖住方格表中的四个小方格，共有多少种不同的放置方法？ 【答案】种 【分析】直接考虑如何覆盖是比较麻烦的，可以考虑将问题进行转化，如图，将纸片中的一个特殊方格染为黑色，考虑黑格在6×6方格表中的位置，它不能位于四个角上，若黑格位于方格表中间的某一位置时，纸片有4种不同的放法，若黑格位于方格表边上如图深色阴影所示的方格中时，纸片的位置随之确定，即只有1种放法；分类枚举出每一种的数量，相加得到总数。 【详解】若黑格位于方格表中间正方形内的某格时，纸片有4种不同的放法，共计种； 若黑格位于方格表边上的方格中时，纸片的位置随之确定，即只有1种放法，此类放法有种。 所以，纸片共有种不同的放置方法。 答：共有80种不同的放置方法。 【点睛】本题考查的是对应法计数的问题，解题的关键在于转化。 考点练习 一、递推法计数 1．如图，8个单位正方体拼成大正方体，沿着面上的格线，从A到B的最短路线共有( )条。 【答案】54 【分析】从A开始，第一步，先在左、前、下面标数，第二步在上、右、后面上标数，最终确定到达B的所有方法数。 【详解】如图所示： 18×3＝54（条） 所以从A到B的最短路线共有54条。 【点睛】本题考查的是立体图形中的计数问题，如果分开考虑的话，相当于是进行了两次平面图形的标数问题。 2．如图所示，一个花坛的道路由3个圆和5条线段组成，小兔要从A处做到B处，如果它在圆上只能顺时针方向走，在线段上只能从小圆走向大圆，且每条道路最多走一次，那么小兔可以选择的不同路线有( )条。 【答案】6 【分析】在线段上只能从小圆走向大圆，且每条道路最多走一次，也就是求最短路径的问题，用标数法求解。 【详解】采用标数法，如图所示： 所以不同路线共有6条。 【点睛】本题考查的是标数法计数问题，标数法是求解最短路径问题最常用的方法。 3．如图所示，科学家“爱因斯坦”的英文名拼写为“Einstein”，按图中箭头所示方向有( )种不同的方法拼出英文单词“Einstein”。 【答案】60 【分析】根据英文“Einstein”的字母顺序，确定的标数顺序，从上往下依次标数即可。 【详解】如图所示: 共有（种）不同拼法。 【点睛】本题考查的是标数法，标数法是归纳递推计数的一种。 4．下图中的“我爱希望杯”有 种不同的读法。 【答案】16 【分析】“我爱希望杯”的读法也就是从“我”走到“杯”的方法，从“我”开始，向右下方进行标数，最后把到达每个“杯”的路线条数相加即可。 【详解】如图所示： 所以共16种方法。 【点睛】对于这种标数法求最短路径的问题，最关键的是确定标数的方向。 5．如图，用水平线或竖直线连结相邻汉字，沿着这些线读下去，正好可以读成“祖国明天更美好”，那么可读成“祖国明天更美好”的路线有( )条。 【答案】127 【分析】必须按照“祖国明天更美好”往下读，典型的标数问题，按照祖→国→明→天→更→美→好的顺序进行标数即可。 【详解】如图所示： 所以可读成“祖国明天更美好”的路线有127条。 【点睛】本题考查的是标数法求解最短路径的问题，在标数的时候注意顺序。 6．如图为一幅街道图，从出发经过十字路口，但不经过走到的不同的最短路线有( )条。 【答案】18 【分析】先从A标数到B，然后再从B标数到D，其中C处标0，整个过程，只有向上、向右是允许的。 【详解】如图所示： 所以最短路径有条。 【点睛】在标数法问题中，如果一个点不能经过，那么这个点标0即可。 7．如图，某城市的街道由5条东西向马路和7条南北向马路组成，现在要从西南角的处沿最短的路线走到东北角出，由于修路，十字路口不能通过，那么共有( )种不同走法。 【答案】120 【分析】求从A到B的最短路线的数量，顺序判断方向，向上、向右是允许的，另外两个方向是不允许的，从A开始依次标数，C处标0。 【详解】如图所示： 所以共有120种不同走法。 【点睛】本题也可采用排除法，由于不能经过C，可以先计算出从A到C的最短路线有多少条，再去掉其中那些经过C的路线数，即得到所求的结果。 8．有6个木箱，编号为1，2，3，…，6，每个箱子有一把钥匙，6把钥匙各不相同，每个箱子放进一把钥匙锁好。先挖开1，2号箱子，可以取出钥匙去开箱子上的锁，如果最终能把6把锁都打开，则说这是一种放钥匙的“好”的方法，那么“好”的方法共有( )种。 【答案】240 【分析】直接考虑6个木箱的情况是比较麻烦的，可以先考虑2个木箱、3个木箱的情况，找出规律，然后应用规律求解。 【详解】设第1，2，3，…，6号箱子中所放的钥匙号码依次为，，，…，。当箱子数为（）时，好的放法的总数为。 当时，显然（，或，）。 当时，显然，否则第3个箱子打不开，从而或，如果，则把1号箱子和3号箱子看作一个整体，这样还是锁着1，2两号钥匙，撬开1，2两号箱子，那么方法有种；当也是如此。于是时的每一种情况对应或时的一种情况，这样就有。 当时，也一定有，否则第个箱子打不开，从而、、…、中有一个为，不论其中哪一个是，由于必须要把该箱子打开才能打开号箱子，所以可以将锁着这把钥匙的箱子与第号箱子看作1个箱子，于是还是锁着、、…、这把钥匙，需要撬开1，2两号箱子，所以每种情况都有种。所以。 所以， 所以好的方法总数为240种。 【点睛】本题考查的是归纳递推计数问题，归纳法是数学中常用的方法之一，归纳法的关键是找出规律或总结出通项公式。 9．设、为正八边形的相对顶点，顶点处有一只青蛙，除顶点外青蛙可以从正八边形的任一顶点跳到其相邻两个顶点中任意一个，落到顶点时青蛙就停止跳动，则青蛙从顶点出发恰好跳次后落到的方法总数为( )种。 【答案】 【分析】如图，如果跳到A、B、C、E、G、H点，那么上一步都有2种可能，如果跳到D、F点，那么上一步都有1种可能，落到E，那么上一步在D、F点，用列表法进行递推计数。 【详解】如图所示： 可以使用递推法。 回到 跳到或 跳到或 跳到或 停在 1步 1 2步 2 1 3步 3 1 4步 6 4 2 5步 10 4 6步 20 14 8 7步 34 14 8步 68 48 28 9步 116 48 其中，第一列的每一个数都等于它的上一行的第二列的数的2倍，第二列的每一个数都等于它的上一行的第一列和第三列的两个数的和，第三列的每一个数都等于它的上一行的第二列和第四列的两个数的和，第四列的每一个数都等于它的上一行的第三列的数，第五列的每一个数都等于都等于它的上一行的第四列的数的2倍。这一规律很容易根据青蛙的跳动规则分析得来。 所以，青蛙第10步跳到有种方法。 【点睛】本题考查的是归纳递推计数问题，采用列表法进行分析，简单明了。 10．在下图的街道示意图中，C处因施工不能通行，从A到B的最短路线有多少条？ 【答案】6条 【分析】因为B在A的右上方，从A到B的最短路径上，到达任何一点的走法数都等于到它左侧点的走法数与到它下侧点的走法数之和。而C是一个特殊的点，因为不能通行，所以不可能有路线经过 ，可以认为到达C点的走法数是0，接下来，可以从左下角开始，依次标数即可。 【详解】如图所示： 答：从A到B的最短路径有6条。 【点睛】本题考查的是不规则图形的标数问题，注意不允许通过的地方标0即可。 11．在下图中，用水平或者垂直的线段连接相邻的字母，当沿着这些线段行走是，正好拼出“APPLE”的路线共有多少条？ 【答案】31条 【分析】要想拼出英语“APPLE”的单词，必须按照“A→P→P→L→E”的次序拼写。在图中的每一种拼写方式都对应着一条最短路径。 【详解】如图所示： 答：正好拼出“APPLE”的路线共有31种不同的路径。 【点睛】本题考查的是标数法求最短路径的问题，顺序要明确标数的顺序，然后依次进行标数即可。 12．图中有10个编好号码的房间，你可以从小号码房间走到相邻的大号码房间，但不能从大号码走到小号码，从1号房间走到10号房间共有多少种不同的走法？ 【答案】22种 【解析】因为不能从大号码走到小号码，所以只有向下、向左下方、向右下方是允许的，从“1”开始进行标数。 【详解】如图所示： 答：从1号房间走到10号房间共有22种不同的走法。 【点睛】本题考查的是标数法求最短路线的问题，标数法其实是归纳递推计数的一种。 13．如下图，一只蜜蜂从处出发，回到家里处，每次只能从一个蜂房爬向右侧邻近的蜂房而不准逆行，共有多少种回家的方法？ 【答案】种 【分析】蜜蜂“每次只能从一个蜂房爬向右侧邻近的蜂房而不准逆行”这意味着它只能从小号码的蜂房爬近相邻大号码的蜂房。明确了行走路径的方向，就可以运用标数法进行计算。 【详解】如图所示： 小蜜蜂从A出发到B处共有89种不同的回家方法； 答：共有89种回家的方法。 【点睛】可以发现，这种问题也是基于类斐波那契数列的，当然也属于归纳递推计数问题。 二、对应法计数 1．如图，其中同时包括两个☆的长方形有( )个。 【答案】24 【分析】分别数出上边☆的左上角的格点个数，以及下边的☆右下角的格点个数，从左上角选一个点，右下角选一个点，构成的长方形一定同时包括两个☆。 【详解】（个） 同时包括两个☆的长方形有24个。 【点睛】本题考查的是几何计数问题，这种方法我们称为“鼠标法”，是对应法计数中的一种。 2．学学和思思一起洗个互不相同的碗（顺序固定），思思洗好的碗一个一个往上摞，学学再从最上面一个一个地拿走放入碗柜摞成一摞，思思一边洗，学学一边拿，问学学摞好的碗一共有( )种不同的摞法。 【答案】 【分析】只有当思思把洗好的碗摞好之后，学学才能把摞好的碗拿走放入碗柜摞成一摞，所以如果将思思洗碗的顺序将这4个碗依次标号为1、2、3、4，那么必须是思思洗好的碗才可以被学学拿走，对顺序是有要求的。 【详解】按思思洗碗的顺序将这个碗依次标号为、、、，则学学摞好的碗有下列不同的摆法：，，，，，，，，，，，，，。 所以学学摞好的碗一共有14种不同的摞法。 【点睛】本题考查的是计数问题，也可以采用阶梯型标数法进行求解。 3．由20个边长为1的小正方形拼成一个长方形中有一格有“☆”图中含有“☆”的所有长方形（含正方形）共有 个，它们的面积总和是 。 ☆ 【答案】 48 360 【分析】如图，首先确定含☆的一行内所有可能的长方形有几种，以及含☆的一列内所有可能的长方形有几种，二者相乘，得到含☆的长方形个数；计算面积时，可以先保证长方形的长不变，求出每一种情况下的长方形面积之和，最后相加得到所有长方形的面积和。 【详解】含☆的一行内所有可能的长方形有：（八种） 含☆的一列内所有可能的长方形有：（六种） 所以总共长方形有个，面积总和为 【点睛】数含☆的长方形的个数时，可以根据其左上角有6个格点，右下角有8个格点来确定。 4．数3可以用4种方法表示为一个或几个正整数的和，如3，，，。问：1999表示为一个或几个正整数的和的方法有多少种？ 【答案】种 【分析】对于数3，上述4种和的表达方法对应：1 1 1，1＋1 1，1 1＋1，1＋1＋1；相当于是2个空隙，每个空隙要么填＋，要么不填，2种选法，可以按照乘法原理来理解。 【详解】我们将1999个1写成一行，它们之间留有1998个空隙，在这些空隙处，或者什么都不填，或者填上“＋”号，有2种可能； 因此1999可以表示为正整数之和的不同方法有种。 答：1999表示为一个或几个正整数的和的方法有种。 【点睛】本题考查的是计数问题，也可以多写几个数，然后从中找出规律，再应用规律求解问题。 5．圆周上有12个点，其中一个点涂红，还有一个点涂了蓝色，其余10个点没有涂色，以这些点为顶点的凸多边形中，其顶点包含了红点及蓝点的多边形称为双色多边形；只包含红点（蓝点）的多边形称为红色（蓝色）多边形。不包含红点及蓝点的称无色多边形。试问，以这12个点为顶点的所有凸多边形（边数可以从三角形到12边形）中，双色多边形的个数与无色多边形的个数，哪一种较多？多多少个？ 【答案】双色多边形；55个 【分析】从任意一个双色的N边形出发（ N≥5时），在去掉这个双色多边形中的红色顶点与蓝色顶点后，将得到一个无色的N－2边形；另一方面，对于一个任意的无色的M边形，如果加上红色顶点和蓝色顶点，就得到一个双色的M＋2边形，所以无色多边形与双色多边形中的五边形以上的图形是一一对应的关系，所以双色多边形的个数比较多，多的是双色三角形和双色四边形的个数。 【详解】除红、蓝点之外，再取一个点构成三角形，有10种方法，所以双色三角形有10个； 双色四边形有个，所以双色多边形比无色多边形多个。 答：双色多边形更多一些；多55个。 【点睛】本题考查的是对应法计数问题，解题的关键是找出双色多边形的个数与无色多边形个数的对应关系。 6．用1元，2元，5元，10元四种面值的纸币若干张（不一定要求每种都有），组成99元有 种方法，组成101元有种方法，则( )。 【答案】 【分析】由于，组成99元的方法与组成101元的某些方法存在一一对应的关系，剩下的都是不包含2元纸币的组成方法，所以Q比P多的就是用1元、5元、10元这三种面值的纸币组成101元方法总数． 【详解】解：设1元x张，5元y张，10元 z张； ， ，对于每一个 z，y可以有种可能，相应的 5元纸币就有种取法； 如果元的取张，即，则，即元的有种取法； 如果元的取张，即，则，即元的有种取法； 如果元的取张，即，则，即元的有种取法； 如果元的取张，即，则，即元的有种取法； 所以总数为，那么。 所以Q－P＝121。 【点睛】本题考查的是对应法计数问题，关键是找出Q和P的对应关系。 7．有一类各位数字各不相同的五位数，它的千位数字比左右两个数字大，十位数字也比左右两位数字大。另有一类各位数字各不相同的五位数，它的千位数字比左右两个数字小，十位数字也比左右两位数字小。请问符合要求的数与，哪一类的个数多？多多少？ 【答案】W多；多个 【分析】对比发现，五位数M和五位数W各个数位上数字的关系恰好是相反的，那么二者就存在一定的对应关系，可以从这一点入手求解问题。 【详解】与都是五位数，都有千位和十位与其它数位的大小关系，所以两类数有一定的对应关系。比如有一个符合要求的五位数（不为0），那么就有一个与之相反并对应的五位数，比如为类，则与之对应的为类。 所以对于类的每一个数，类都有一个数与之对应。但是两类数的个数不是一样多，因为类中不能做首位，而类中9可以做首位。所以类的数比类的数要多，多的就是就是首位为的符合要求的数。 计算首位为的类的数的个数，首先要确定另外四个数，因为要求各不相同，从除9外的其它个数字中选出个，有种选法。 对于每一种选法选出来的4个数，假设其大小关系为，由于其中最小的数只能在千位和十位上，最大的数只能在百位和个位上，所以符合要求的数有类：①千位、十位排、，有两种方法，百位、十位排、，也有两种方法，故此时共有种；②千位、十位排、，只能是千位，百位，十位，个位，只有种方法。 根据乘法原理，首位为的类的数有个。 答：W多；多630个。 【点睛】本题考查的是对应法计数的问题，关键是找出五位数M和五位数W的对应关系，以及二者的不同点。 8．游乐园的门票1元1张，每人限购1张。现在有10个小朋友排队购票，其中5个小朋友只有1元的钞票，另外5个小朋友只有2元的钞票，售票员没有准备零钱。问有多少种排队方法，使售票员总能找得开零钱？ 【答案】种 【分析】与类似题目找对应关系。要保证售票员总能找得开零钱，必须保证每一位拿2元钱的小朋友前面的若干小朋友中，拿1元的要比拿2元的人数多，先将拿1元钱的小朋友看成是相同的，将拿2元钱的小朋友看成是相同的，可以利用斜直角三角模型。在下图中，每条小横线段代表1元钱的小朋友，每条小竖线段代表2元钱的小朋友，因为从A点沿格线走到B点，每次只能向右或向上走，无论到途中哪一点，只要不超过斜线，那么经过的小横线段都不少于小竖线段，所以本题相当于求下图中从A到BV有多少种不同走法。使用标数法，可求出从A到B有42种走法。然后再考虑小朋友不同所产生的影响。 【详解】如图所示： 但是由于10个小朋友互不相同，必须将他们排队，可以分成两步，第一步排拿2元的小朋友，5个人共有种排法；第二步排拿到1元的小朋友，也有120种排法，所以共有种排队方法。这样，使售票员能找得开零钱的排队方法共有（种）。 答：有604800种排队方法。 【点睛】本题将标数法计数与排列组合问题相结合，解题的关键在于转化，将题目与阶梯型标数法计数问题相结合。 9．如图，其中的每条线段都是水平的或竖直的，边界上各条线段的长度依次为5厘米、7厘米、9厘米、2厘米和4厘米、6厘米、5厘米、1厘米。求图中长方形的个数，以及所有长方形面积的和。 【答案】100个，10664平方厘米 【分析】确定好长方形的长和宽，长方形就唯一确定，而图中只需确定好横向线段，竖向线段即可，横向10条线段，竖向10条线段，总共可以构成100个长方形；可以保证长方形的长不变，求出不同的宽的长方形面积之和，然后相加得到总和。 【详解】横向线段有（1＋2＋3＋4）＝10种选法，竖向线段也有（1＋2＋3＋4）＝10种选法，则共有10×10＝100个长方形。 这些长方形的面积和为： （5＋7＋9＋2＋12＋16＋11＋21＋18＋23）×（4＋6＋5＋1＋10＋11＋6＋15＋12＋16） ＝124×86 ＝10664（平方厘米）。 【点睛】本题考查的是几何计数问题，对应法计数是数长方形个数最常用的方法。 10．将1～12这12个数填入到2行6列的方格表中，使得每行右边比左边的大，每一列上面比下面的大，共有多少种填法？ 【答案】种 【分析】要求每行右边比左边的大，可以用阶梯型标数法求解，水平方向表示右边的数，竖直方向表示左边的数。 【详解】如图所示： 答：共有132种填法。 【点睛】本题考查的是阶梯型标数法问题，考虑其与长方形标数法问题的不同之处。 11．在8×8的方格棋盘中，取出一个由三个小方格组成的“L”形（如图），一共有多少种不同的方法？    【答案】个 【分析】如图，在每一个2×2的正方形方格中可以找到4个目标图形，所以只需要数出8×8的方格中有多少个2×2的正方形即可。 【详解】如图所示： 7×7＝49（个） 一共可以找到49个2×2的正方形； 49×4＝196（种） 答：一共有196种不同的方法。 【点睛】通过上面两个范例我们知道，当直接去求一个集合元素的个数较为困难的时候，可考虑采用相等的原则，把问题转化成求另一个集合的元素个数。 试卷第1页，共3页 第 1 页 共 20 页 学科网（北京）股份有限公司 $