189 8069 5689
这篇文章将为大家详细讲解有关如何python解约瑟夫环问题，文章内容质量较高，因此小编分享给大家做个参考，希望大家阅读完这篇文章后对相关知识有一定的了解。
成都创新互联是一家集网站建设,姜堰企业网站建设,姜堰品牌网站建设,网站定制,姜堰网站建设报价,网络营销,网络优化,姜堰网站推广为一体的创新建站企业，帮助传统企业提升企业形象加强企业竞争力。可充分满足这一群体相比中小企业更为丰富、高端、多元的互联网需求。同时我们时刻保持专业、时尚、前沿，时刻以成就客户成长自我，坚持不断学习、思考、沉淀、净化自己，让我们为更多的企业打造出实用型网站。
约瑟夫环问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到k的那个人被杀掉；他的下一个人又从1开始报数，数到k的那个人又被杀掉；依此规律重复下去，直到圆桌周围的人只剩最后一个。
思路是：当k是1的时候，存活的是最后一个人，当k>=2的时候，构造一个n个元素的循环链表，然后依次杀掉第k个人，留下的最后一个是可以存活的人。代码如下：
class Node():
def __init__(self,value,next=None):
self.value=value
self.next=next
def createLink(n):
if n<=0:
return False
if n==1:
return Node(1)
else:
root=Node(1)
tmp=root
for i in range(2,n+1):
tmp.next=Node(i)
tmp=tmp.next
tmp.next=root
return root
def showLink(root):
tmp=root
while True:
print(tmp.value)
tmp=tmp.next
if tmp==None or tmp==root:
break
def josephus(n,k):
if k==1:
print('survive:',n)
return
root=createLink(n)
tmp=root
while True:
for i in range(k-2):
tmp=tmp.next
print('kill:',tmp.next.value)
tmp.next=tmp.next.next
tmp=tmp.next
if tmp.next==tmp:
break
print('survive:',tmp.value)
if __name__=='__main__':
josephus(10,4)
print('-----------------')
josephus(10,2)
print('-----------------')
josephus(10,1)
print('-----------------')输出结果如下：
结果表明，第一种循环链表的方式比第二种取模运算的方式要快，由于比例不是线性的，不能说是几倍，而且这个测试和python内部实现有关，换作C语言O3优化后结果就不一定一样了，所以测试结果不能说明什么哈~
关于如何python解约瑟夫环问题就分享到这里了，希望以上内容可以对大家有一定的帮助，可以学到更多知识。如果觉得文章不错，可以把它分享出去让更多的人看到。
