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

最近更新

《物流信息化》 31页

大数据与社会治理模式的创新-全面剖析 30页

代谢途径中关键蛋白质鉴定-全面剖析 31页

催化氧化法处理含氰废水机理的探讨 2页

俄罗斯岩土工程研究成果和发展水平 2页

低阶煤热演化生烃的模拟试验研究 2页

位置灵敏半导体探测器的测试原理和方法 2页

煤矿电气产品购销合同协议 7页

以成组技术为基础的成批生产装配自动化 2页

深圳房屋租赁合同电子版样本转让与许可合同 6页

从卫星影像上分析海南岛第四纪玄武岩的分期 2页

介绍一种打印人体生物节律曲线的方法 2页

人工挖孔灌注桩在高速公路施工中的应用 2页

交通运输行业信息化绩效评价体系研究 2页

井下刮板输送机电动机故障原因与处理方法 2页

云南新型工业化与信息化融合问题探讨 2页

汽油供应合同协议书范文 6页

为提高劳动科学研究水平而努力奋斗 2页

毕业生档案托管服务合同协议书样本 7页

中小企业电子商务绩效衡量研究 2页

中国纯碱工业科学技术专家网正式建立 2页

中国建筑科学研究院工程抗震研究所简介 2页

中厚度圆浮板自由振动的一个解析解 2页

东欧经济现状和对西方采取的对策 2页

不溶性阳极与离子交换系统组合的回收镍盐新技.. 2页

上海市肿瘤防治研究学术交流会报道 2页

2025年幼儿园教师活动方案大全 27页

2025年吕梁职业技术学院单招职业适应性测试题.. 74页

煤矿春季预防性电气试验试措施样板 18页

2025届高考模拟作文“时间管理”升格导写 5页