算法设计与分析课程论文.doc

. . 算法设计与分析课程论文 1．引言 算法设计与分析是数据结构的有力补充，从中可以了解到算法设计的奥妙以及对数据结构中的数据存储结构更深层次的运用。计算机算法设计与分析是面向设计的、处于核心地位的一门学科。算法是一组有穷的规则，它规定了解决某一特定类型问题的一系列运算。算法设计是一件非常困难的工作，常用的算法设计方法有：分治法、贪心方法、动态规划、回溯法、分枝－限界法、基本检索与周游方法、遗传算法等。 本文主要对算法设计与分析中的递归算法以及动态规划算法进行了总结、分析以及对具体问题的编程实现。 2．递归算法分析 2.1递归算法简介与特点 递归就是在函数或子过程的内部，直接或间接地调用自己的算法；递归算法是从下往上进行思维，需要对问题有全局的了解；在使用递归算法时，必须至少测试一个可以终止递归的条件，并且还必须对在合理的递归调用次数内未满足此类条件的情况进行处理，如果没有一个在正常情况下可以满足的条件，则过程将陷入执行无限循环的高度危险之中；递归算法的描述非常简洁而易于理解，但因重复计算和较大的堆栈消耗使递归算法的解题的运行效率较低；并不是所有的语言都支持递归，在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储，递归次数过多容易造成栈溢出等不利编程的因素，所以一般不提倡用递归算法设计程序。 2.2递归过程 递归过程是直接调用自己或通过一系列的过程调用语句间接调用自己的过程。在一个过程的运行期间调用另一个过程时，在执行被调用过程之前，系统要先把所有的实在参数返回地址等信息传递给被调用的过程保存，为被调用过程的局部变量分配存储空间，将控制转移到被调用入口。接下来从被调过程返回调用过程要保存被调用过程的计算结果，释放被调用过程的数据区，依照被调过程保存的返回地址将控制转移到调用过程。该过程服从后调用先返回的原则。 2.3递归算法的优缺点 递归算法易于理解，结构清晰，所编写的代码简洁精练，可读性好，有利于代码的维护。然而递归算法的效率却较低，占用较大的内存开销，消耗更多的系统堆栈，算法的空间复杂度大，故可以实现的深度是有限制的。而且要考虑函数或算法是否具备收敛性，当且仅当一个算法存在预期的收敛效果时，采用递归算法才是可行的，否则，就不能使用递归算法。 2.4递归算法的适用范围 由于递归算法的运行效率较低，堆栈容易溢出的特点， 递归算法适用于问题规模较小且那些不存在简明的数学模型以阐明问题的本质，或者存在数学模型，但是难于实现的问题，这样可以减少代码的复杂度。 递归算法所适用的问题一般有这样的特征：为求解规模为N的问题，设法先将它分解为规模较小的子问题，然后从这些子问题的解构造出整个问题的解，并且这些子问题也能采用同样的分解和综合方法，分解成规模更小的子问题，并从这些更小的子问题的解构造出较大规模的问题的解，特别地，当规模N=1时，能直接得解。例如很多的数学函数是递归定义的（阶乘函数）、有的数据结构（广义表，二叉树）还有一类本身没有明显的递归结构但用递归求解更为简单的问题（汉诺塔问题，八皇后问题）。 2.5递归与递推的关系 ①递推法是求解递归方程的基本方法，对于某些递归关系可由逐级递推求得递归方程的解。 ②递归算法会引起一系列的函数调用，并且可能会有一系列的重复计算，所以当某个递归算法能较方便地转化成递推算法时，通常按递推算法编写程序。 ③递归算法的执行过程分递推与回归两个阶段。在递推阶段，把较复杂的问题(规模为N)的求解推到比原问题简单一些的问题(规模小于N)的求解。在回归阶段，当获得最简单的情况后，逐级返回，依次获得稍复杂问题的解。递推是利用问题本身所具有的递推关系对问题求解的一种方法。采用递推法建立起来的算法一般要有重要的递推性质，即当求得问题规模为i-1的解后，由问题的递推性质，能从已求得的规模为1，2，…，i-1的一系列的解，构造出问题规模为i的解。若设这种问题的规模为N，当N=0或N=1时，解或为已知，或能很容易地求得。 2.6用递归算法来解决“骨头的诱惑”问题 2.6.1问题描述 一只小狗在一个古老的迷宫里找到一根骨头，当它叼起骨头时，迷宫开始颤抖，它感觉到地面开始下沉。它才明白骨头是一个陷阱，它拼命地试着逃出迷宫。 迷宫是一个N×M 大小的长方形，迷宫有一个门。刚开始门是关着的，并且这个门会在第T 秒钟开启，门只会开启很短的时间（少于一秒），因此小狗必须恰好在第T 秒达到门的位置。每秒钟，它可以向上、下、左或右移动一步到相邻的方格中。但一旦它移动到相邻的方格，这个方格开始下沉，而且会在下一秒消失。所以，它不能在一个方格中停留超过一秒，也不能回到经过的方格。 小狗能成功逃离吗？ 2.6.2问题分析 小狗要在迷宫中到处搜寻可以逃离道路，如果找到则成功逃离，如果找不到则会被困住。 此骨头的诱惑问题可以用典型