递归算法一个（C++）？(50分)

  • 主题发起人 主题发起人 KenLee
  • 开始时间 开始时间
K

KenLee

Unregistered / Unconfirmed
GUEST, unregistred user!
下面的递归算法有点难懂，请哪位大虾指定一下。
template<class T>
void Perm(T list[], int k, int m )
{
int i;
if (K==m){
for(i = 0;
i <= m;
i++)
cout<< list;
cout<< endl;
}
else
for( i = k;
i <= m;
i++){ //哪位给这段讲解一下递归过程
Swap(list[k], list);
Perm(list, k+1, m);
Swap(list[k], list);
}
//if end
template<class T>
inline void Swap(T&amp;
a, T&amp;
b)
{
T temp = a;
a = b;
b = tamp;
}
 
[?] 我也想知道这个问题的答案，我前几天刚学模板，还不太理解。
 
看来只有画在纸上了
 
该算法k,m如果分别指向list[]的头和尾，是输出list从左到右的循环移位，每移一位就输出list直到list恢复原样，但在整个过程中list的值并为改变
 
对不起，各位大侠，差点忘了——好像不是这么简单的
还有吗？
 
大家看是不是快速排序的算法？
法Quick_Sort的实现：
Pascal实现：
Procedure Quick_Sort(p,r:TPosition;var L:TList);
{快速排序}
var
q:TPosition;
begin

if L[p..r]足够小 then
Sort(p,r,L) {若L[p..r]足够小则直接对L[p..r]排序}
else

begin

q:=Partition(p,r,L);
{将L[p..r]分解为L[p..q]和L[q+1..r]两部分}
Quick_Sort(p,q,L);
{递归排序L[p..q]}
Quick_Sort(q+1,r,L);
{递归排序L[q+1..r]}
end;

end;


 
我觉得是一串字符的全排列
结果是2^n个字符串
不是化简的quick sort
 
同意楼上的说法。
else
for( i = k;
i <= m;
i++){
Swap(list[k], list);
Perm(list, k+1, m);
<-- 不管这行，则此循环的意义就是轮流将k后面的数组元素
Swap(list[k], list);
在k中存放了一遍。
}
想想看，首先把第一个数组单元后的元素在第一个数组单元中轮流存放一遍，然后将第二个
数组单元后的数组单元在第二个数组单元中存放一遍。然后将第三个数组单元中的...。
还可以这样理解：
比如要获得数列1,2,3,4的完全排列组合。
首先定下第一个数为：1，然后只要获得剩下的2,3,4的所有排列组合。在这些排列前面加上第一个数1,
就行了。
然后定下第一个数为 2，然后只要获得剩下的1,3,4的所有排列组合，在这些排列组合前面加上第一
个数 2就可以了。
接下来定下第一个数为 3,最后定第一个数为4。（轮流把这四个数定为第一个数）
要得到2,3,4；1,3,4；1,2,4；1,2,3的排列组合重复上述步骤。
最后的结果便是，整个数组中的数字被排列组合了一遍。
 
只是做了一个排列组合，连比较也没有怎么会是快速排序呢。
 
呵呵
前几天考试
这个确实在长相上有点象quick sort
 
是一串字符的全排列
结果是2^n个字符串
 
多人接受答案了。
 
您必须登录或注册才可回复。

Similar threads

I
常用算法（3）动态规划
回复
0
查看
1K
import
I
I
排列组合
回复
0
查看
603
import
I
I
对称逆矩阵的计算方法
回复
0
查看
792
import
I
I
8皇后问题的非递归程序
回复
0
查看
790
import
I
I
Uuencode
回复
0
查看
573
import
I
后退
顶部