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

最近更新

《真理诞生于一百个问号之后》第二课时 15页

人教版高中物理课件第十三章光13.1光的折射 38页

关于民族地区用活财政资金问题的探讨 2页

关于日本鲚属(Coilia)鱼类分类位置的探讨 2页

关于改良A.D.A湿法脱硫机理的探讨 2页

关于推广合同能源管理机制的几点思考 2页

关于我国粮棉生产徘徊不前的政策因素分析 2页

2025年直流离子风机项目建议书 58页

2025年特种工程塑料项目建议书 51页

2025年电动机合作协议书 54页

关于岗位培训目的内容方法的探讨 2页

关于实现我区农村信贷宏观调控目标的思考 2页

关于多级负反馈放大器的分析方法 2页

关于在铁路混凝土工程中推广应用减水剂的探讨.. 2页

2025年特发性肺纤维化病情急剧恶化 23页

《新闻写作》 22页

关于中国第四纪海面变化及其特点研究的进展 2页

关于《小企业会计准则》相关问题的思考 2页

2025年护理职业素养与礼仪规范教程 71页

兰花同宝资源整合矿井采煤方法及装备选型研究.. 2页

公路建设投资项目风险综合评估方法研究 2页

全芳香性螺环正碳酸酯的聚合及其产物的差热分.. 2页

全国首届医药技术交易信息交流会在长沙举行 2页

全国电力设备可靠性技术讨论会在宁波召开 2页

全国土石坝情报网“技术情报交流会”在湖南岳.. 2页

人教版品德与社会小学四年级上册《做个聪明的.. 11页

光催化技术在净化室内空气上的研究进展 2页

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

服装设计合作协议书 5页

煤炭资源地质勘查设计编写提纲 14页