全排列算法原理与实现01928

全排列算法原理与实现01928

ID:22049311

大小:29.50 KB

页数:8页

时间:2018-10-26

全排列算法原理与实现01928_第1页
全排列算法原理与实现01928_第2页
全排列算法原理与实现01928_第3页
全排列算法原理与实现01928_第4页
全排列算法原理与实现01928_第5页
资源描述:

《全排列算法原理与实现01928》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、全排列算法原理和实现01928http://acm-hit.sunner.cn/index.php全排列是将一组数按一定顺序进行排列,如果这组数有n个,那么全排列数为n!个。现以{1,2,3,4,5}为例说明如何编写全排列的递归算法。1、首先看最后两个数4,5。它们的全排列为45和54,即以4开头的5的全排列和以5开头的4的全排列。由于一个数的全排列就是其本身,从而得到以上结果。2、再看后三个数3,4,5。它们的全排列为345、354、435、453、534、543六组数。即以3开头的和4,5的全排列的组

2、合、以4开头的和3,5的全排列的组合和以5开头的和3,4的全排列的组合.从而可以推断,设一组数p={r1,r2,r3,...,rn},全排列为perm(p),pn=p-{rn}。因此perm(p)=r1perm(p1),r2perm(p2),r3perm(p3),...,rnperm(pn)。当n=1时perm(p}=r1。为了更容易理解,将整组数中的所有的数分别与第一个数交换,这样就总是在处理后n-1个数的全排列。算法如下:#includeintn=0;voidswap(int*a,i

3、nt*b){intm;m=*a;*a=*b;*b=m;}voidperm(intlist[],intk,intm){inti;if(k>m){for(i=0;i<=m;i++)printf("%d",list[i]);printf("");n++;}else{for(i=k;i<=m;i++){swap(&list[k],&list[i]);perm(list,k+1,m);swap(&list[k],&list[i]);}}}intmain(){intlist[]={1,2,3,4,5};perm(

4、list,0,4);printf("total:%d",n);return0;}谁有更高效的递归和非递归算法,请回贴。《银河系列原创教程》发布000(请您对文章做出评价)postedon2008-05-1109:30银河使者阅读(5394)评论(9)编辑收藏网摘所属分类:algorithmBody:46.875,BeforeCate:0,62.5,Total:1265.625评论1546187#1楼2008-05-1110:25lucklier[未注册用户]递归的话如果排列的数字多了,效率可能会比较低

5、,高中的时候为了奥赛这个问题研究了比较长时间,用pascal写过一个,不过现在都忘了。有时间俺也去研究研究回复引用#2楼2008-05-1123:32镜涛递归深度对性能的影响会很大,呵呵。对算法研究不深就不献丑啦回复引用查看#3楼2008-06-0419:56ptrlink[未注册用户]为什么总有少数组数会出现错位呢?回复引用#4楼2008-07-0815:48asfasfas[未注册用户]如果数组中有重复的数,输出会重复,怎么解决?回复引用#5楼2008-10-0515:23五行连环[未注册用户]if(

6、k>m)应该是if(k==m)回复引用#6楼2008-11-2813:24miao44[未注册用户]优化了一下intperm(intlist[],intk,intm){inti;staticintn;...swap(list[k],list[i]);...swap(list[k],list[i]);...returnn;}main(){intlist[5]={1,2,3,4,5};printf("total:%d",perm(list,0,4));}这样就可以不用定义全局变量n,更友好。另外swap函

7、数可以不用重写,直接使用系统函数,去掉前面的取址符就可以了。回复引用#7楼2009-03-1414:35YJC[未注册用户]5楼的你才错了不是等号是大于号因为这里多一层回复引用#8楼2009-04-2716:57FC[未注册用户]思想就是你说的这样,代码好像更好了点,献丑#includevoidswap(char*a,char*b){chart;t=*a;*a=*b;*b=t;}voidprint(char*a,intl){inti=0;for(;i

8、a[i]);printf("");}voidpermut(char*a,intp,intq,intlength){inti=0;for(i=p;i<=q;++i){swap(&a[i],&a[p]);if(p==q)print(a,length);permut(a,p+1,q,length);}}intmain(){chara[4]={'a','b','c','d'};permut(a,0,3,4);return0;}回复

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。