第11讲递推法例题教师版.docVIP

知识导航 基本方法：从简单情况入手,探寻出规律,推广到复杂情况 问题分类：计算类递推 几何类递推 计数类递推 递推类计数的典型方法:传球法 例题精讲： 例1.已知44444444448888888889是两个相同自然数的乘积，这个自然数是________ 分析：49=7*7 4489=67*67 因此得解为6666666667 例2．（1）10条直线没有平行，每两条都有交点，但没有3条及以上的直线共点，即两两相交，则共有多少个交点？ （2）10条两两相交的直线，最多能把平面分成几个区域？ 分析与答： (1)直线为1,2,3,4,5 时交点数分别为 0,1,3,6,10，因此知道其规律，最终结论为45个交点！ （规律为n*（n-1）/2） （2）直线为1,2,3,4,5时平面数分别为2,4,7,11，因此知道其规律，知其最后答案为56（规律为1+n*（n+1）/2） 例3 平面上10个两两相交的圆，最多能把平面分成几个区域？ 分析与答：圆的个数为1,2,3,4,5时，平面的个数分别为2,4,8,14,22 (规律为An=An-1+2*(n-1)),因此答案为92 例4. 上一段11级的台阶，规定每一步只能上一级或者两级，那么登上第11级台阶有_____种不同的走法？ 分析与解答：上1级台阶有1种走法，上2级台阶有两种走法，上3级台阶 1+2=3种，上4级台阶有2+3=5中，我们发现是一个斐波那契数列，因此很容易求解答案为144！ 例5．将一根绳子连续对折4次， 然后每隔一定长度剪一刀，共剪了五刀，绳子剪成几段？ 分析与解答：对折一次，剪五刀：中间4*2，两头2+1=3段 对折两次，剪五刀：中间4*4，两头4+1=5段 对折三次，剪五刀，中间4*8，两头8+1=9段 对折四次，剪五刀：中间4*16，两头16+1=17段，因此答案为81段 例题6. 2000个学生排成一行，依次从左到右编上1～2000号，然后从右到左按一、二报数，报一的离开队伍，剩下的人继续按一、二报数，报一的人离开队伍，……按这个规律如此下去，直至当队伍只剩下一人为止。问：最后留下的这个人原来的号码是多少？ 分析与解答：我们通过前几次留在队伍中的学生的编号找出规律。 第一次留下的学生编号是：2，4，6，8，10，……； 都是2的倍数。即21的倍数； 第二次留下的学生编号是：4，8，12，16，20，……； 都是4的倍数，即22的倍数； 第一次留下的学生编号是：8，16，24，32，40，……；都是8的倍数。即23的倍数；…… 由于210=1024＜2000＜211=2048；这样可知，最后留下学生的号码一定是1024。 例题7. 圆周上两个点将圆周分为两半，在这两点上写上数1；然后将两段半圆弧对分，在两个分点上写上相邻两点上的数之和；再把4段圆弧等分，在分点上写上相邻两点上的数之和，如此继续下去，问第6步后，圆周上所有点上的之和是多少？ 分析与解答：先可以采用作图尝试寻找规律。 第一步，圆周上有两个点，第二步有四个点，第三步有八个点，第四步有十六个点，…，第六步有32个点。 因为问题是求圆周上所有数的和，所以我们不必去考虑每一步具体增加了哪些数，只须知道每一步增加数的总和是多少。 第一步：圆周上有两个点，两个数的和是1+1=2； 第二步：圆周上有四个点，四个数的和是1+1+2+2=6；增加数之和恰好是第一步圆周上所有数之和的2倍。 第三步：圆周上有八个点，八个数的和是1+1+2+2+3+3+3+3=18，增加数之和恰好是第二步数圆周上所有数之和的2倍。 第四步：圆周上有十六个点，十六个数的和是1+1+2+2+3+3+3+3+4+4+4+4+5+5+5+5=54，增加数之和恰好是第三步数圆周上所有数之和的2倍。…… 这样我们可以知道，圆周上所有数之和是前一步圆周上所有数之和的3倍。用递推法关系表示。 设an为第n步后得出的圆周上所有数之和，则an=3×an－1利用此式可以得到： an=3×an－1=3×3an－2=3×3×3an－3=……=3×3×……×3a1 因为a1=2，所以： an=3×3×……×3a1=3（6-1）×2=486。 例题8 4个人进行篮球训练，互相传球接球，要求每个人接球后马上传给别人，开始由甲发球，并作为第一次传球，第五次传球后，球又回到甲手中，问有多少种传球方式？ 分析与解答：设第n次传球后，球又回到甲手中的传球方式有an种。可以想象前n-1次传球，如果每一次传球都任选其他三人中的一人进行传球，即每次传球都有3种