十四讲递推的方法

第14讲递推的方法一、知识要点和基本方法有时，我们会遇上一些具有规律性的数学问题，这就需要我们在解题时根据已知条件尽快地去发现规律，并利用这一规律去解决问题．例如：按规律填数：l，4，9，16，25，（），49，64．分析：要在括号内填上适当的数，就要正确判断出题目所呈现出的规律．若你仔细地观察这一数列，就会发现这些数之间的规律：（1）先考虑相邻两个数之间的差，依次是3，5，7，9，……，15；可以看到相邻两数的差从3开始呈现递增2的规律，所以括号里的数应是25＋11—36，再看36十13—49得到验证．（2）如果我们换一个角度去考虑，那么我们还可以发现，这数列的第一项是1的平方，第二项是2的平方，第三项是3的平方……从这些事实中，发现规律是第n项是n的平方．那么所求的是第六项是62＝36．我们把相邻数之间的关系称为递归关系，有了递归关系可以利用前面的数求出后面的未知数．像这种解题方法称为递推法．二、例题精讲例1109109999999999999个个的乘积中有多少个数字是奇数？分析我们可以从最简单的99的乘积中有几个奇数着手寻找规律。9×9=81，有1个奇数；99×99=99×（100－1）=9900－99=9801，有2个奇数；999×999=999×（1000－1）=999000－999=998001，有3个奇数；······从而可知，109109999999999999个个的乘积中共有10个数字是奇数．例2如图所示：线段AB上共有10个点（包括两个端点），那么这条线段上一共有多少条不同的线段？分析先从AB之间只有一个点开始，逐步增加AB之间的点数，找出点和线段之间的规律．我们可以采用列表的方法清楚地表示出点和线段数之间的规律．AB之间只有1个点：线段有1＋2＝3条．AB之间只有2个点：线段有1＋2＋3＝6条．AB之间只有3个点：线段有1＋2＋3＋4＝10条．AB之间只有3个点：线段有1＋2＋3＋4＋5＝15条．······不难发现，当AB之间有8个点时，线段有1＋2＋3＋4＋5＋6＋7＋8＋9＝45条．若再进一步研究可得出这样的规律，线段数=点数×（点数－1）÷2．例3计算333333333312345678910的值．分析这是一道特殊的计算题，当然我们可以采用分别求出每个数的立方是多少，再求和计算出这题的结果．这样的计算工作量比较大，是否可以采用其他较简便的方法计算呢？下面我们就来研究这个问题．2331212;2333123123;2333412341234;······这样我们可以容易地得到333333333312345678910＝（1＋2＋3＋4＋5＋6＋7＋8＋9＋10）2＝552＝3025通过这个例题我们可以得到23333123123nn例4将自然数按下面的规律分组：（1，2），（3，4，5，6），（7，8，9，10，11，12），（13，14，15，16，17，18，19，20），……，第1991组的第一个数和最后一个数各是几？分析仔细观察找出这些自然数分组的规律，再找出每一组的第一个数与该组的序数之间的关系．第1组的第1个数是：1＝（1－1）×1＋1；第2组的第1个数是：3＝（2－1）×2＋1；第3组的第1个数是；7＝（3－1）×3＋1；第4组的第1个数是：13＝（4－1）×4＋1；根据这一规律，可求出第1991组的第1个数是：（1991－1）×1991＋1＝3962091．第1992组的第一个数是：（1992－1）×1992＋1＝3966073．因此，第1991组的最后一个数是：3966073－l＝3966072．例5圆周上两个点将圆周分为两半，在这两点上写上数1；然后将两段半圆弧对分，在两个分点上写上相邻两点上的数之和；再把4段圆弧等分，在分点上写上相邻两点上的数之和（如图14－1），如此继续下去，问第6步后，圆周上所有点上的数之和是多少？分析先可以采用作图尝试寻找规律．第一步，圆周上有两个点，第二步有四个点，第三步有八个点，第四步有十六个点……第六步有32个点．图14-1因为问题是求圆周上所有数的和，所以我们不必去考虑每一步具体增加了哪些数，只须知道每一步增加数的总和是多少．第一步：圆周上有两个点，两个数的和是1＋1＝2；第二步：圆周上有四个点，四个数的和是1＋1＋2＋2＝6；增加数之和恰好是第一步圆周上所有数之和的2倍．第三步：圆周上有八个点，八个数的和是1＋1＋2＋2＋3＋3＋3＋3＝18，增加数之和恰好是第二步圆周上所有数之和的2倍．第四步：圆周上有十六个点，十六个数的和是1＋l＋2＋2＋3＋3＋3＋3＋4＋4＋4＋4＋5＋5＋5＋5＝54，增加数之和恰好是第三步圆周上所有数之和的2倍．……这样我们可以知道，圆周上所有数之和是前一步圆周上所有数之和的3倍．用递推法关系表示．设na为第n步后得出的圆周上所有数之和，则13nnaa利用上式可以得到123333333nnnnaaaa……1(1)3333na个因为1a=2，所以：61(61)3=333=32=486.aa（6-1）个例64个人进行篮球训练，相互传球接球，要求每个人接球后马上传给别人，开始由甲发球，并作为第一次传球，第五次传球后，球又回到甲手中，问有多少种传球方法？分析设第n次传球后，球又回到甲手中的传球方法有na种．可以想象前n－1次传球，如果每一次传球都任选其他三人中的一人进行传球，即每次传球都有3种可能，由乘法原理，共有-1(1)3333=3nn个（种）传球方法．这些传球方法并不是都符合要求的，它们可以分为两类，一类是第n－1次恰好传到甲手中，这有1na；种传法，它们不符合要求，因为这样第n次无法再把球传给甲；另一类是第n－1次传球，球不在甲手中，第n次持球人再将球传给甲，有na传法．根据加法原理，有-11(1)3333=3nnnnaa个由于甲是发球者，一次传球后球又回到甲手中的传球方法是不存在的，所以利用递推关系可以得到2a＝3－0＝3，3a＝3×3－3＝6，4a＝3×3×3－6＝21，5a＝3×3×3×3－21＝60．这说明经过5次传球后，球仍回到甲手中的传球方法有60种．当然这题也可以利用列表法求解．我们可以这样想，第n次传球后，球不在甲手中的传球方法，第n＋1次传球后球就可能回到甲手中，所以只需求出第四次传球后，球不在甲手中的传法共有多少种．第n次传球传球的方法球在甲手中的传球的方法球不在甲手中的传球的方法130329363276214812160524360183从表中可以看出经过五次传球后，球仍回到甲手中的传球方法共有60种．练习题A组1．根据各数间的关系，在括号内填上一个恰当的数．（1）1，2，6，24，（），72O；（2）1，2，4，7，11，16，（）．2．19991999的末位数字是几？3．八个自然数排成一行，从第三个数开始，每个数都等于它前面两个数的和．已知第一个数是3，第八个数是180，那么第二个数是几？3，，，，，，，1804．小红把平时节省下来的全部五分硬币先围成一个正三角形，正好用完，后来又改围成一个正方形，也正好用完．正方形每条边比三角形每条边少用5枚硬币．小红的五分硬币共价值多少元？5．平面上有8个圆，最多能把平面分成几部分？6．平面上有一条直线，把平面分成两部分，两条直线最多可把平面分成四部分，三条直线最多可把平面分成七部分，四条直线最多可把平面分成11部分，那么十条直线最多可把平面分成多少部分？7．1111251017、、、……按这样的规律排着一列数．请你找出它的规律，然后写出第1990个数．B组8．如图14-2所示，是一个街区的道路图．某人沿着箭头的方向行走一周，从A点出发后回到A点．问他一共有多少种不同的走法？图14-29．有甲乙两人进行汽车比赛，第一分钟内甲的速度为每秒66．米，乙的速度为每秒29．米．以后每分钟内的速度，甲总是前一分钟的两倍，乙总是前一分钟的三倍，出发后几分几秒乙追上甲？10．有100个人，第一位带有3元9角钱，第二位比第一位多1角，第三位比第二位多1角，……，以后每位总比前一位多一角．每人把自己所有的钱用来买练习本，练习本有两种，一种每本8角，一种每本5角．每人尽可能买5角一本的，这100人共买了多少本8角的练习本？11．有50名学生参加联欢会，第一个到会的女生同全部男生握过手，第二个到会的女生只差工个男生没握过手，第三个到会的女生只差两个男生没有握过手，……这样，最后一个女生与7个男生握过手，那么，50名学生中，男生有多少名？12．如图14－3，在2×2方格中，画一条直线最多可穿过3个方格，在3×3方格中，画一条直线最多可穿过5个方格．那么在10×10的方格中，画一条直线最多可穿过几个方格？图14－313．对于任意的两个自然数a和b，规定新运算“*”为：(1)(2)abaaa…(1)ab．如果323660x，那么x等于几？14．图14－4是按规律排列的三角形数阵，那么第1999行中左起第三个数是几？图14－4图14－515．如图14－5所示，在正六边形A周围画出6个同样的正六边形（阴影部分）围成第1圈；在第1圈外面再画出12个同样的正六边形，围成第2圈．按这个方法继续画下去，当画完第10圈时，图中共有多少个与A相同的正六边形？16．一个长方形把平面分成两部分，那么三个长方形最多能把平面分成几部分？17．假设刚出生的雌雄小兔过两个月就能生下一对小兔，此后每月生下一对小兔．如果养了初生的一对小兔，问满一年时共可得多少对兔子？测试题1．下列数是按一定规律排列的．3、8、15、24、35、48、63……，那么，它的第36个数是（）．2．图14－6中最上面的空格中应填（）．图14-63．八个数排成一排，从第三个数开始，每个数都等于他前面两个数之和．现用六张纸片盖住了其中的六个数，只露出第五个数是7，第八个数是30．那么被纸片盖住的第一个数是几？7304．一个人在三个城市A、B、C中游览．他今天在这个城市，明天就必须到另一个城市．这个人从A城出发，4天后还回到A城，那么这个人有多少种旅游路线？5．如图14－7，从A点到B点，最短路线共有多少条？图14-76．将一根绳子连续对折3次，然后每隔一定长度剪一刀，共剪了6刀．这样原来的绳子被剪成（）段．7．在一张四边形纸上共有10个点，如果把四边形的顶点算在一起测一共有14个点．已知这些点中的任意三个点都不在同一直线上．按照下面规定把这张纸片剪成一些三角形：（1）每个三角形的顶点都是这14个点中的3个；（2）每个三角形内都不再有这些点．那么，这张四边形的纸最多可以剪出（）个三角形．8．如图14－8：小正方形的边长是1厘米，依次作出下面图形．图14－8图上第一个图形的周长是10厘米，（1）36个正方形组成的图形周长是多少厘米？（2）周长是70厘米的图形，由多少个正方形组成？9．一辆客车沿11个站行走，每到一个站，上车的人中至少有一人到下一个站下车，那么这辆车至少要准备多少个座位？10．一个三位数，如果它的每一位数字都不小于另一个三位数对应数位上的数字，就称它“吃掉”后一个三位数，例如545吃掉432，543吃掉543，但是543不能吃掉534．那么能吃掉587的三位数共有多少个？11．1本书编上页码，如第8页需要1个数码，第109页需要3个数码等等，这样共需7825个数码，这本书共有多少页？12．五个人互相传球，由甲开始发球，并作为第一次传球，经过4次传球后，球仍回到甲手中．问：共有多少种传球方式？