约瑟夫环经典问题的几种算法比较

《约瑟夫环经典问题的几种算法比较》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、研究与开发约瑟夫环经典问题的几种算法比较王永红$江苏畜牧兽医职业技术学院信息工程系&泰州**VW’’%摘要#约瑟夫环是数据结构中一个经典问题&通过解决约瑟夫环问题&可以熟悉掌握顺序表和链表的数据结构和相关运算&对提高数据结构的应用能力大有裨益)给出约瑟夫环的几种算法&讨论不同存储结构下实现的约瑟夫环算法&并从空间复杂度和时间复杂度进行了算法比较)关键词#算法*约瑟夫环*比较!引言L<,63=I51D0106M%G-L<,63=@95%1M)NNI51D0106MH%G-约瑟夫环问题#"$是数据结构中一个非常值得研究,H=,GOP%GQ"J的问题&特别是在线性表的

2、学习过程中经常碰到&学,RP+.&/010#,$G-生对此也饶有兴趣&通过对约瑟夫环问题的分析&对@95%1QQJ线性表的理解与应用大有裨益(7"约瑟夫环问题简介7I51D0106QQJ设编号为"/%的%$%&’%个人按顺时针方向围成FP234561QI51D0106GH+.&/010#,$JKK出列(添加到230一圈&首先第"个人从"开始顺时针报数(报)的人4561中$)为正整数%&令其出列)然后再从他的下一个人开+.&/010#,$H’J始&重新从"顺时针报数&报)的人&再令其出列)如此@95%1H’JKK计数器恢复下去&直到圈中所有人出列为止)求出列编号序

3、列#*$7)R9?P,H"J,MH%J,QQG#循环顺序表实现的算法;?,%1RPST%O/(O/S(,(234561#,$GJ?315?%J算法思想#7KK:943;<54"!建立约瑟夫环&将%个人存储在循环顺序表+中*算法思想#"若第,个人报数)后&则#!建立约瑟夫环&将%个人存储在循环顺序表+-出列的元素+.&/010#,$放在数组234561中*中*将+.&/010#,$置为’*"若第,个人报数后出列&则#现7将+.&/010#,$置于循环顺序表倒数的第,个位置代计#重复"步&直到圈中所有元素出列为止)上&而原来第,Q"个至倒数第,个元素依次向前移动算算

4、法如下#一个位置*机89,/:943;<54"=>,?@560?A3B+,41C+(363)3%1DE;3F230#重复"步&直到圈中剩下+.&/010#"$为止)总!4561G-算法如下#第,%1,H’(@95%1H’(I51D0106H’JKKI51D0106为出列的89,/:943;<54*=>,?@560?A3B+,41F+G-二总数&@95%1为计数器#".)$&,为约瑟夫环数组下标,%1,(U(;94H"J七收稿日期#!""#$%"$&"修稿日期#!""#$%!$!’五期作者简介#王永红$%’(($%&男&江苏泰州人&副教授&硕士&研究方向为软件技术

5、’多媒体网络技术"!"!"#$%&’"!()*+%,--!."研究与开发#$%&’()*’+(,*’--./尾结点%修改尾指针0$1(&0$123-".4’*0:-+)7Q6(J7<%J71E96-+)7Q6*’#&0$1((5.BB添加到J71E96尾部CB0$1(’*J7<%J71E96-+)7Q6(0:*67308973(:-+;<6<=0$1>*J7<%J71E96(J7<%J71E96-+)7Q6*#$%&?(0$1*?@’-"*?22.N$E)6(5*:-+;<6<=?>(:-+;<6<=?2">*0:(R:-+)7Q6*:-+;<6<=’>(673

6、08973*’#&VJ7<%:.0:(PU::*BB如果尾指针为空D链ABC#$%CB表没有结点了%0:置空D循环条件将结束#$%&’()*’+("*’--.A0%’)6#$D:-+;<6<=’>.*ABBF$170GE1L%76E%)*"算法的比较ABBF$170GE1,在空间复杂度方面%,H"算法增加了一存储出列在该算法中%从第"个人开始进行"-3报数%报序列的数据组%需要辅助空间%而且与问题的规模到3的人%即第’个位置%将:-+;<6<=’>置于倒数第’W

7、前移动&果仍然存储在环中%好处是没有增加额外的空间&与!循环链表实现的算法LH"算法相同的是%,H,算法也改变了原有的约瑟夫对,H"和,H,中的算法%都可以用链表实现&下面环&对,H"算法用不带头结点I的循环链表实现%出列的在时间复杂度方面%,H,算法从中可以看到%报数序列放在链表J71E96中&3的时间极短%比,H"算法用时少%问题在出列时%由算法思想’于用顺序表做删除操作%平均移动大约表中一半的元!建立约瑟夫环%将)个人存储在循环链表:素%影响效率&但是%两者都存在二重循环%算法中语中(句重复执行次数的数量级没有发生变化%即时间复杂"若第’个人)即0:结点*

8、报数3后%则’度"相同&