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-zhi1,2,LIU Zhi-bin1   

  1. 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   

  1. 1.西南石油大学 理学院,成都 610500
    2.西华师范大学 数学与信息学院,四川 南充 637000
  • 通讯作者: 潘大志

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: