3313小学、初中、高中各种试卷真题知识归纳文案合同PPT等免费下载www.doc985.com第三讲递推计数例题例1．答案：927详解：将作文数量与完成作文的方法数列成一张表格，如下所示：下面解释一下这张数表是如何累加得到的．写1、2、3篇作文的方法数可以枚举得到．写4篇作文的完成方法数可以分三类去数：如果第一天写1篇，那么参考数表可得，剩下3篇有4种完成方法；如果第一天写2篇，同样参考数表可得，剩下2篇有2种完成方法；如果第一天写3篇，那么剩下1篇还有1种完成方法——因此4篇作文的完成方法总数为，如上表箭头所示．接着分析5篇作文的完成方法数，仍然分三类：第一天写1篇，那么参考数表可得，剩下4篇还有7种完成方法；第一天写2篇，那么剩下3篇还有4种完成方法；第一天写3篇，那么剩下2篇还有2种完成方法——因此5篇作文的完成方法数等于……以此类推便可填满整张表格．例2．答案：28详解：我们同样可以列出一个递推数列，将其表示如下：下面详细说明该问题的递推规律．覆盖1×3、2×3和3×3方格表的方法数可以枚举得到．接着分析覆盖4×3的表格有几种覆盖方法．如下图所示，左上角的阴影方格在覆盖的时候有两种方法：竖着覆盖或横着覆盖．当竖着覆盖时，余下部分恰好是一个3×3的方格表，覆盖方法数为2；当横着覆盖时，其下方的方格只能被横放的纸片盖住，因此只剩下一个1×3的方格表需要覆盖，方法数为1．由此可得4×3表格的方法数为2+1=3．用同样的方法分析5×3的方格表，可得其覆盖方法数等于的方法数加上的方法数，因此等于．接着以此类推即可．例3．答案：5051详解：我们同样可以列出一个递推数列，将其写为如下的一张数表：2351004…第4条IIIIIIIVIIIIIIIV增加第n条直线1n第n条直线被分成n部分直线的每一部分都分出一个新区域增加n个新区域小学、初中、高中各种试卷真题知识归纳文案合同PPT等免费下载www.doc985.com下面详细说明该递推过程．平面上有1、2、3条直线的情形画图即可解决，我们从第4条直线开始分析．如右图所示，当画上第4条直线时，会把原有的区域一分为二（如编号为I、II、III、IV的4个区域），因此会增加4个新区域．而之所以能产生4个新区域，就是由于第4条直线会与原有的3条直线产生3个交点，而这3个交点会把第4条直线分为4部分，每一部分都会位于一个原有的区域中，因此每一部分都就会把原有的某个区域一分为二，因此直线被分为几部分，区域数量自然也就增加几部分．上述逻辑关系在下方右侧有明确的表示．由此可得，增加到第n条直线就会增加n个新区域，因此答案是．例4．答案：1641详解：本题的方法称为“传球法”．传球法在很多问题中有着广泛的应用．如右侧表格所示，除了第“0”行外，其余每一行的数量都是由上一行的数量通过某种规则累加得到的．比如第“1”行A下方的0，就是通过第“0”行B、C、D的数量相加得到的；第“3”行B下方的7，就是通过第“2”行A、C、D的数量相加得到的；第“4”行C下方的20，就是通过第“5”行A、B、D的数量相加得到的；第“6”行D下方的182，就是通过第“5”行A、B、C的数量相加得到的．之所以有这样的累加规则，就是因为A想拿球，必须由B、C、D传球给他，所以他下方的数也必须由B、C、D累加给他——这就是传球规则决定累加规则．依据这一累加规则，我们不停地将数表向下累加，每传一次球就多累加一行，最后得到第“8”行．这一行的四个数分别为1641、1640、1640和1640．他们分别表示8次传球后，由A、B、C、D拿球的传球方法数．由于题目要求最后球回到A手中，因此答案为1641种．例5．答案：1224详解：我们把这个七位数看作是1、2、3三个人之间传6次球的一个传球顺序，具体的传球规则是：1能传球给2、3，但不能给自己；2、3都能传球给1、2、3．依据“传球规则决定累加规则”，我们可以列出如右表所示的一张递推表格．表格的第“0”行是发球行，对应的是这个七位数的首位数字．由于1、2、3都能作首位，因此第“0”行写的都是1．接着按照传球规则累加即可．表格中第“6”行（最后一行）中A3A1A2A4A5A6A1A2A3A4A5A6A7A8还剩4个点，2种方法．1种方法．还剩4个点，2种方法．还剩6个点，共5种方法．2121...