算法设计与分析课程论文

《算法设计与分析课程论文》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、算法设计与分析课程论文1.引言算法设计与分析是数据结构的有力补充，从中可以了解到算法设计的奥妙以及对数据结构中的数据存储结构更深M次的运用。计算机算法设计与分析是面向设计的、处于核心地位的一门学科。算法是一组有穷的规则，它规定了解决某一特定类型问题的一系列运算。算法设计是一件非常网难的工作，常用的算法设计方法有：分治法、贪心方法、动态规划、冋溯法、分枝一限界法、基本检索与周游方法、遗传算法等。本文主要对算法设计与分析中的递归算法以及动态规划算法进行了总结、分析以及对異体问题的编程实现。2.递归算法分析2.1递归算法简介与特点递归就是在函数或子过程的内部，直接或问接地调

2、用自己的算法；递归算法是从下往上进行思维，需要对问题有全局的了解；在使用递归算法时，必须至少测试一个可以终止递归的条件，并且还必须对在合理的递归调用次数内未满足此类条件的情况进行处理，如果没有一个在止常情况卜可以满足的条件，则过程将陷入执行无限循环的高度危险之巾；递归算法的描述非常简洁而易于理解，但因重复计算和较大的堆栈消耗使递归算法的解题的运行效率较低：并不是所有的语言都支持递归，在递归调用的过程当中系统为每一层的返冋点、局部量等开辟了栈来存储，递归次数过多容易造成栈溢出等不利编程的因素，所以一般不提侣用递归算法设计程序。2.2递归过程递归过程是直接调用G己或通过一

3、系列的过程调用语川间接调用0己的过程。在一个过程的运行期问调用另一个过程时，在执行被调用过程之前，系统要先把所有的实在参数返回地址等信息传递给被调用的过程保存，为被调用过程的局部变量分配存储空间，将控制转移到被调用入口。接下来从被调过程返冋调用过程要保存被调用过程的计算结果，释放被调用过程的数据区，依照被调过程保存的返冋地址将控制转移到调用过程。该过程服从后调用先返冋的原则。2.3递归算法的优缺点递归算法易于理解，结构清晰，所编写的代码简洁精练，可读性好，有利于代码的维护。然而递归算法的效率却较低，占用较大的PJ存开销，消耗更多的系统堆栈，算法的空1X1复杂度大，故可

4、以实现的深度是有限制的。而且要考虑函数或算法是否具备收敛性，当且仅当一个算法存在预期的收敛效來时，采用递归算法1是可行的，否则，就不能使用递归算法。2.4递归算法的适用范围由于递归算法的运行效率较低，堆栈容易溢出的特点，递归算法适用于问题规模较小且那些不存在简明的数学模型以阐明问题的本质，或者存在数学模型，但是难于实现的问题，这样可以减少代码的复杂度。递归算法所适用的问题一般有这样的特征：为求解规模为N的问题，设法先将它分解为规模较小的子问题，然G从这些•了问题的解构造出整个问题的解，井且这些子问题也能采用同样的分解和综合方法，分解成规模更小的子问题，并从这些更小的子

5、问题的解构造出较大规模的问题的解，特别地，当规模N=1时，能直接得解。例如很多的数学函数是递归定义的（阶乘函数）、有的数据结构（广义表，二叉树）还宥一类本身没宥明显的递归结构但用递归求解更为简单的问题（汉诺塔问题，八皇后问题）。2.5递归与递推的关系①递推法是求解递归方程的基木方法，对于某些递归关系可由逐级递推求得递归方程的解。②递归算法会引起一系列的函数调用，并且可能会有一系列的重复计算，所以当某个递归算法能较方便地转化成递推算法吋，通常按递推算法编写程序。③递归算法的执行过程分递推与回归两个阶段。在递推阶段，把较复杂的问题（规模为N）的求解推到比拟问题简单一些的问

6、题（规模小于N）的求解。在［H］归阶段，当获得最简单的情况后，逐级返回，依次获得稍复杂问题的解。递推是利用问题本身所具有的递推关系对问题求解的一种方法。采用递推法建立起来的算法一般耍宥重耍的递推性质，即当求得问题规模为i-1的解石，由问题的递推性质，能从已求得的规模为1，2，…，i-1的一系列的解，构造出问题规模为i的解。若设这种问题的规模为N,当N=0或N=1时，解或为已知，或能很各易地求得。2.6用递归算法來解决"骨尖的诱惑〃问题2.6.1问题描述一只小狗在一个古老的迷宫里找到一根骨头，当它叼起骨尖吋，迷宫开始颤抖，它感觉到地面开始下沉。它:i明白骨头是一个陷阱，

7、它拼命地试着逃出迷宫。迷宫是一个NXM大小的长方形，迷宫有一个门。刚幵始门是关着的，并且这个门会在第T秒钟开启，门只会开泊很短的吋间(少于一秒)，因此小狗必须恰好在第T秒达到门的位置。每秒钟，它可以向上、卜、左或右移动一步到相邻的方格屮。但一旦它移动到相邻的方格，这个方格开始卜沉，而且会在下一秒消失。所以，它不能在一个方格中停留超过一秒，也不能回到经过的方格。小狗能成功逃离吗？2.6.2问题分析小狗耍在迷宫中到处搜寻可以逃离道路，如來找到则成功逃离，如采找不到则会被困住。此骨尖的诱惑问题可以用典型的递归与回溯方法进行求解。对问题进行建模并用非形式化语