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

最近更新

摄影棚装修合同书3篇 51页

1981年国内研究生入学试题选载(Ⅱ) 2页

1515—75″布机投梭力配置的初探 2页

10吨工频炉熔炼潜力与经济性的探讨 2页

东风日产PPAP表格 22页

质量审核中不合格项的判定 19页

高速铁路CPⅢ测量标志在建筑变形监测中的应用.. 3页

社会资本在社会创新中的作用-全面剖析 26页

非物质文化遗产的传承开发研究——以丝绸之路.. 3页

闭式循环水系统在空气压缩机的应用 3页

铁路固定资产管理的探讨与探究 3页

详解营销渠道管理与渠道设计 68页

7个方面直观幼儿园的幼小衔接是否成熟可行 2页

透水层水中承台沉井围堰施工技术 4页

大数据应用中的内存优化方法-全面剖析 32页

路桥工程施工中的软土地基处理技术探究 3页

超分子聚乙醇类“固-固相变材料”的研究 3页

财政专项资金预算绩效管理初探 3页

试论作者队伍建设的重要性及途径、方法 3页

记者在新闻采访中的作用及沟通技巧的有效应用.. 3页

西门子技术在棒材轧机改造中的应用 3页

行政事业单位固定资产内部控制问题研究 3页

蔗渣纤维素分离纯化预处理工艺条件优化 3页

苏浙沪三省(市)二氧化碳排放现状与影响因素分.. 3页

2025年度个人住房装修贷款协议 7页

2025年商砼站绿色建材应用合作合同 10页

膜类材料标签产品加工溢胶原因分析 3页

聚丙烯纤维机制砂水泥砂浆早期抗裂性能试验研.. 3页

罗定电厂#2汽轮机#1轴瓦温度高的原因分析 3页

综采工作面液压支架回撤技术应用 3页