当前位置:首页 >> 学科竞赛 >> 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 递推关系 西安电子科技大学出版社 姜建国著 组合数学 第章习题答案西安...当然本数列可以不用特征根法求解, 当然本数列可以不用特征根法求解,直接由解递...

1、几类常见递推数列的解题方法(学生)

然后用数学归纳法证明;另一类是将已知递推关系,用代数法、迭代法、换元法, ...3 ,数列{ a n }满足 a 1 =1,a n = f (a n?1 ),求 a n . 3...

高三物理递推法解题

高三物理对称法解题 3页 免费 高考物理解题方法递推法方... 14页 免费 高中...×5 ∴ ?=190.5/(129×5)=0.3 6. 0.02J 0 13 第 10 页共 10 ...

三年级奥数第十二讲 递推法解题_教师版(A)

年级奥数第十二讲 递推法解题_教师版(A) 隐藏>> 杰睿学校 数学 VIP 教师 冯宝石 13121194356 第十二讲 逆推法解题(A 卷) 逆推法解题(年级 一、填空题 1...

高三物理递推法解题(修改版)

高三物理递推法解题(修改版)_理化生_高中教育_教育专区。高中物理解题方法专题指导...μG/64·(1+2+3+……+128)=129μ×5 ∴μ=190.5/(129×5)=0.3 ...

...数学考前3个月知识方法专题训练第22练常考的递推公...

通用版2017届高考数学考前3个月知识方法专题训练第22练常考的递推公式问题的...n n 点评 构造法就是利用数列的递推关系灵活变形,构造出等差、等比的新数列,...

三年级奥数4-倒推法解题

三年级奥数4-倒推法解题_三年级数学_数学_小学教育_教育专区。三年级上册奥数专题...三年级奥数之典型问题:... 3页 免费 三年级奥数:递推法解题... 暂无评价 ...

由递推公式求通项的9种方法经典总结

递推公式求通项的9种方法经典总结_数学_高中教育_教育专区。精析由递推公式...3 2 根据待定系数法,得 bn+1-3= (bn-3). 3 5 4 所以数列{bn-3}是...

BX110937李建辉实验三递推算法上交

3​7​李​建​辉​实​验​​递​推​算​法​...电子信息学院 实验报告书课 程名:题目: 算法设计与分析实验三 递推算法 【...
更多相关标签:
网站地图

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