多重集全排列算法研究与汇编分析-毕业论文.doc

《多重集全排列算法研究与汇编分析-毕业论文.doc》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、本科毕业论文(科研训练、毕业设计)题目：多重集全排列算法研究与汇编分析姓名：学院：软件学院系：软件工程系专业：软件工程年级：学号：指导教师：职称：年月摘要全排列产生算法已有悠久的历史，其涉及的理论研究领域和应用范围相当广泛。数百年来，对全排列问题的研究一直都未间断，计算机的诞生使该问题得到了更多的关注且有了巨大的发展。本文对全排列算法前进过程中产生的算法进行了简要的分类介绍，并对各类中的经典算法进行了分析说明。随后提出一种全新的全排列产生算法——TWDRI,该算法能同时对多重集和单集进行全排列，并且

2、性能优异。一个对全排列算法进行比较的平均时间测试模型将在文中给出，用以证明TWDRI算法的优越性。经过大量模拟，其结果显示TWDRI算法比世界上现有的其他全排列算法速度都快。为了在理论上进一步论证该比较结果的科学性与正确性，一个在汇编层次分析算法的设想在文中提出，其探索也取得了初步的成果。关键词：多重集全排列算法汇编IVAbstractPermutationsgenerationenjoysalonghistoricalstanding.Ittouchesmanytheoreticalresearc

3、handapplicationdomains.Forcenturies,thestudyonpermutationgenerationhasneverbeenceased.Furthermore,moreattentionshavebeenpaidonitsincetheinventionofcomputers,thustremendousdevelopmentofithasbeenachieved.Inthisthesis,thewholepermutationgenerationalgorith

4、msthatappearedinhistorywillbeintroducedbycategory，andtheclassicalgorithmofeachkindwillalsobedescribedrespectively.ThenanewalgorithmforpermutationgenerationnamedTWDRIwillbeputforward,whichcanbesimultaneouslyappliedtomultisetandsinglesetwithexcellentperf

5、ormance.Moreover,acalculationmodelofaveragetimewillbeintroduced,inordertocompareallthepermutationgenerationalgorithmsandprovethesuperiorityofTWDRIalgorithm.Afteralotofsimulations,theresultsshowthatTWDRIalgorithmrunsfasterthantheotherexistingworld-widep

6、ermutationgenerationalgorithms.Tofurtherprovethatthiscomparisonisbothscientificandcorrectintheory,anassumptionbasedonassemblyanalysisisalsogiven,andhasgainedpreliminaryresultsinrealpractice.Keywords：multiset;permutation;algorithm;assemblyIV目录第一章绪论11.1课

7、题背景与意义11.2主要研究内容11.3本文结构2第二章全排列概述及经典算法32.1基本定义32.2按字典序排法32.3格雷码与相邻交换52.4Loopless算法72.5递归算法82.6迭代算法102.7TWDRI算法12第三章平均时间测试模拟比较143.1平均时间测试模型143.1.1模型介绍143.1.2平均时间测试程序173.2模拟比较结果183.2.1比较方案说明193.2.2多重集算法的平均时间和内存花销比较203.2.3所有算法同一单集输入下的时间和内存花销比较213.2.4TWDRI

8、算法与其他算法的比较分析23第四章汇编层次分析比较的探索264.1汇编层次比较的必要性264.2分析方案的选择274.3分析举例27第五章总结与展望31致谢语32参考文献33IVContentsChapter1Introduction11.1BackgroundandConstruction11.2MainContent11.3ChaptersStructure2Chapter2PermutationSummaryandClassicalAlgorithms32.1B