Josephus问题的算法设计与应用研究.PDF

计算机工程与应用 , ()61 ComputerEngineeringandApplications 2007431 Josephus问题的算法设计与应用研究 陈海山,钱 锋,田 英,雷 鸣 , , , CHENHai-shanQIANFengTIANYingLEIMing 厦门大学 软件学院,福建 厦门 361005 , , , , SoftwareSchoolXiamenUniversityXiamenFujian361005China : E-mailhschen@ CHENHai-shan, , , QIANFengTIANYingetal.Algorithm designandapplicationresearchofJosephusproblem.Computer , , (): EngineeringandApplications2007431 61-64. : Abstract Josephusproblem isoneoftheheadstreamsofcombinatorics.TherearesomanymethodstodescripttheJosephus , , problem now.Inthispaperaftersomanyexperimentsandanalysisacommonmethodissummarizedandanalgorithm is , , designedwhichisbasedoncircularlinkedlist.Thedatasourceofthealgorithm isfrom textfilesothepracticabilityis , enhanced.Andsincethecircularlinkedlistiscreatedbasedontheascendantsequenceofthedatalistsothedatacanbe classifiedeffectivelytomaketheJosephusdatalisttobedistributedsymmetricallyandnoduplicate.Someapplicationsof , , Josephusproblemisofferedwhichincludethetestpapercombinationalgorithmincommontestquestionsdatabaseandfindinga , , , listofdatawhichbelongstocertainrangefromasetofdataetc. : ; ; ; KeywordsJosephusproblemalgorithmdesigndynamiccircularlinkedlisttextfile 摘 要: 问题是组合数学的发展源头之一。关于 问题的描述形式甚多。文章通过实验和分析,总结了一个通用性 Josephus Josephus 的描述形式,并给出了基于循环链表的算法设计。算法的数据源从文本文件中获取,增强了算法的实用性;根据数据元素值的递增 顺序建立循环链表,能够有效地分类数据,使Josephus数据序列均匀分布且不重复。文章还给出了Josephus问题的若干个应用实