当前位置:首页 >> 学科竞赛 >> 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 } 的坐标。


更多相关文档:

递推法解题

高三物理递推法解题 10页 1下载券 二轮复习-7递推法解题 10页 4下载券喜欢...报 3 的出列; 如此类推,第 I 次报 I+1 的出列,直至最后一个人出列...

高三物理递推法解题

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

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

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

递推法物理解题

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

递推法解题

递 推关系一般可以用归纳、猜想等途径获得。 利用递推法解题的一般步骤为:(1)确定初始值;(2)建立递推关系;(3)利用递推关系求 通项。 典例分析例 1.用 ...

递推法

浅谈递推法 5页 1财富值 递推法1 44页 2财富值 递推法的应用 3页 免费 递推法解题 3页 免费 用递推法解题 2页 免费 6.递推法 18页 2财富值 归纳...

习题3 递推关系

习题3 递推关系 西安电子科技大学出版社 姜建国著 组合数学 第章习题答案西安...当然本数列可以不用特征根法求解, 当然本数列可以不用特征根法求解,直接由解递...

2015年高考数学 解题技术(3)如何求递推数列的通项

2015年高考数学 解题技术(3)如何求递推数列的通项_数学_高中教育_教育专区。高考解题技术(3) 如何求递推数列的通项 1、代换法 【例 1】 (2010 年重庆理卷...

递推法

浅谈递推法 5页 1财富值 递推法1 44页 2财富值 递推法的应用 3页 免费 递推法解题 3页 免费 用递推法解题 2页 免费 6.递推法 18页 2财富值 归纳...

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

递推法解题方法和解题思维上的使用 东风七中叶飞对于信息学奥林匹克联赛的...摘下来就可以 按照此法对第位进行计算,如此往复就可以把一个二进制的数变成...
更多相关标签:
网站地图

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