文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 工程科技 > 信息与通信 > 约瑟夫环次序解的链表模算法
侵权投诉

约瑟夫环次序解的链表模算法

第2 9卷第 1期 2 0 1 3年 2月 文章编号: 1 6 7 4— 0 8 7 4 ( 2 0 1 3)叭一 0 0 1 3 - 0 3

山西大同大学学报 (自然科学版) J o u r n a l o f S h a n x i D a t o n g U n i v e r s i t y ( N a t u r a l S c i e n c e )

V0 1 . 2 9 . No . I

F e b 2 Ol 3

约瑟夫环次序解的链表模算法 白 宇 (山西大同大学数学与计算机科学学院,山西大同 0 3 7 0 0 9 ) 摘要:对经典问题“约瑟夫环”进行分析,提出了一种全新的基于链表模运算的高速算法,给出了在务件遍历

算法设计中运用模运算的一般思路,同时进行了算法分析和实验测试。 关键词:约瑟夫环;链表计数;模运算 中图分类号: T P 3 1 2 . 1 2 文献标识码: A

经典问题“约瑟夫环”是由古罗马的史学家 F l a v i u s J o s e p h I l S提出的,一般描述如下:已知 n个元素,以编号 1, 2,3,…, n分别表示,顺序排列成一个环,从编号为 l的元素依次计数,计数到 m的元素出列;再由第 m+ 1个元素重新计数,同样计

由于需出列 n— 1个元素,且每个元素需计数 m

次,其时问复杂度为 D 2 ),而当该算法运行到后期时,线性表中空位逐渐增多,而空位需进行比较判定,以决定是否计数, m计数的命中率将逐渐降低,根据空位数量可得命中率为: p ( l, 2, 3,…, ), ( 1 )

数到 m的元素出列;依此规律重复下去,直到环中仅剩余一个元素,求出列次序I l 1 o该问题的次序解在随机数产生理论以及动态规划理论中有一定的应用, 但目前通用的次序解算法其时间复杂度均为 0 2 )【, 效率较低,文章通过数学分析,找出其效率较低的原因,从而采用新的计数方法,对循环链表进行模运算,使得该问题的次序解时间复杂度降低为 D ( 阶。

( 1 )式中为计数轮数,一 1表示第 i轮的空位 数量。由( 1 )式可得该算法的实际比较判定次数为: n—l

c= i=1

— ————

} — . ——一

。

( 2 )

m+ ( i一 1 )

由( 2 )式展开得: n+2 m m c: (一 1

), n +— m— n— ̄3 ———

1 算法分析 求解“约瑟夫环”有两种不同的要求:

—

—

一

。

l

( 3 )

f 1 )仅求解最后剩余元素的编号,此时可以使用 时间复杂度为 D㈨的递归公式: f 1 )= l ( n= 1 )

由( 3 )式可知该算法随 m、 n的增大,实际比较判定次数呈 3次幂级增长 f 4】。

其二,链表计数算法。该算法同样采用线性表实现,但线性表中的每一个元素存放的是下一元素 的索引值,由此构成首尾相接的循环链表。计数方式与线性表计数算法相同,当有元素出列后,修改 链表结构,删除已出列的元素,即修改该元素前一元素的索引,使其指向该元素的下一元素。虽然该

I。, ( n )= ( ., ( n一 1 )+ m— 1 ) o r o d n+ l ( n> 1 ),

其中为环中元素总数,m为出列数。显然, 使用该公式无法求得次序解,即次序出列数。 ( 2 )采用循环计数法模拟出列过程,可以求得次序解。当前通用的算法有两种:

算法时间复杂度仍为 D 2 ),但线性表中不存在空 位,实际比较判定次数为: c - m n, ( 4 )

其一,线性表计数算法。该算法首先定义一个长度为 n的线性表,其中放置 1, 2, 3,…,n,然后以n+ l为模逐一判断该线性表中每一个元素,如该元素尚未出列(不为 0 ),计数值累加 1,直到计数值等于 m时,将对应元素出列f置0 ),并输出该元素, 直到输出 n一 1个元素为止。 收稿日期: 2 0 1 2— 1 0— 1 5

( 4 )式的实际比较判定次数为 n 阶,要比( 3 )式 小得多。

当 m和 n较大时,上述两种算法性能将变得

较差,那么是否存在一种时间复杂度为 D ( n )的求次

作者简介:向字( 1 9 7 6一 ),男,山西大同人,硕士,讲师,研究方向:图论算法和并行算法。

约瑟夫环次序解的链表模算法

第1页

你可能喜欢

热门文档

相关文档

  • 链表处理约瑟夫环——算法分析与设计算法实例C语言

    (LinkList *list,int m) //约瑟夫环算法 { LinkList p,q; int i; q=p=*list; while(q->next!=p) q=q->next; puts("参加游戏的人按照如下顺序出...

  • 约瑟夫环的循环链表实现

    约瑟夫环的循环链表实现 #include <stdio.h> #include <stdlib.h> #define ...("\n 被选出的次序:\n"); // // 进行操作 // pTwo = pHead; pOne =...

  • 约瑟夫环链表方法

    p->link=head 解决问题的核心步骤: (程序的基本算法) 1.建立一个具有 n 个... 约瑟夫环单循环链表的实... 2页 免费 约瑟夫环次序解的链表模... 暂无评价...

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

    约瑟夫环经典问题的几种算法比较_工学_高等教育_教育专区。约瑟夫环... 约瑟夫环问题算法 2页 免费 约瑟夫环次序解的链表模... 暂无评价 3页 ...

  • 用循环链表实现约瑟夫环问题

    用循环链表实现约瑟夫环问题_计算机软件及应用_IT/计算机_专业资料。《软件技术...-4- 期末大作业报告书 (2) (3) 运算符重载的方法。通过查阅 C++数据予以...

  • 用循环链表实现约瑟夫环

    程序清单 约瑟夫环的实现 学号 200900800276 4.算法说明 实验日期 2011 年 3 ...设计程序输出出列顺序。 3.程序清单 : Josepus.h #ifndef _TRIPLET_H #define...

  • 用双向循环链表求解约瑟夫环

    用双向循环链表求解约瑟夫环 学校:东北大学 专业:...(1)开始对双向循环链表的删除操作的指针改变顺序出现...对指针和链表了 解得更加透彻,掌握得更加牢固; (2...

  • 约瑟夫环的实现

    链表模块 约瑟夫环的实现 5.约瑟夫环中出列一个人的伪码算法: 约瑟夫环的实现(...5.当程序大体完成时,却又在调试过程中发现出列次序总是错误的,才想到实现约瑟夫...

  • c语言实现约瑟夫环问题

    建立一个不带头结点的循环链表并由头指针 first 指示 3.算法设计 1、 工作指针...运行、测试与分析 (二)采用顺序存储结构如何实现约瑟夫环问题代码和解释 #include...

  • 单向循环链表实现约瑟夫环

    单向循环链表实现约瑟夫环_IT/计算机_专业资料。 CirLinkList(单向循环链表实现...于是,约瑟夫斯建议每个人应该轮流杀死他旁边的人,而这个顺序是由抽签决定的。...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email