資源描述：
《多重集全排列算法的研究——模擬比較與匯編分析-本科畢業(yè)論文.doc》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。
1、本科畢業(yè)論文(科研訓(xùn)練、畢業(yè)設(shè)計(jì))題目：多重集全排列算法的研究——模擬比較與匯編分析姓名：學(xué)院：軟件學(xué)院系：軟件工程專業(yè)：軟件工程年級(jí)：學(xué)號(hào)：指導(dǎo)教師：職稱：年月摘要全排列問題是組合數(shù)學(xué)中的基礎(chǔ)問題，對它的研究已經(jīng)有幾個(gè)世紀(jì)的歷史了，幾百年來產(chǎn)生了很多種類的全排列算法。但是，大于25的全排列對于我們來說規(guī)模仍過于龐大，因此我們需要更快的算法。本文研究了眾多全排列的經(jīng)典算法，對它們進(jìn)行了分析和總結(jié)，在此基礎(chǔ)上提出了TWDRI算法，它突破了以往只有采用換位思想才能達(dá)到最快速度的傳統(tǒng)思想的束縛，以自身獨(dú)特的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)為基石，充
2、分利用遞歸方式的優(yōu)勢，取得遠(yuǎn)優(yōu)于其他同類算法的速度和內(nèi)存損耗。此外，不同于大多數(shù)排列產(chǎn)生算法只能處理數(shù)值的特性，本算法適用于各種不同字符的輸入情況，具有通用性。本文設(shè)計(jì)了平均時(shí)間測試模型，經(jīng)過大量的時(shí)間測試和模擬比較，得出TWDRI是目前速度最快算法的結(jié)論。為了進(jìn)一步驗(yàn)證該結(jié)論，我們選擇在匯編語言的環(huán)境下進(jìn)行數(shù)學(xué)分析，力求通過數(shù)學(xué)公式的比較證明TWDRI算法的優(yōu)越性。最后，本文還提出了該領(lǐng)域未來的一些研究方向。關(guān)鍵詞：全排列匯編數(shù)學(xué)模型多重集IIAbstractPermutationisthebasicprobleminc
3、ombinatorics，andtheresearchworkhasbeencarriedonforhundredsofyears,whichproducedmanytypesofmethodstodothepermutationcalculation.However,thepermutationofthenumberwhichislargerthan25isstillbeyondus.Asaresult,weneedaswifteralgorithm.Thisthesisdoestheresearchonthesecla
4、ssicalgorithms,analyzesandsummariesthem,onthebasisofwhichbringsouttheTWDRIalgorithms.Thismethodbrokethetraditionallimitsthatthelargestspeedcanonlybeachievedbyusingtheexchangemethods.Itisbasedonthespecialdesignofdatastructureandmakesthebestuseoftheadvantagesofrecur
5、sion,that’showitobtainsthespeedandmemorycostwhichcanhardlybeachievedbyitscounterparts.Moreover,differentfromthetraitsofmostpermutationsthatthealgorithmsproducedcanonlydealwithdata,thiscalculationisquiteuniversal,foritsuitsdifferententeringsituationsofallkindsofstr
6、ing.TheaveragetimetestmodelisdesignedinthisthesisandwecanconcludethatTWDGIisthefastestalgorithminthepresentworldafteralargeamountoftimetestsandsimulationcomparisonshavebeenpracticed.Tofurthercheckthisconclusion,wedecidetodothemathematicalanalysisintheenvironmentof
7、compilationlanguage,tryingtoprovethesuperiorityofTWDRIbythecomparisonsofmathematicalformulas.Intheend,thisthesisalsoprovidessomehintsaboutthefutureresearchdirectioninthisfield.Keywords:Permutation;Assembly;MathematicsModel;MultisetII目錄第一章緒論11.1研究背景及意義11.2基本概念21.3本
8、文主要內(nèi)容41.4本文組織結(jié)構(gòu)4第二章經(jīng)典算法52.1基于相鄰交換的算法52.1.1簡介52.1.2代表算法62.2基于遞歸的算法72.2.1簡介82.2.2代表算法82.3基于迭代的算法92.3.1簡介102.3.2代表算法102.4字典序類算法112.4.1簡介112.4.2代表算法122.5其他1
