Application of recursive algorithm in extended Josephus problem

doi:10.3778/j.issn.1002-8331.2010.34.019

Computer Engineering and Applications ›› 2010, Vol. 46 ›› Issue (34): 62-63.DOI: 10.3778/j.issn.1002-8331.2010.34.019

• 研发、设计、测试 • Previous Articles Next Articles

Application of recursive algorithm in extended Josephus problem

PAN Da-zhi^1，2，LIU Zhi-bin¹

1.School of Sciences，Southwest Petroleum University，Chengdu 610500，China
2.College of Mathematic and Information，China West Normal University，Nanchong，Sichuan 637000，China

Received:2010-04-28 Revised:2010-08-23 Online:2010-12-01 Published:2010-12-01
Contact: PAN Da-zhi

递推算法在扩展约瑟夫环问题中的应用

潘大志^1，2，刘志斌¹

1.西南石油大学理学院，成都 610500
2.西华师范大学数学与信息学院，四川南充 637000

通讯作者: 潘大志

Abstract

Abstract: This paper expands the Josephus problem and solves the expansion problem with the ideas of recursive algorithm and static list.Ones get its recursive express and algorithm，which time complexity is O（n）.Running examples show that its speed of solving problems is faster greatly than the normal simulation algorithm’s.

Key words: the extended Josephus problem, recursive algorithm, simulation algorithm, static list

摘要： 对约瑟夫环问题进行扩展，并将递推算法和静态链表的思想用于解决扩展问题。得到了扩展问题的递推表达式，给出了求解扩展问题的算法，其时间复杂度为O（n）。运行实例表明，与常规的模拟算法相比，大大提高了求解问题的速度。

关键词: 扩展约瑟夫环问题, 递推算法, 模拟算法, 静态链表

CLC Number:

TP311.11

PAN Da-zhi^1，2，LIU Zhi-bin¹. Application of recursive algorithm in extended Josephus problem[J]. Computer Engineering and Applications, 2010, 46(34): 62-63.

潘大志^1，2，刘志斌¹. 递推算法在扩展约瑟夫环问题中的应用[J]. 计算机工程与应用, 2010, 46(34): 62-63.

[1]	XU Qili. Algorithm Design of Equilibrium Bidding Strategy in Bargaining Game [J]. Computer Engineering and Applications, 2020, 56(21): 170-175.
[2]	JING Shaoxue. Two-stage recursive Bayesian parameter identification algorithm with covariance resetting [J]. Computer Engineering and Applications, 2017, 53(6): 60-66.
[3]	WANG Tingting，YANG Qin，HUANG Lin，WANG Lu，HUANG Yiping. Optimization scheduling of retail checkout based on customers’ behavior [J]. Computer Engineering and Applications, 2016, 52(3): 266-270.
[4]	ZHU Lei1, JI Feng2, BAI Ruilin1. Thresholding segmentation based on gray-gradient 2-D symmetric Tsallis cross entropy [J]. Computer Engineering and Applications, 2015, 51(19): 194-199.
[5]	LI Lei, GUO Rui, XIE Xiaolu. Research for combination algorithm of interval multiple attribute group decision making [J]. Computer Engineering and Applications, 2015, 51(17): 48-52.
[6]	CHENG Limei, YUAN Wei, YAO Ruoxia. Constructing moving frames and differential invariants and its applications in pattern recognition [J]. Computer Engineering and Applications, 2013, 49(19): 147-152.
[7]	WANG Hongjiang1, GUO Huijun1, Li Junhuai2. Optimization algorithm of TDE based on ultrasonic echo envelope correlation [J]. Computer Engineering and Applications, 2012, 48(20): 154-157.
[8]	XU Jiying. Hybrid heuristic algorithm for rectangle packing problem [J]. Computer Engineering and Applications, 2012, 48(13): 234-239.
[9]	LI Yin-kui. Algorithm for computing rupture degree of unicycle graphs [J]. Computer Engineering and Applications, 2010, 46(26): 38-39.
[10]	LI Yu-hua,CUI Feng-yun,LIU Xiao-qing. Level iterative algorithm for towers of Hanoi puzzle [J]. Computer Engineering and Applications, 2008, 44(35): 73-75.
[11]	ZHANG Kun¹,ZHANG You-zhi². Recursive algorithm for calculating eigenvalues of real symmetric matrix based on LDL^T decomposition [J]. Computer Engineering and Applications, 2008, 44(3): 78-80.

Application of recursive algorithm in extended Josephus problem

递推算法在扩展约瑟夫环问题中的应用

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 11

Recommended Articles

Metrics