算法设计与分析课程论文Word格式.docx

1、递归算法易于理解，结构清晰，所编写的代码简洁精练，可读性好，有利于代码的维护。然而递归算法的效率却较低，占用较大的内存开销，消耗更多的系统堆栈，算法的空间复杂度大，故可以实现的深度是有限制的。而且要考虑函数或算法是否具备收敛性，当且仅当一个算法存在预期的收敛效果时，采用递归算法才是可行的，否则，就不能使用递归算法。2.4递归算法的适用范围由于递归算法的运行效率较低，堆栈容易溢出的特点， 递归算法适用于问题规模较小且那些不存在简明的数学模型以阐明问题的本质，或者存在数学模型，但是难于实现的问题，这样可以减少代码的复杂度。递归算法所适用的问题一般有这样的特征：为求解规模为N的问题，设法先将它分解为

2、规模较小的子问题，然后从这些子问题的解构造出整个问题的解，并且这些子问题也能采用同样的分解和综合方法，分解成规模更小的子问题，并从这些更小的子问题的解构造出较大规模的问题的解，特别地，当规模N=1时，能直接得解。例如很多的数学函数是递归定义的（阶乘函数）、有的数据结构（广义表，二叉树）还有一类本身没有明显的递归结构但用递归求解更为简单的问题（汉诺塔问题，八皇后问题）。2.5递归与递推的关系递推法是求解递归方程的基本方法，对于某些递归关系可由逐级递推求得递归方程的解。递归算法会引起一系列的函数调用，并且可能会有一系列的重复计算，所以当某个递归算法能较方便地转化成递推算法时，通常按递推算法编写程序

3、。递归算法的执行过程分递推与回归两个阶段。在递推阶段，把较复杂的问题（规模为N）的求解推到比原问题简单一些的问题（规模小于N）的求解。在回归阶段，当获得最简单的情况后，逐级返回，依次获得稍复杂问题的解。递推是利用问题本身所具有的递推关系对问题求解的一种方法。采用递推法建立起来的算法一般要有重要的递推性质，即当求得问题规模为i-1的解后，由问题的递推性质，能从已求得的规模为1，2，i-1的一系列的解，构造出问题规模为i的解。若设这种问题的规模为N，当N=0或N=1时，解或为已知，或能很容易地求得。2.6用递归算法来解决“骨头的诱惑”问题2.6.1问题描述一只小狗在一个古老的迷宫里找到一根骨头，当

4、它叼起骨头时，迷宫开始颤抖，它感觉到地面开始下沉。它才明白骨头是一个陷阱，它拼命地试着逃出迷宫。迷宫是一个NM 大小的长方形，迷宫有一个门。刚开始门是关着的，并且这个门会在第T 秒钟开启，门只会开启很短的时间（少于一秒），因此小狗必须恰好在第T 秒达到门的位置。每秒钟，它可以向上、下、左或右移动一步到相邻的方格中。但一旦它移动到相邻的方格，这个方格开始下沉，而且会在下一秒消失。所以，它不能在一个方格中停留超过一秒，也不能回到经过的方格。小狗能成功逃离吗？2.6.2问题分析小狗要在迷宫中到处搜寻可以逃离道路，如果找到则成功逃离，如果找不到则会被困住。此骨头的诱惑问题可以用典型的递归与回溯方法进行

5、求解。对问题进行建模并用非形式化语言描述如下： 递归搜索阶段：给定小狗当前位置，按照一定的顺序对下一步的走向进行深度递归搜索，算法需要保存现场。 回溯恢复阶段：当某条路径的终点并不是出口时，算法需要回退，这就恢复现场，一边从另一个方向进行搜索。 结束条件：当搜索了所有的路径，让没有找到出口，则结束算法，此结果代表没有出路；当找到一个出口，同样结束算法，此结果代表找到出路，递归路径即为小狗逃离路径。2.6.3程序设计C语言实现的主要代码如下：int fun（int si,int sj,int time） int i; int g,h; if（si=di & sj=dj & time=t） ret

6、urn 1; for（i=0; i4; i+） g = si+movei0; h = sj+movei1; if（mazegh = .） mazegh = X; / 走过之后，设置为墙壁 if（fun（g,h,time+1） / 递归下一分支是否有通路 return 1; / 回溯，恢复现场 return 0;3动态规划分析3.1动态规划简介与特点动态规划（dynamic programming）是运筹学的一个分支，是求解决策过程（decision process）最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程（multistep decision

7、 process）的优化问题时，提出了著名的最优化原理（principle of optimality），把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法动态规划。动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。不象搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。因此必须具体问题具体分析处理，

8、以丰富的想象力去建立模型，用创造性的技巧去求解。3.2动态规划基本思想动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我

9、们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。3.3适合动态规划解决的问题 具有最优子结构性，即原问题的最优解包含子问题的最优解。 子问题重叠性，也就是说子问题之间不是独立的，一个子问题在下一阶段决 策中可能被多次使用到。对有分解过程的子问题还表现在：自顶向下分解问题时，每次产生的子问题并不总是新问题，有些子问题会反复出现多次。3.4算法设计步骤 找出最优解的性质，并刻划其结构特征。 递归地定义最优值。 以自底向上的方式计算出最优值。 根据计算最优值时

10、得到的信息，构造最优解。3.5用动态规划来解决“0/1背包”问题3.5.1问题描述给定n种物品和1个背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何装入背包中的物品，使得装入背包中物品的总价值最大？在选择装入背包的物品时，对每种物品只有两种选择，即装入背包、不装入背包。不能将物品装入背包多次，也不能只装入部分的物品i。该问题称为0/1背包问题。3.5.2问题分析令V（i,j）表示在前i（1=i=n）个物品中能够装入容量为就j（1=j=C）的背包中的物品的最大价值，则可以得到如下的动态规划函数:（1）V（i,0）=V（0,j）=0（2）V（i,j）=V（i-1,j） j（1）式表

11、明：如果第i个物品的重量大于背包的容量，则装人前i个物品得到的最大价值和装入前i-1个物品得到的最大价是相同的，即物品i不能装入背包；（2）式表明：如果第i个物品的重量小于背包的容量，则会有一下两种情况：（a）如果把第i个物品装入背包，则背包物品的价值等于第i-1个物品装入容量位j-wi的背包中的价值加上第i个物品的价值vi; （b）如果第i个物品没有装入背包，则背包中物品价值就等于把前i-1个物品装入容量为j的背包中所取得的价值。显然，取二者中价值最大的作为把前i个物品装入容量为j的背包中的最优解。3.5.3程序设计int KnapSack（int n,int w,int v,int x,i

12、nt C）int i,j;for（i=0;=n; i+）Vi0 = 0;for（j=0; j=C; j+）V0j = 0;=n-1;for（j=0;if（j =0; i-） if（Vij Vi-1j） xi = 1;j = j-wi;elsexi = 0;printf（选中的物品是:n）;n;printf（%d ,xi）;return Vn-1C;4总结递归和动态规划是算法设计中的重要方法，它们涉及面很广泛，本文只是对其进行了初步探讨，还有很多更加深入的东西等着大家去深入研究。作为算法设计的经典方法，它们并不会随着时间的流逝而丧失意义，相反，它对我们的算法设计研究提供了重要的思路以及指导。参考文献1 余祥宣，崔国华，邹海明.计算机算法基础M.武汉：华中科技大学出版社，2003.2 吕国英，任瑞征，钱宇华.算法设计与分析：清华大学出版社.3 应莉0-1背包问题及其算法计算机与现代化（2009）06-0024-03.