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

Application of recursive algorithm in extended Josephus problem

作　　者：潘大志[1,2] 刘志斌[1] 

机构地区：[1]西南石油大学理学院,成都610500 [2]西华师范大学数学与信息学院,四川南充637000

出　　处：《计算机工程与应用》2010年第34期62-63,106,共3页Computer Engineering and Applications

基　　金：国家自然科学基金(No.50874094);四川省教育厅青年基金(No.07ZB087)~~

摘　　要：对约瑟夫环问题进行扩展,并将递推算法和静态链表的思想用于解决扩展问题。得到了扩展问题的递推表达式,给出了求解扩展问题的算法,其时间复杂度为O(n)。运行实例表明,与常规的模拟算法相比,大大提高了求解问题的速度。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）.Rurming examples show that its speed of solving problems is faster greatly than the normal simulation algorithm＇s.

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

分 类 号：TP311.11[自动化与计算机技术—计算机软件与理论]