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

最近更新

内蒙古2018版保育员初级考试试题试卷及答案 11页

内蒙古2018年保育员三级专业能力考试试题试卷.. 10页

关爱留守儿童暑期社会实践心得体会与关爱留守.. 16页

关于读书活动心得体会与关于读书演讲稿汇编 7页

交警大队开展交通安全隐患排查整治工作总结与.. 5页

云南省2020版保育员四级业务能力考试试题试卷.. 11页

2020版幼儿园小班保育员上学期考试试题试卷及.. 10页

2025年度奶茶店员工劳动合同解除备案与执行合.. 8页

2025年度夫妻忠诚协议及出轨赔偿条款合同 7页

2025年度太阳能设备维修服务委托协议 8页

2025年度大连正规房产买卖合同毁约处理细则 8页

2025年度大学生实习实训项目实习实训基地建设.. 9页

2025年度大型挂车租赁及全程物流跟踪服务合同.. 8页

2025年度外贸企业供应链金融合作协议书 8页

2025年度塑料管材防腐蚀性能购销合同 9页

2025年度城市综合体停车位使用权转让协议 7页

2025年度城市文化旅游节庆活动宣传策划合同 9页

2025年度城市地下管线探测与修复劳务合同承担.. 9页

2025年度城乡供水一体化项目供用水合同模板 9页

2025年度地基房屋买卖及配套设施管理合作协议.. 10页

2025年度地下室房屋租赁与艺术展览合作合同 8页

2025年度土建工程绿色施工废弃物处理合同 9页

2025年度土地流转居间与农业生态循环经济发展.. 9页

2025年度土地厂房租赁合同:航空航天装备维修.. 8页

2025年度国际贸易实习生合作协议范本 8页

XX学校义务教育优质均衡发展创建实施方案范文.. 8页

顺丁烯二酸酐工艺规程 25页

节后复工复产安全生产培训记录 6页

核电知识竞赛试题及答案 7页

(LARS)评价量表 1页