1 / 11
文档名称:

排列问题的递归算法.ppt

格式:ppt   页数:11页
下载后只包含 1 个 PPT 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

排列问题的递归算法.ppt

上传人:fy3986758 2016/7/7 文件大小:0 KB

下载得到文件列表

排列问题的递归算法.ppt

相关文档

文档介绍

文档介绍:算法设计与分析排列问题的递归算法 排列问题的递归算法有n个元素,把它们编号为 1,2…n,用一个数组 A 来存放所生成的排列,然后输出它们。假定开始时 n个元素以依次存放在数组 A中,为了生成这 n个元素的所有排列,可以采取下面的步骤: (1)第一个元素为 1,即排列的第一个元素为 1,生成后面 n-1 个元素的排列。(2)第一个元素和第二个元素互换,使排列的第一个元素为 2,生成后面 n-1 个元素的排列。(3)如此继续,最后第一个元素和第 n个元素互换,使排列的第一个元素为 n,生成后面 n-1 个元素的排列。在上面的第一步,为生成后面 n-1 个元素的排列,继续采取下面的步骤: (1)第二个元素为 2,即排列的第二个元素为 2,生成后面 n-2 个元素的排列。(2)第二个元素和第三个元素互换,使排列的第二个元素为 3,生成后面 n-2 个元素的排列。(3)如此继续,最后第二个元素和第 n个元素互换,使排列的第二个元素为 n,生成后面 n-2 个元素的排列。这种步骤一直继续,当排列的前 n-2 个元素已确定后,为生成后面 2个元素的排列,可以: (1)第 n-1 个元素为 n-1, 即排列的第 n-1 个元素为 n-1 ,生成后面 1个元素的排列,此时 n个元素已构成一个排列。(2)第 n-1 个元素和第 n个元素互换,使排列的第 n-1 个元素为 n,生成后面 1个元素的排列,此时n个元素已构成一个排列。令排列算法 perm(A,k,n) 表示生成数组后面个元素的排列。通过上面的分析有: (1)基础步: k=1, 只有一个元素,已构成一个排列。(2)归纳步:对任意的 k,1<k<=n 完成 perm(A,k-1,n), 逐一对第 n-k 元素与第 n-k~n 元素进行互换,每互换一次,就执行一次 perm(A,k -1,n) 操作,产生一个排列。由此,排列生成的递归算法可描述如下: 算法 排列的生成输入:数组 A[ ], 数组的元素个数 n 输出:数组 A[ ] 的所有排列 <class Type> perm(Type A[],int k,int n) 3.{ i; (k==1) (i=0;i<n;i++) / *已构成一个排列,输出它*/ << A[i]; 9.{10. for (i=n-k;i<n;i++) / *生成后续的一系列排列*/ 11. {12. swap(A[i],A[n-k]); (A,k-1,n); (A[i],A[n-k]); 15. }16. }17.} ???????1)1()( )1(nnfnnf nf 递归方程: 基本操作:元素输出。得到!)(nnnf?。算法的运行时间: )!(nn?。递归栈的空间为作单元,递归深度为每一次递归需常数个工)( ,n n?栈的变化情况: 算法的执行过程和递归例:对数组}3,2,1{?A i k 1 1 1 1 1 1 n 3 3 3 3 3 3 A 的内容 1 2 3 1 3 2 2 1 3 2 3 1 3 2 1 3 1 2 输出结果 i 1 2 1 2 1 2 n – k = 1 k 2 2 2 n 3 3 3 A 的内容 1 2 3 1 3 2 1 2 3 2 1 3 2 3 1 2 1 3 3 2 1 3 1 2 3 2 1 i 0

最近更新

2025年推进基本医疗服务公平可及化 61页

2025年尿路结石预防与治疗攻略 24页

二零二五年度企业廉洁自律培训协议 8页

二零二五年度企业培训人员借调与员工培训服务.. 8页

2025年发烧原因与诊断方法探究 52页

二零二五年度企业反垄断合规与律师事务所合作.. 9页

二零二五年度企业信用评估委托代办服务合同 9页

二零二五年度人工智能教育平台合作框架协议 8页

二零二五年度人力资源公司企业员工档案管理服.. 8页

二零二五年度互联网科技公司个人入股合同 7页

2025年出血凝血障碍诊疗策略探究 31页

2025年感恩亲情素材200字作文 12页

二零二五年度乙方商铺租赁合同附带租金预付安.. 7页

二零二五年度临时用电安全协议书(施工企业专.. 9页

2025年养老护理基础培训教程 41页

二零二五年度中日合资企业日语外贸顾问劳动合.. 9页

2025年愚人节起源于哪个国家呢 5页

二零二五年度个体家具制造厂品牌及生产线整体.. 8页

二零二五年度个人转租房屋租赁合同(含社区健.. 7页

二零二五年度个人车位出租与停车场安全管理协.. 8页

二零二五年度个人著作权转让合同 9页

二零二五年度个人经营性贷款委托合同 7页

2025年情人节经典抖音语句 11页

2025年儿童心理发展关键理论解析 81页

二零二五年度个人家居用品销售提成与设计咨询.. 9页

二零二五年度个人农村土地租赁合同(附带农业.. 8页

二零二五年度个人信用担保抵押借款协议 8页

2025年保险医疗与临床诊疗比较研究 37页

艺术舞蹈老师简历模板 1页

服装设计合作协议书 5页