递推法解题.doc

递推法解题 基础知识 对于某些与自然数有关的问题，我们有时可以用递推法解决，扎谓用递推法解题，就是根据题目的特点，构造出递推关系解题的一种方法，解决问题的关键在于构造递推关系。递推关系一般可以用归纳、猜想等途径获得。 利用递推法解题的一般步骤为：(1)确定初始值；(2)建立递推关系；(3)利用递推关系求通项。 递推方法是人们从开始认识数量关系时就很自然地产生的一种推理思想.例如自然数中最小的数是1，比1大1的数是2，接下来比2大1的数是3，…由此得到了自然数数列：1，2，3，4，5，….在这里实际上就有了一个递推公式，假设第n个数为an，则an+1=an+1;　即由自然数中第n个数加上1，就是第n+1个数。由此可得　　an＋2=an＋1＋1，这样就可以得到自然数数列中任何一个数. 再看一个例子： 平面上5条直线最多能把圆的内部分成几部分？平面上100条直线最多能把圆的内部分成几部分？ 　　解：假设用ak表示k条直线最多能把圆的内部分成的部分数.这里k＝0，1，2，…. 　　a0＝1 　　a1=a0+1＝2 　a2=a1＋2=4 　　a3=a2＋3=7 　　a4=a3+4＝11 … 归纳出递推公式an＋1＝an+n. （1） 　　即画第n＋1条直线时，最多增加n部分.原因是这样的：第一条直线最多把圆分成两部分，故a1＝2.当画第二条直线时要想把圆内部分割的部分尽可能多，就应和第一条直线在圆内相交，交点把第二条直线在圆内部分分成两条线段，而每条线段又把原来的一个区域划分成两个区域，因而增加的区域数是2，正好等于第二条直线的序号.同理，当画第三条直线时，要想把圆内部分割的部分数尽可能多，它就应和前两条直线在圆内各有一个交点.两个交点把第三条线在圆内部分成三条线段.而每条线段又把原来一个区域划分成两个区域.因而增加的区域部分数是3，正好等于第三条直线的序号，….这个道理适用于任意多条直线的情形.所以递推公式（1）是正确的.这样就易求得5条直线最多把圆内分成： 　　a5=a4+5＝11=5＝16（部分）。 　　要想求出100条直线最多能把圆内分成多少区域，就去求通项公式。 一般来说，如果一个与自然数有关的数列中的任一项an可以由它前面的k（≤n-1）项经过运算或其他方法表示出来，我们就称相邻项之间有递归关系，并称这个数列为递归数列.如果这种推算方法能用公式表示出来，就称这种公式为递推公式或递推关系式.通过寻求递归关系来解决问题的方法就称为递推方法. 许多与自然数有关的数学问题都常常具有递推关系，可以用递推公式来表达它的数量关系.如何寻求这个递推公式是解决这类问题的关键之一，常用的方法是“退”到问题最简单情况开始观察.逐步归纳并猜想一般的速推公式.在小学生阶段，我们仅要求学生能拨开问题的一些表面现象由简到繁地归纳出问题的递推公式就行了，不要求严格证明.当然能证明更好.所谓证明，就是要严格推出你建立的关系式适合所有的n，有时，仅仅在前面几项成立的关系式，不一定当n较大时也成立。 1、 “河内塔问题” 传说在印度的佛教圣地贝拿勒斯圣庙里安放着个一个黄铜板，板上插着三根宝石针，在第一根宝石针上，从下到上穿着由大到小的64片中心有孔的金片.每天都有一个值班僧侣按下面规则移动金片：把金片从第一根宝石针移到其余的某根宝石针上.要求一次只能移动一片，而且小片永远要放在大片的上面.当时传说当64片金片都按上面的规则从第一根宝石针移到另一根宝石针上时，世界将在一声霹雳中毁灭.所以有人戏称这个问题叫“世界末日”问题（也称为“Hanoi塔”问题），当然，移金片和世界毁灭并无联系，这只是一个传说而已，但说明这是一个需要移动很多很多次才能办到的事情.解这个问题的方法在算法分析中也常用到.究竟按上述规则移动完成64片金片需要移动多少次呢？ 将此问题一般化为： 设有个银圈，大小不同，从大到小排列在三根金棒中的一根。这些银圈要搬到另一根金棒上，每次搬一个。第三根金棒作为银圈暂时摆放用。在搬动过程中，仍要保持大圈在下，小圈在上，问要搬动多少次，才能将所有银圈从一根棒搬到另一根，且搬完后银圈相对位置不变？ 思路：寻找与前面各项之间的关系，由题设条件列出等式。 解：令用表所求的搬动次数，把第一棒个银圈的个搬到第三棒，再将最大一个银圈搬到第二棒，然后又将第三棒上的个圈搬到第二棒上，如此继续，可完成这次搬动任务。 因为搬个银圈从一棒到另一棒需次，故可得递推式。 下面对递推式的求解。 最后，可得。 典例分析 例1．用100元人民币购买物品，规定每天只能用以下三种方式之一购买物品： (1)买甲物品1元；(2)买乙物品2元；(3)买丙物品2元 而且规定不允许不买物品。试问有多少种方式花完这100元钱？ 例2．有一种用硬币下棋的游戏，棋盘上标有第0站，