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年度汽车修理厂车辆维修全面免责服务协议.. 9页

2025年度水利工程款支付与生态补偿协议 9页

2025年度民宿室内设计纯设计服务协议 9页

2025年度校园外卖代运营项目合同 9页

2025年3月孙丽鼻咽癌放疗护理攻略 23页

2025年度智能电网合伙经营合同 7页

2025年度智能房产交易委托代理协议书的意义与.. 8页

2025年度智能家居系统拓扑分析与智能化改造合.. 9页

2025年度智能家居产品研发委托代理合同 9页

2025年度智能化社区保安承包管理合同 8页

2025年度智能制造专利申请代理服务契约 9页

2025年度智慧家居系统合同财务审核要点与智能.. 9页

2025年度时尚秀场商业拍摄制作合同 9页

2025年度施工人员安全培训及考核合同 8页

2025年度新能源电动车销售业务合作协议 9页

2025年度新能源汽车专用运输服务合同模板 9页

2025年度新型城镇化小区地下车位租赁管理合同.. 8页

2025年度文化旅游项目业务承包合同 9页

2025年度文化创意产业孵化劳务咨询服务合同 8页

2025年度数据中心工程结算付款合作协议 7页

2025年度教育机构教师教学质量评估与改进合同.. 8页

2025年度教育培训机构品牌推广人员劳动合同 8页

2025年度房屋买卖不过户产权变更及过户风险防.. 8页

2025年度房地产众筹合作分红执行合同 7页

2025年度户外用品区域代理销售合同 9页

临床常用护理技术注意事项 85页

2025年度建筑工程架架子工人员技能培训及用工.. 8页

2025年度店铺转让协议版-医疗健康店铺转让 9页

2025年度广告宣传合作终止合同解除通知书 8页

2025年度幼儿园教师实习期幼儿教育法律法规聘.. 7页