网站位置: /论文/文献综述/写作范文资料阅读

方程方面毕业论文格式模板范文,与递归方程求解方法综述相关论文范文素材

全文下载

此文是一篇方程论文范文,方程方面论文范文素材,与递归方程求解方法综述相关本科论文开题报告。适合不知如何写方程及算法及函数方面的文献综述专业大学硕士和本科毕业论文以及方程类开题报告范文和职称论文的作为写作参考文献资料下载。

摘 要 :随着计算机科学的逐步发展,各种各样的算法相继出现,我们需要对算法进行分析,以选择性能更好的解决方案.算法分析中计算复杂度常用递归方程来表达,因此递归方程的求解有助于分析算法设计的好坏.阐述了常用的3种求解递归方程的方法:递推法、特征方程法和生成函数法.这3种方法基本上可以解决一般规模递归方程的求解问题.

关 键 词 :递归;递推法;特征方程;生成函数

中图分类号:TP301文献标识码:A文章编号:16727800(2011)012003902

作者简介:郭萌萌(1983- ),女,山东济南人,硕士,山东英才学院计算机电子信息工程学院讲师,研究方向为软件工程、算法分析与设计.

0引言

寻求好的解决方案是算法分析的主要目的,问题的解决方案可能不只一个,好的方案应该执行时间最短,同时占有存储空间最小,故算法分析一般考虑时间复杂性、空间复杂性两方面的参数.在算法分析时我们采用时间耗费函数来表示时间参数,用当问题规模充分大时的时间耗费函数的极限表示时间复杂度.

一般算法对应的时间耗费函数常用递归方程表示,找出递归方程的解,就可以表示其对应算法复杂度的渐进阶,从而比较算法的优劣.因此研究递归方程的解法意义重大.下文将分析并给出常用递归方程的3种解法.

1递归方程的解法

递归方程是对实际问题求解的一种数学抽象,递归的本质在于将原始问题逐步划分成具有相同解题规律的子问题来解决,原始问题与子问题仅在规模上有大小区别,并且子问题的规模比原始问题的规模要小.对于规模为n的原始问题,我们通常会寻找规模n的问题与规模n-1或者规模n/2的问题之间存在的联系,从而进一步推导出具有递归特性的运算模型.

递归方程求解方法综述参考属性评定
有关论文范文主题研究: 关于方程的论文范本 大学生适用: 高校毕业论文、函授论文
相关参考文献下载数量: 69 写作解决问题: 如何怎么撰写
毕业论文开题报告: 标准论文格式、论文选题 职称论文适用: 刊物发表、中级职称
所属大学生专业类别: 如何怎么撰写 论文题目推荐度: 优秀选题

根据递归方程的一般形式,常用的解法有三种,分别是递推法、公式法及生成函数法.下面就分别来分析其求解过程.

1.1递推法

当递归方程形式简单且阶数较低时,一般可以采用递推法求解,根据一步一步递推找到方程的递推规律,得到方程的解.下面举例说明: T(1)等于0

T(n)等于2T(n/2)+n2(n≥2)

T(n)等于2T(n/2)+n2等于2(2T(n/22)+(n/2)2)+n2

等于22T(n/2)2+2n2/22+n2

等于22(2T(n/23)+(n/22)2)+2n2/22+n2

等于23(2T(n/23)+22n2/(22)2)+2n2/(22)1+n2等

等于2kT(n/2k)+∑k-1i等于02in2(22)i递推到这里我们就可以发现递归规律,找到递归出口, T(1)等于0,令n等于2k 则可以得到如下结果:T(n) 等于2kT(1) +∑k-1i等于0n2(1/2)i)等于

n2(1-(1/2)k1-1/2)等于2n2-2n 上面得到方程的解,我们来分析其对应算法复杂性的渐进阶,根据渐进阶定理有:设有函数f(n),g(n)均是规模n的函数,则O(f(n))+O(g(n))等于O(max(f(n), g(n))).故有T(n)等于O(n2).

1.2公式法

对所需求解的递归方程进行观察,如果它是符合以下形式的常系数齐次线性方程,可用公式法求解.F(0)等于b0,

F(1)等于b1,等

F(k-1)等于bk-1,


怎么写方程硕士论文
播放:33653次 评论:6583人

F(n)等于a1F(n-1)+a2F(n-2)+等+akF(n-k) 在此,常系数是指a1 、a2、等ak是常数,线性指所有的F均为一次幂,齐次指无常数项.

解这类方程,可由F(n)项得出:F (n)-a1F(n-1)-a2F(n-2)-等

-akF(n-k) 等于0,寻找形如F(n)等于 xn的解.

令xn-a1xn-1-a2xn-2-等-akxn-k等于0;xn-k(xk-a1xk-1-等-ak) 等于0;即xk-a1xk-1-等-ak 等于0;

由此,我们得到了这类递归方程的特征方程,它有n个特征根,设为x1,x2,等,xk;其线性组合是F(n)的通解.即c1x1n+c2x2n+等+ckxkn等于F(n);其中c1,c2,等,ck可由k个初始条件得到的线性方程组解出.

例如,常系数齐次线性方程组F(0)等于0,

F(1)等于1,

F(n)等于4F(n-2),(n>1) 令F(n)等于xn;则xn 等于4xn-2;

xn - 4xn-2等于0 ;

x2-4等于0; (特征方程)

x1等于2;x2等于-2;(特征根)

设有c1,c2使F (n) 等于c1x1n+c2x2n;

由初始条件 F(0) 等于c1x10+c2x20等于c1+c2等于0,F(1)等于c1x11+c2x21等于2c1-2c2等于1;即c1+c2等于0,

2c1-2c2等于1解得c1等于1/4;c2等于-1/4;

∴F(n)等于2n/4-(-2)n/4即为以上递归方程的解.

1.3生成函数法

第三种方法是利用生成函数的方法,即已知一个数列a0,a1,a2,等,an,定义它的生成函数为一个形式幂级数:F(x)等于a0+a1x1+a2x2+等+anxn+等

我们寻找an的代数式.有了生成函数F(x),无需知道a0,a1,a2,等,an 的各项就可以设法找出它的生成函数的解析式,再将其展开成一个幂级数,则xn项的系数即为要求得的an.

以汉诺(Hanoi)塔问题的递归方程为例:T(1)等于1,

T(n)等于2T(n-1)+1,(n≥2) 该序列的生成函数为:T(x)等于T(1)x+T(2)x2+T(3)x3+等+T(n)xn+等(1)下面求T(n)的解析式.

由递归方程可得:T(2)-2T(1) 等于1,

T(3)-2T(2)等于1,

T(4)-2T(3)等于1,

T(n+1)-2T(n)等于1将(1)式×2x得:2xT(x)等于2T(1)x2+2T(2)x3+

2T(3)x4+等+2T(n)xn+1+等(2)(1)式-(2)式得,T(x) -2xT(x)等于 T(1)x+x2+x3+等+xn+等(1-2x)T(x)等于 x+x2+x3+等+xn+等

T(x)等于 等于 x1-x1-2x等于x(1-x)(1-2x)设T(x)等于A1-x+B1-2x等于A(1-2x)+B(1-x)(1-x)(1-2x)等于(A+B)-(2A+B)x(1-x)(1-2x)


该文 http://www.tjhyzyxy.com/wenxian/456247.html

应有x等于(A+B) - (2A+B)x

则A+B等于0,

2A+B等于-1解得A等于-1;B等于1

即T(x)等于-11-x+11-2x

用幂级数展开,得:T(x) 等于 (1+2x+22x2+23x3+...

+2nxn+...) - (1+x+x2+等+xn+等)

等于 (2-1) x+ (22-1) x2+ (23-1) x3+

等+ (2n-1) xn+等∴解出an等于2n-1;

在设定生成函数后,在求解解析式的过程中,需要消去中间的多余项,这就需要观察递归方程,上例中是采取了乘以一个系数相减的方法,在遇到具体问题时,可采取不同的方法, 比如移位、乘法、甚至求导,以求出要找的解析式.

2结束语

在算法设计中,很多问题可以采用递归解决.递归的引入往往使某些函数的定义和算法的描述更加清晰、明了.而且,递归对

关于递归方程求解方法综述的毕业论文格式模板范文
方程方面论文范文素材
于一些用非递归无法完全描述的复杂函数和过程也能清楚地进行表达.根据递归方程的解的形式可以评价一个算法的时间复杂度,从而可以直接判断算法的优劣,因此递归方程求解在算法设计中至关重要.本文给出了3种求解递归方程的方法,采用这些方法就可解决一般的递归方程,对于递归方程的学习有十分重要的指导意义.参考文献:

[1]胡章平,王瑞胡.算法时间复杂度分析中递归方程求解方法综述[J].中国科技信息,2006(3).

[2]高见元.递归方程的分析[J].中国高新技术企业 2007(13).

[3]武继刚.关于递归方程T(n)等于a[1].T(n/c)+d(n)的一般解[J].兰州大学学报(自然科学版),1989(4).

[4]孙红丽,叶斌.浅析递归方程解法及其渐进阶表示[J].四川文理学院学报(自然科学版),2007(2).

[5]王晓东.计算计算法设计与分析[M].北京:清华大学出版社,2008.

(责任编辑:杜能钢)


基于结构方程模型的行为贝塔分解

基于结构方程模型的商业银行竞争力

智力资本与民营企业治理绩效的实证

三维预成型体渗透率的数值模拟

运河区域城市史综述

宅基地流转意愿综述总结

结构方程论文
结构职称论文烟台 学位论文应选题恰当论据可靠论述有序,结构合理,语言规范,并具有一定的独特见解.,学位论文应采用英语撰写篇幅为5000词左右如文,译文过多则词数须相应增加.,学生。

论文方法
.,教育硕士专。开题报告的研究方法论文题的理论和实际意义),2,国内外研究现状综述,3,研究内容,研究思路,研究方法,4,研究重点,难点与创新点,5,论文总体计划和进度安排,。

论文综述
论文综述例文小学××××××××××××××撰写时间201602送审论文专业石油炼制催化剂取得高级任职资格以来近五年的专业技术工作业绩综述(限300字以内),注意事项,1.本栏。

论文的综述
论文综述例文小学××××××××××××××撰写时间201602送审论文专业石油炼制催化剂取得高级任职资格以来近五年的专业技术工作业绩综述(限300字以内),注意事项,1.本栏。

综述论文
有关文献综述的论文阅读关于上交开题报告,外文资料翻译,文献综述的通知,根据《2016届本科毕业设计(论文)工作计划》,毕业设计(论文)工作已进行到调研阶段,请同学们于2016年1。

论文发表方法
i,zhangshouhong.altitudemeasurementbasedo。毕业论文撰写方法及基本要求.也可以利用网络查阅相关资料.,文献综述实际上是对相关研究成果的简要介绍,包括作者,发表时间,论文或者书籍题目,主。

发表论文的方法
i,zhangshouhong.altitudemeasurementbasedo。毕业论文撰写方法及基本要求.也可以利用网络查阅相关资料.,文献综述实际上是对相关研究成果的简要介绍,包括作者,发表时间,论文或者书籍题目,主。

硕士论文方法
题的理论和实际意义),2,国内外研究现状综述,3,研究内容,研究思路,研究方法,4,研究重点,难点与创新点,5,论文总体计划和进度安排, 。硕士研究生学位论文格式规范,硕士研究生论文库中。

硕士论文研究方法
文之研读,了解财金实证方法与程序,(3)衍生出相关硕士论文研究课题. 。开题报告的研究方法论文题的理论和实际意义),2,国内外研究现状综述,3,研究内容,研究思路,研究方法,4,研。

硕士论文的研究方法
文之研读,了解财金实证方法与程序,(3)衍生出相关硕士论文研究课题. 。开题报告的研究方法论文题的理论和实际意义),2,国内外研究现状综述,3,研究内容,研究思路,研究方法,4,研。

递归方程求解方法综述 Doc版本