[精品]浅谈递推法

《[精品]浅谈递推法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、浅谈递推法082i3ml002邢莉英摘要：本文是阐述简单的递推法概念应用方法。递推法是根据具体问题，建立递推关系，在通过递推关系求解的方法。其中递推关系是表示关于正整数参变量的一类特殊关系，它从给定的初值出发，通过这种关系一步一步地通过递推获得所需结果。并给出用递推法解题的一-般过程。关键词：递推法；类型；应用我们在大学的生活已经过去三年来，学习了很多专业知识，数形结合，换元法，构造法，交集法，递推法，数学归纳法等等。在这里就简单说说递推法。一、递推法那么什么是递推法呢？递推法是根据具体问题，建

2、立递推关系，在通过递推关系求解的方法。其中递推关系是表示关于正整数参变量的一类特姝关系，它从给定的初值出发，通过这种关系-•步一-步地通过递推获得所需结果。递推法的步骤是:：1)按次序研究集合中最初授原始的若干个问题。2)按次序寻求集合中问题间的转换规律即递推关系，使问题逐次转化成较低级层次或简单的且能解决问题的或己解决的问题。我们在中学的时候学过与递推法相近的数学归纳法，那么他们有什么区别呢。对于一个可数的无穷命题集，数学归纳法的第一部是以证明集合屮第一个命题成立作为基础；第二步就是假设集合中

3、的笫k个命题成立，推出笫k+1个命题成立，也就是证实存在递推关系。因此数学归纳法中有递推方法，但这又是两种不同的方法。数学归纳法是一种证实归纳猜想关系的方法；而递推方法是一种研究问题的探索方法，也就是研究是否能递推？如何递推？而不仅仅是证实存在某种递推关系。二、递推法的类型及递推关系的建立递推方法是普及在数学各个领域中的，是探索和发现数学规律的重要方法z—。在中学教学中有很多方法可以用递推方法解决。我们來看一个典型的问题梵塔问题。梵塔问题起源于中东地区的一个古老的传说:在梵城(Harm)地下有一

4、个僧侣的秘密组织，他们冇3个大型的塔柱，左边的塔柱上由上到下套着64个金盘。僧侣们的工作就是把64个金盘从左边塔柱移到右边的塔柱上去。但转移的是冇规定的，1、每次只能搬动一只盘子，盘十只能在3个塔柱上安放，不允许放在地上；2、在每个塔柱上，只允许把小盘十叠在大盘上，反之不允许。据传说，僧侣们完成这个任务吋，世界的末FI就来临来。那么这个伟大的工程要多久才能完成呢，下面我们用递推法来研究下。解:设移动的次数记为f(n).从n=l开始分析,显然是需要一次，即f(l)=l；当n=2时，现将上面的一片小

5、金盘移到第二根塔柱上，移动次数为f(l),再将大的一边金盘移到第三根塔柱上，移动一次，再把第二个塔柱上的金盘取F套在第三根塔柱上，移动f(l)次，共移动2f(l)+l次，即f(2)二2f(1)+1；当n二3吋先将第一•根上而的两片按n=2的方法移动到第二根塔柱上，需移动f(2)次,在把最大的移动到第三个塔柱上，移动-次，再把第二根塔林上的移动到第三根上，需移动f(2)次,这样共移动f(3)二2f(2)+l；同理把第n-l片金盘移动到第二根塔柱上，共需移动f(n-l)次，再把第一个最下面的移到笫三

6、根上，需移动一次，授后把第二根的移动到第三根上这样共需要f(n)=2f(n-l)+l次,f(n)=2f(n-l)+l即为递推关系式。由f(l)=l与f(n)=2f(n-l)+l,可以推出f(n)的公式。事实上f(n)=2f(n-l)+l,而f(n)+l=2(f(nT)+l),令g(n)=f(n)+l,则g(n)=2g(n~l),经迭代后,可得g(n)=2g(n-1)=264-1=18446744073709551615o假设僧侣们个个身强力壮，每天24小时不知头疲倦地工作，而几一秒钟移动一个金盘

7、，那么，完成这个任务也得花5800亿年。这的确是出乎意料的。像这种解决问题也叫做单基递推法，是设问题U(n)是可以按顺序1,2,进行分析研究的，贝IJ,1,先研究第一级问题U(l)。2,在研究第n级问题U(n)A/n-1级问题U(n-l)的转化规律。在我们数学中的问题往往不是仅通过一个关系就可以表示出来的，往往需要多次的反复就会用到多基和串基的递推方法。三、常规的递推关系求解方法运用递推方法求解问题时，首先要建立递推关系试，但如何求解递推关系即求出通向，通常也是不可缺少的。求解递推关系方法很多，

8、例举归纳法，叠加法，累乘法，构造数列法等。,其中/2二2,3,…，试求/⑺)的解析解：因为/(I)故/⑵=(sin彳)2、，/(3)=(sin彳)2切方，可猜想f(n)=(sin彳尹戸芦"而彳丿3竹一1)=(sin彳尸［/(/i-l)p,jr—(1)猜想成立。假设n=k(k>2,keN)猜想成立，即/仗)=(sin—)32^,经证7T—(1+-=(sin—)233x2这就是根据列举归纳法在数学中应用的举例。下面我们来看看构造数列法证明不等式。所谓构造数列法，就是根据所证不等式的需要构造一个含何数