资源描述
第十四讲 递推方法家庭是幼儿语言活动的重要环境，为了与家长配合做好幼儿阅读训练工作，孩子一入园就召开家长会，给家长提出早期抓好幼儿阅读的要求。我把幼儿在园里的阅读活动及阅读情况及时传递给家长，要求孩子回家向家长朗诵儿歌，表演故事。我和家长共同配合，一道训练，幼儿的阅读能力提高很快。 递推方法是人们从开始认识数量关系时就很自然地产生的一种推理思想.例如自然数中最小的数是1，比1大1的数是2，接下来比2大1的数是3，由此得到了自然数数列：1，2，3，4，5，.在这里实际上就有了一个递推公式，假设第n个数为an，则唐宋或更早之前，针对“经学”“律学”“算学”和“书学”各科目，其相应传授者称为“博士”，这与当今“博士”含义已经相去甚远。而对那些特别讲授“武事”或讲解“经籍”者，又称“讲师”。“教授”和“助教”均原为学官称谓。前者始于宋，乃“宗学”“律学”“医学”“武学”等科目的讲授者；而后者则于西晋武帝时代即已设立了，主要协助国子、博士培养生徒。“助教”在古代不仅要作入流的学问，其教书育人的职责也十分明晰。唐代国子学、太学等所设之“助教”一席，也是当朝打眼的学官。至明清两代，只设国子监（国子学）一科的“助教”，其身价不谓显赫，也称得上朝廷要员。至此，无论是“博士”“讲师”，还是“教授”“助教”，其今日教师应具有的基本概念都具有了。 an+1=an+1课本、报刊杂志中的成语、名言警句等俯首皆是,但学生写作文运用到文章中的甚少,即使运用也很难做到恰如其分。为什么?还是没有彻底“记死”的缘故。要解决这个问题,方法很简单,每天花3-5分钟左右的时间记一条成语、一则名言警句即可。可以写在后黑板的“积累专栏”上每日一换,可以在每天课前的3分钟让学生轮流讲解,也可让学生个人搜集,每天往笔记本上抄写,教师定期检查等等。这样,一年就可记300多条成语、300多则名言警句,日积月累,终究会成为一笔不小的财富。这些成语典故“贮藏”在学生脑中,自然会出口成章,写作时便会随心所欲地“提取”出来,使文章增色添辉。 即由自然数中第n个数加上1，就是第n+1个数。由此可得an2=an11，这样就可以得到自然数数列中任何一个数再看一个例子：例1 平面上5条直线最多能把圆的内部分成几部分？平面上100条直线最多能把圆的内部分成几部分？解：假设用ak表示k条直线最多能把圆的内部分成的部分数.这里k0，1，2，.如图可见。a01a1=a0+12a2=a12=4a3=a23=7a4=a3+411归纳出递推公式an1an+n. （1）即画第n1条直线时，最多增加n部分.原因是这样的：第一条直线最多把圆分成两部分，故a12.当画第二条直线时要想把圆内部分割的部分尽可能多，就应和第一条直线在圆内相交，交点把第二条直线在圆内部分分成两条线段，而每条线段又把原来的一个区域划分成两个区域，因而增加的区域数是2，正好等于第二条直线的序号.同理，当画第三条直线时，要想把圆内部分割的部分数尽可能多，它就应和前两条直线在圆内各有一个交点.两个交点把第三条线在圆内部分成三条线段.而每条线段又把原来一个区域划分成两个区域.因而增加的区域部分数是3，正好等于第三条直线的序号，.这个道理适用于任意多条直线的情形.所以递推公式（1）是正确的.这样就易求得5条直线最多把圆内分成：a5=a4+511=516（部分）。要想求出100条直线最多能把圆内分成多少区域，不能直接用上面公式了，可把上面的递推公式变形：an=an-1+n=nn-2（n-1）n=an-3+（n-2）（n-n）+n公式（2）也称为数列1，2，4，7，11，16，的通项公式.一般来说，如果一个与自然数有关的数列中的任一项an可以由它前面的k（n-1）项经过运算或其他方法表示出来，我们就称相邻项之间有递归关系，并称这个数列为递归数列.如果这种推算方法能用公式表示出来，就称这种公式为递推公式或递推关系式.通过寻求递归关系来解决问题的方法就称为递推方法.许多与自然数有关的数学问题都常常具有递推关系，可以用递推公式来表达它的数量关系.如何寻求这个递推公式是解决这类问题的关键之一，常用的方法是“退”到问题最简单情况开始观察.逐步归纳并猜想一般的速推公式.在小学生阶段，我们仅要求学生能拨开问题的一些表面现象由简到繁地归纳出问题的递推公式就行了，不要求严格证明.当然能证明更好.所谓证明，就是要严格推出你建立的关系式适合所有的n，有时，仅仅在前面几项成立的关系式，不一定当n较大时也成立。例2 平面上10个两两相交的圆最多能将平面分割成多少个区域？平面上1993个圆最多能将平面分割成多少个区域？解：设平面上k个圆最多能将平面分割成ak部分.我们先“退”到最简单的情形.如图可见a1=2，a2=4221，a38=422，a4=14=8+23，an=an-1+2（n-1）.（3）（3）是这个问题的递推公式.再把它变形为当n较大时也能方便求出结果的公式：anan-1+2（n-1）an-2+2（n-2）+（n-1）an-32（n-3）+（n-2）+（n-1）=a1+2（1+2+3+n-2+n-1）a10=102-10+2=92（个），a1993=19932-19932=3970058（个）。关于这个递推公式成立的正确性分析与例1完全类似.比如，第一个圆显然将平面分为两个区域；当画第二个圆时，应与原来的一个圆有两个交点，即被第一个圆截成两段弧，而每一段弧将原来的每一个区域分成两个区域，故区域数增加了2，即增加了原来圆的个数的2倍；当画第三个圆时，应与原来的两个圆共有4个交点，圆弧被截成4段，而每段弧又将原来的每个区域分成两个区域，所以区域增加了4，即原来圆的个数的2倍，同理类推，说明递推公式应该是an=an-1+2（n-1）。例3在一个圆周上按下面规则标上一些数:第一次先把圆周二等分三次把4段圆弧分别二等分，并在4个分点旁边标上两个相邻分点旁所去，当第八次标完数以后，圆周上所有已标的数的和是多少？解：解：我们一般地设第一次所标的两数分别为a、b，用Sk表示第k次标完后各分点所标数的和.如图可见S1ab，S2S1+2S13S13（ab）。原因是这样的：S2是两类分点旁的标数和，一类是原来分点所标数的和S1，另一类是新增分点所标数的和，它正好是由原来各分点所标的数向左加一次，又向右加一次的和，故新增分点旁所标数的和恰好是原来所有数之和的2倍2S1，因此有S2=S12S1=3S1，同理类推S3=S2+2S23S2=32S1，S432S1232S132S1，Sn=3n-1S1=3n-1（ab） （4）（4）式为递推公式：Sn3Sn-1在S1=ab时已解出的表达式.所谓解出，即Sn直接依赖于n与S1而计算出.不再是Sn依赖于Sn-1，Sn-1又依赖于Sn-2这样的形式。例4 假设刚出生的雌雄一对小兔过两个月就能生下雌雄一对小兔，此后每月生下一对小兔.如果养了初生的一对小兔，问满一年时共可得多少对兔子？解：我们先退到开始的简单情况来推算，从中归纳出递推关系.如图：第一个月：只有1对小兔。第二个月：一对小兔长成一对大兔，但尚不会生殖.仍只有一对兔子。第三个月：这对大兔生了一对小兔，这时共2对兔子。第四个月：大兔又生了一对小兔，而上月出生的小兔正在长大，这时共3对兔子。第五个月：这时已有两对大兔可以生殖（原来的大兔和第三个月出生的小兔），于是生了两对小兔，这时共有5对兔子。把推算的结果列成一张表由表中可见满一年时可得144对兔子。如果要算的时间长，这种方法就有困难了，现在我们来找递推关系。用un表示第n个月时的兔子对数，则un：1，1，2，3，5，8，13，21，34，。容易发现递推公式是un=un-1+un-2。现在说明这个递推公式是正确的.因为第n个月时的兔子对分两类，一类是第n-1个月时的兔子对，另一类是当月新生的兔子对，而这些小兔对数恰好是第n-2个月时的兔子对数un-2。有了上面的递推公式就可以写出un的第12项为144对.这正是本题要求的满一年时的小兔总对数。数列un称为斐波那契数列（Fibonacci，11701250，是意大利数学家）.由于数列un具有许多重要的奇特性质.因而受到数学家们的极大关注，并把数列un取名为斐波那契数列.例5 传说在印度的佛教圣地贝拿勒斯圣庙里安放着个一个黄铜板，板上插着三根宝石针，在第一根宝石针上，从下到上穿着由大到小的64片中心有孔的金片.每天都有一个值班僧侣按下面规则移动金片：把金片从第一根宝石针移到其余的某根宝石针上.要求一次只能移动一片，而且小片永远要放在大片的上面.当时传说当64片金片都按上面的规则从第一根宝石针移到另一根宝石针上时，世界将在一声霹雳中毁灭.所以有人戏称这个问题叫“世界末日”问题（也称为“Hanoi塔”问题），当然，移金片和世界毁灭并无联系，这只是一个传说而已，但说明这是一个需要移动很多很多次才能办到的事情.解这个问题的方法在算法分析中也常用到.究竟按上述规则移动完成64片金片需要移动多少次呢？解：设有n片金片，把从第一片金片至第k片金片按题目要求由第I根宝石针移到另一根宝石针共需移动ak次。先对4片金片的简单情形用下列的几组图来表示移动过程中的各种状态，并计数，归纳出递归关系式。这节的前几个例子都是“退”到简单的特殊情况来归纳出一般规律.在这个例子里，我们将先用一般推理得出递推公式，再以n=64代入，便可解决我们这个例题.这种从一般到特殊来解决问题的方法也是数学上的一种常用方法。我们可以这样来想：为了移动第n片到第根宝石针上，我们必须先把它上面的n-1片按题目的规则采用某种程序移到第根宝石针上，这需要移动an-1次.然后才能把最下面第n片（最大的），称到第根宝石针上.最后再经过an-1次才能把第根宝石针上的n-1片金片按上面规则采用同样程序移到第根宝石针上.因此把n片金片按题中的规则全部移到另一根宝石针上共应移an=2an-1+1（次）. （5）这就是递推公式。为了求得n=64时a64的值，我们当然不能一次次地由a1=1，a2=3，a3=7，直到算出a64.现在我们设法把递推公式（5）变形为可以直接计算a64的形式。an=2an-1+1=2（2an-21）+1=22an-2+21=22（2an-3+1）+2+123an-322+21+12n-1a12n-2+2n-3+21=1222+2n-22n-1，an2an-an=2（1+2+22+2n-1）-（1+2+2n-1）=2n-1，a64264-1。a64是一个非常大的数.如果按每移动一片次需一秒钟算，把64片金片从一根宝石针移到另一根宝石针上大约需要5800亿年。习题十四1. 请你根据下列各个数之间的关系，在括号里填上恰当的数：1，5，9，13，17，（ ）。0.625，1.25，2.5，5，（ ）。198，297，396，495，（ ），（ ）。2.将自然数1，2，3，按图排列，在“2”处转第一个弯，“3”处转第二个弯，“5”处转第三个弯，.问哪个数处转第二十个弯？3.请用速推方法求出甲、乙、丙、丁四人站成一排照相，共有多少种不同站法？4.上一段12级楼梯，规定每一步只能上一级或两级.问要登上第12级楼梯共有多少种不同走法？5. 有10个村庄，分别用A1，A2，A10表示，某人从A1出发按箭头方向绕一圈最后经由A10再回到A1，有多少种不同走法？注：每点（村）至多过一次，两村之间，可走直线，也可走圆周上弧线，但都必须按箭头方向走.第 7 页
展开阅读全文