计算机思维与算法课程论文.docx

****大学****学院《计算机思维与算法分析》课程论文计算机思维与算法之美学班部********级*************专业计算机科学与技术学姓号************名******计算机思维与算法之美摘要:本文通过参考相关文献,对递归算法和动态规划进行了较为全面的分析与解释,并且通过举一个实例进行代码实现演示,具体分析递归算法与动态规划分析,从中了解递归算法和动态规划问题。关键字:计算机思维,递归算法,动态规划分析,算法设计Abstract:Inthispaper,byreferencetorelevantliterature,prehensiveanalysisandinterpretation,andthroughcodeimplementsdemonstrationciteanexample,detailedanalysisofrecursivealgorithmanddynamicprogramminganalysis,,从中可以了解到算法设计的奥妙以及对数据结构中的数据存储结构更深层次的运用。计算机算法设计与分析是面向设计的、处于核心地位的一门学科。算法是一组有穷的规则,它规定了解决某一特定类型问题的一系列运算。算法设计是一件非常困难的工作,常用的算法设计方法有:分治法、贪心方法、动态规划、回溯法等。一、,直接或间接地调用自己的算法;递归算法是从下往上进行思维,需要对问题有全局的了解;在使用递归算法时,必须至少测试一个可以终止递归的条件,并且还必须对在合理的递归调用次数内未满足此类条件的情况进行处理,如果没有一个在正常情况下可以满足的条件,则过程将陷入执行无限循环的高度危险之中;递归算法的描述非常简洁而易于理解,但因重复计算和较大的堆栈消耗使递归算法的解题的运行效率较低;并不是所有的语言都支持递归,在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储,递归次数过多容易造成栈溢出等不利编程的因素,所以一般不提倡用递归算法设计程序。。在一个过程的运行期间调用另一个过程时,在执行被调用过程之前,系统要先把所有的实在参数返回地址等信息传递给被调用的过程保存,为被调用过程的局部变量分配存储空间,将控制转移到被调用入口。接下来从被调过程返回调用过程要保存被调用过程的计算结果,释放被调用过程的数据区,依照被调过程保存的返回地址将控制转移到调用过程。该过程服从后调用先返回的原则。,结构清晰,所编写的代码简洁精练,可读性好,有利于代码的维护。然而递归算法的效率却较低,占用较大的内存开销,消耗更多的系统堆栈,算法的空间复杂度大,故可以实现的深度是有限制的。而且要考虑函数或算法是否具备收敛性,当且仅当一个算法存在预期的收敛效果时,采用递归算法才是可行的,否则,就不能使用递归算法。,堆栈容易溢出的特点,递归算法适用于问题规模较小且那些不存在简明的数学模型以阐明问题的本质,或者存在数学模型,但是难于实现的问题,这样可以减少代码的复杂度。递归算法所适用的问题一般有这样的特征:为求解规模为N的问题,设法先将它分解为规模较小的子问题,然后从这些子问题的解构造出整个问题的解,并且这些子问题也能采用同样的分解和综合方法,分解成规模更小的子问题,并从这些更小的子问题的解构造出较大规模的问题的解,特别地,当规模N=1时,能直接得解。例如很多的数学函数是递归定义的(阶乘函数)、有的数据结构(广义表,二叉树)还有一类本身没有明显的递归结构但用递归求解更为简单的问题(汉诺塔问题,八皇后问题)。,对于某些递归关系可由逐级递推求得递归方程的解。递归算法会引起一系列的函数调用,并且可能会有一系列的重复计算,所以当某个递归算法能较方便地转化成递推算法时,通常按递推算法编写程序。递归算法的执行过程分递推与回归两个阶段。在递推阶段,把较复杂的问题(规模为N)的求解推到比原问题简单一些的问题(规模小于N)的求解。在回归阶段,当获得最简单的情况后,逐级返回,依次获得稍复杂问题的解。递推是利用问题本身所具有的递推关系对问题求解的一种方法。采用递推法建立起来的算法一般要有重要的递推性质,即当求得问题规模为i-1的解后,由问题的递推性质,能从已求得的规模为1,2,…,i-1的一系列的解,构造出问题规模为i的解。若设这种问题的规模为