毕业论文移动版

有的递归特性，特别适合用递归的形式来描述。 如汉诺塔问题：

将塔座 a 上的一叠 n 个圆盘移动到塔座 b 上，并按照同样的顺序叠置。递归 算法如下：

//把 n 个盘子依照规则从塔座 a 移至塔座 b； hanoi(n,a,b,c)

{

if(n>0)

{

//依照规则利用塔座 b 把 n-1 个较小的盘子从塔座 a 移至塔座 c； hanoi(n-1,a,c,b);

//把最下面那个盘子从塔座 a 移动到塔座 b; move(a,b);

//依照规则利用塔座 b 把 n-1 个较小的盘子从塔座 c 移至塔座 b; hanoi(n-1,c,b,a);

}

}

由上述可知，递归算法的实现类似于多个算法之间嵌套的调用，只不过调用 和被调用的算法是同一个算法。

2.2 分治

顾名思义，“分治”名字本身就给出了强大的算法设计技术。分治方法是一 种典型的自顶向下的算法设计技术，它可以解决各类问题。为解决某一个问题， 把问题分解为一个或多个子问题，使得每个子问题的类型与原问题相似，并且对 每个子问题独立进行求解，最后将各个子问题的解合并，从而获得原问题的解。 如果划分后的子问题规模仍然相当大，则可利用用分治方法对这些子问题反复进 行划分，直至问题划分得足够小，容易求出问题的解为止。在应用分治方法的过 程中，由于子问题的类型仍然和原问题相似，因此设计算法时很自然地导致递归 过程。

分治算法通常用递归操作来实现。作为算法设计的技巧来说，递归是分治策来!自~优尔论-文|网www.youerw.com

略常用的算法设计技巧