当前位置:首页 >> 学科竞赛 >> 3.3递推法解题

3.3递推法解题


§3.3 递推法解题
基础知识
对于某些与自然数有关的问题,我们有时可以用递推法解决,扎谓用递推法解题,就是 根据题目的特点,构造出递推关系解题的一种方法,解决问题的关键在于构造递推关系。递 推关系一般可以用归纳、猜想等途径获得。 利用递推法解题的一般步骤为:(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 片金片需要移动多少次呢? 将此问题一般化为: 设有 n 个银圈,大小不同,从大到小排列在三根金棒中的一根。这些银圈要搬到另一根 金棒上, 每次搬一个。 第三根金棒作为银圈暂时摆放用。 在搬动过程中, 仍要保持大圈在下, 小圈在上,问要搬动多少次,才能将所有银圈从一根棒搬到另一根,且搬完后银圈相对位置 不变? 思路:寻找 an 与前面各项之间的关系,由题设条件列出等式。 解:令用 an 表所求的搬动次数,把第一棒 n 个银圈的 n ? 1 个搬到第三棒,再将最大一 个银圈搬到第二棒,然后又将第三棒上的 n ? 1 个圈搬到第二棒上,如此继续,可完成这次 搬动任务。 因为搬 n ? 1 个银圈从一棒到另一棒需 an ?1 次,故可得递推式 an ? 2an?1 ? 1, a1 ? 1 。 下面对递推式 an ? 2an?1 ? 1, a1 ? 1 的求解。 最后,可得 an ? 2n ? 1 。

典例分析
例 1.用 100 元人民币购买物品,规定每天只能用以下三种方式之一购买物品: (1)买甲物品 1 元;(2)买乙物品 2 元;(3)买丙物品 2 元 而且规定不允许不买物品。试问有多少种方式花完这 100 元钱?

例 2.有一种用硬币下棋的游戏,棋盘上标有第 0 站,第 1 站,第 2 站,??,第 100 站。 一枚棋子开始在第 0 站,棋手每掷一次硬币,棋子跳动一次:若掷出的是正面,棋子向前跳 两站,若掷出的是反面,则棋子向前跳一站,直到棋子恰好跳到第 99 站(胜利大本营)或第 100 站(失败大本营)时,游戏结束。如果硬币出现正反面的概率都是 利大本营与失败大本营的概率。

1 ,分别求棋子跳到胜 2

例 3.现有四个人做传球游戏,要求接球后马上传给别人。由甲先传球,并作为第 1 次传球, 求经过 10 次传球仍回到发球人甲手中的传球方式的种数。

例 4. (Bernoulli-Euler 装错信问题)某人写了 n 封信, 并在每个信封上写下了对应的地址和收 信人的姓名。问:将所有的信都错信封的情况共有多少种?

例 5.现将 n 边形的边依次记为 a1 , a2 ,?, an ,每条边都涂上红、黄、绿三种颜色中的一种, 要使相邻两边的颜色互不相同,有多少种不同的涂色方法?

例 6.(第五届西部竞赛题)已知 ? 2005 ? ? 2005 可以表示成 ? ? ? ,?? 为变元的二次多项式, 求这个多项式的系数之和。

例 7. 已知函数 f ( x) ? ( x ? 1) 2 , 数列 {an } 是公差为 d 等差数列, 数列 {bn } 为公比为 q(q ? 1) 的等比数列, a1 ? f (d ?1) ,a3 ? f (d ? 1) ;b1 ? f (q ? 1) ,b3 ? f (q ? 1) 。 且 设数列 {cn } 对于任意的正整数 n 都有

c c1 c2 c3 求 ? ? ? ? ? n ? an?1 成立, c1 ? c3 ? c5 ? ?? c2n?1 的值。 b1 b2 b3 bn

例 8.已知一列非零向量 an 满足:a1 ? ( x1 , y1 ) , an ? ( xn , yn ) ? (1)证明:{| an |}是等比数列; (2)求向量 a n ?1 与向量 an 的夹角;

?

?

?

1 ( xn?1 ? yn?1 , xn?1 ? yn?1 ) ( n ? 2 ) 2

?

?

?

(3)设向量 a1 ? (1,2) ,把 a1 , a2 ,??, an 中所有与 a1 共线的向量取出按原来的顺序排 成一列,组成一组新数列,记为: b1 , b2 ,??, bn ,求数列{ bn }的通项公式;若令

?

?

?

?

?

?

?

?

?

? ? ? OBn = b1 + b2 +?+ bn , O 为坐标原点,求点列 {Bn } 的坐标。


更多相关文档:

3.3递推法解题

§3.3 递推法解题基础知识对于某些与自然数有关的问题,我们有时可以用递推法解决,扎谓用递推法解题,就是 根据题目的特点,构造出递推关系解题的一种方法,解决...

三年级奥数专题:递推法解题习题及答案(A)

​年​级​奥​数​专​题​:​递​推​法​解​题...34 个. (3-1)×2=4(个) (4-1)×2=6(个) (6-1)×2=10(个) (...

习题3 递推关系

(3) ? (5) ? 解下列递推关系: 解下列递推关系: 题 ?a n ? 7a ...当然本数列可以不用特征根法求解, 当然本数列可以不用特征根法求解,直接由解递...

递推法物理解题

递推法物理解题_公务员考试_资格考试/认证_教育专区...t1 ? t 2 ? 3 2mL/ qE (3)由(3) (4)两...μ=190.5/(129×5)=0.3 0.02J 0 13 ...

高三物理递推法解题

高中物理解题方法专题指导 方法专题六:递推法解题 编辑 朱爱玲 主编 杨国兴 一....μG/64·(1+2+3+……+128)=129μ×5 ∴μ=190.5/(129×5)=0.3 6...

递推方法与解题之道(2015.4南安一中—陈俊鸿)

递推方法与解题之道 1 什么是递推法 如果数列 {an } 的第 n 项与它前...0 即可. 3.3 关于多维形式的递推 多维形式的递推跟上面介绍的一维形式和二维...

高中物理竞赛解题方法 六、递推法

高中物理竞赛解题方法 六、递推法_从业资格考试_资格考试/认证_教育专区。六、...以第 i 个薄片 AB 为研究对象,受力情况如图 6—3 甲所示,第 i 个 薄片...

小学五年级奥数递推法专题解析

象这种解题方法 称为递推法。 ◇例题解析◇ 例 1 999…999×999…999 的...2. 3. 4. 5. 6. 这列数规律是第 n 个数是(n+1) -1。所以第 36 ...

递推法在解题方法和解题思维上的使用东风七

递推法解题方法和解题思维上的使用 东风七中叶飞对于信息学奥林匹克联赛的...(4+3) mod 10)=1×7=7,要求最大值时,为((2+4+3) mod 10) ×(-1...
更多相关标签:
递推最小二乘法 | 递推法 | 递推最小二乘法原理 | 递推法和递归法 | 递推法和递归法的联系 | 递推平均滤波法 | 什么是递推法和递归法 | 什么是递推法 |
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com