我们先来看看大家熟知的一个的故事：
从前有座山，山上有座庙，庙里有个老和尚在给小和尚讲故事，他说从前有座山轮孙，山上有座庙，庙里有个老和尚在给小和尚讲故事，他说……
上面的故事本身是递归的，用递归算法描述：
procedure bonze-tell-story；
begin
if 讲话被打断 then 故事结束
else begin
从前有座山，山上有座庙，庙里有个老和尚在给小和尚讲故事；
bonze-tell-story；
end
end
从上面的递归事例不难看出，递归算法存在的两个必要条件：
（1）必须有递归的终止条件；
（2）过程的描述中包含它本身；
在设计递归算法中，如何将一个问题转化为递归的问题，是初学者面临的难题，下面我们通过分析汉诺塔问题，看看如何用递归算法来求解问题；
例1：汉诺塔问题，如下图，有A、B、C三根柱子。A柱子上按从小到大的顺序堆放了N个盘子，现在要把全部盘子从A柱移动到C柱，移动过程中可以借助B柱。移动时有如下要求：
（迅搏1）一次只能移动一个盘子；
（2）不允许把大盘放在小盘上边；
（3）盘子只能放在三根柱子上；
算法分析：当盘子比较多的时，问题比较复杂，所以我们先分析简单的情况：
如果只有一个盘子，只需一步，直接把它从A柱移动到C柱；
如果是二个盘子，共需要移动3步:
（1）把A柱上的小盘子移动到B柱
（2）把A柱上的大盘子移动到C柱；
（3）把B柱上的大盘子移动到C柱；
如果N比较大时，需要很多步才能完成腊昌链，我们先考虑是否能把复杂的移动过程转化为简单的移动过程，如果要把A柱上最大的盘子移动到C柱上去，必须先把上面的N-1个盘子从A柱移动到B柱上暂存，按这种思路，就可以把N个盘子的移动过程分作3大步：
（1）把A柱上面的N-1个盘子移动到B柱；
（2）把A柱上剩下的一个盘子移动到C柱；
（3）把B柱上面的N-1个盘子移动到C柱；
其中N-1个盘子的移动过程又可按同样的方法分为三大步，这样就把移动过程转化为一个递归的过程，直到最后只剩下一个盘子，按照移动一个盘子的方法移动，递归结束。
递归过程：
procedure Hanoi(N,A,B,C:integer)；{以B柱为中转柱将N个盘子从A柱移动到C柱}
begin
if N=1 then write(A,’->’,C){把盘子直接从A移动到C}
else begin
Hanoi(N-1,A,C,B)；{ 以C柱为中转柱将N-1个盘子从A柱移动到B柱}
write(A,’->’,C)；{把剩下的一个盘子从A移动到C}
Hanoi(N-1,B,A,C)； { 以A柱为中转柱将N-1个盘子从B柱移动到C柱}
end
end
从上面的例子我们可以看出，在使用递归算法时，首先弄清楚简单情况下的解法，然后弄清楚如何把复杂情况归纳为更简单的情况。
在信息学奥赛中有的问题的结构或所处理的数据本身是递归定义的，这样的问题非常适合用递归算法来求解，对于这类问题，我们把它分解为具有相同性质的若干个子问题，如果子问题解决了，原问题也就解决了。
例2求先序排列 (NOIP2001pj)
[问题描述]给出一棵二叉树的中序与后序排列。求出它的先序排列。(约定树结点用不同的大写字母表示，长度≤8)。
[样例] 输入：BADC BDCA 输出：ABCD
算法分析：我们先看看三种遍历的定义：
先序遍历是先访问根结点，再遍历左子树，最后遍历右子树；
中序遍历是先遍历左子树，再访问根结点，最后遍历右子树；
后序遍历是先遍历左子树，再遍历右子树，最后访问根结点；
从遍历的定义可知，后序排列的最后一个字符即为这棵树的根节点；在中序排列中，根结点前面的为其左子树，根结点后面的为其右子树；我们可以由后序排列求得根结点，再由根结点在中序排列的位置确定左子树和右子树，把左子树和右子树各看作一个单独的树。这样，就把一棵树分解为具有相同性质的二棵子树，一直递归下去，当分解的子树为空时，递归结束，在递归过程中，按先序遍历的规则输出求得的各个根结点，输出的结果即为原问题的解。
源程序
program noip2001_3
var z,h : string
procedure make(z,h:string){z为中序排列,h为后序排列}
var s,m : integer
begin
m:=length(h){m为树的长度}
write(h[m]){输出根节点}
s:=pos(h[m],z){求根节点在中序排列中的位置}
if s>1 then make(copy(z,1,s-1),copy(h,1,s-1)){处理左子树}
if m>s then make(copy(z,s+1,m-s),copy(h,s,m-s)){处理右子树}
end
begin
readln(z)
readln(h)
make(z,h)
end.
递归算法不仅仅是用于求解递归描述的问题，在其它很多问题中也可以用到递归思想，如回溯法、分治法、动态规划法等算法中都可以使用递归思想来实现，从而使编写的程序更加简洁。
比如上期回溯法所讲的例2《数的划分问题》，若用递归来求解，程序非常短小且效率很高，源程序如下
var
n,k:integer
tol:longint
procedure make(sum,t,d:integer)
var i:integer
begin
if d=k then inc(tol)
else for i:=t to sum div 2 do make(sum-i,i,d+1)
end
begin
readln(n,k)
tol:=0
make(n,1,1)
writeln(tol)
end.
有些问题本身是递归定义的，但它并不适合用递归算法来求解，如斐波那契(Fibonacci)数列，它的递归定义为：
F(n)=1 (n=1,2)
F(n)=F(n-2)+F(n-1) (n>2)
用递归过程描述为：
Funtion fb(n:integer):integer
Begin
if n<3 then fb:=1
else fb:=fb(n-1)+fb(n-2)
End
上面的递归过程，调用一次产生二个新的调用，递归次数呈指数增长，时间复杂度为O（2n）,把它改为非递归：
x:=1y:=1
for i:=3 to n do
begin
z:=yy:=x+yx:=z
end
修改后的程序，它的时间复杂度为O（n）。
我们在编写程序时是否使用递归算法，关键是看问题是否适合用递归算法来求解。由于递归算法编写的程序逻辑性强，结构清晰，正确性易于证明，程序调试也十分方便，在NOIP中，数据的规模一般也不大，只要问题适合用递归算法求解，我们还是可以大胆地使用递归算法。
文件结构：插入排序
1.直接插入排序
2.二叉插入排序
3.2路插入排序
4.表插入排序
5.希尔排序
选择排序
1.简单选择排序
2.锦标赛排序（树选择排序）
3.堆排序
交换排序
1.冒泡排序
2.鸡尾酒排序（双向冒泡排序）
3.快速排序
归并排序
1.归并排序
分配漏启排序
1.箱排序（桶排序）
2.基数排序
注意：
1.箱排序没有太大实用价值，主要是被基数返卜如排序所调用。该排序对不同的数据类型有不同的比较方法，本函数中针对整形数据进行比较。
2.快速弊孙排序和堆排序具有较高的效率，但是为了兼具高效保持排序的稳定性，建议使用归并排序。
看了你说递归的效率低。那么你可以不用的。给出的方法就是先生成第一个排列，然后每次调用下面的函数给出下丛橘旅一个排列，这样生成的效率很高，这个函数可以内联。
这个是很经典的排列组合算法啊？在网上能搜到一大堆。
大概是那种带指向的移动的算法。我给你搜一个吧。
我找了几个，这个是我觉得说的比较清楚的，你可以仔细参考一下，看不懂的话再搜点别的好了。。
全排列的算法跟这个不太一样的。需要有点改动的。
至于语言的话，应该不会有太大问题吧。。basic版的确实比较少，现在我也比较懒不想动手写。。还是要靠你自己啦。
★生成排列的算法：
比如要生成5，4，3，2，1的全排列，首先找出一个最小的排列12345, 然后依次调用n!次STL算法中的next_permutation()即可渗凳输出所有的全排列情况。所以这种算法的细节就是STL algorithm中next_permutation()的实现机制。详细的实现代伍携码，大伙可以参考侯捷的《STL源代码剖析》，在这里我只说一下我的理解：
1>首先从最尾端开始往前寻找两个相邻元素，令第一个元素为*i,第二个元素为*ii，且满足*i<*ii，找到这样一组相邻的元素后。
2>再从最尾端开始往前检验，找出第一个大于*i的元素，令为*k，将i,k元素对调。
3>再将ii及ii之后的所有元素颠倒排列，此即所求之"下一个"排列。
prev_permutation()算法的思路也基本相同，只不过它们寻找的"拐点"不同，在next_permutation()算法中寻找的是峰值拐点，而在prev_permutation()算法中寻找的是谷值拐点。另外，在第二步中，prev_permutation()要找的是第一个小于*i的元素而不是第一个大于*i的元素。
具体例子，有空再举，现在时间太晚了:)
★生成组合的算法：
如下面截图所示，分全组合和r-组合两种情况。
这里有一段核心代码：
//--------------------------------------------------------
// Generate next combination (algorithm from Rosen p. 286)
//--------------------------------------------------------
public int[] getNext () {
if (numLeft.equals (total)) {
numLeft = numLeft.subtract (BigInteger.ONE)
return a
}
int i = r - 1
while (a[i] == n - r + i) {
i--
}
a[i] = a[i] + 1
for (int j = i + 1j <rj++) {
a[j] = a[i] + j - i
}
numLeft = numLeft.subtract (BigInteger.ONE)
return a //这里返回的a数组，存储的就是下标的排列组合。
}
到这里，也许大伙会有一个疑问，假如要求的不是数字的排列组合，而是字符或字符串的排列组合呢？怎么办？其实很简单，你只要拿数组的下标来做排列组合，返回他们下标的排列组合，然后再到原数组中读取字符串值，就可以输出全部的排列组合结果。
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）