约瑟夫环问题python解法 Python

约瑟夫环问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到k的那个人被杀掉；他的下一个人又从1开始报数，数到k的那个人又被杀掉；依此规律重复下去，直到圆桌周围的人只剩最后一个。
思路是：当k是1的时候，存活的是最后一个人，当k>=2的时候，构造一个n个元素的循环链表，然后依次杀掉第k个人，留下的最后一个是可以存活的人。代码如下：
【约瑟夫环问题python解法】

class Node(): def __init__(self,value,next=None): self.value=https://www.it610.com/article/value self.next=nextdef 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 rootdef showLink(root): tmp=root while True: print(tmp.value) tmp=tmp.next if tmp==None or tmp==root: breakdef 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('-----------------')

输出结果如下：

文章图片

-------------------------------------分界线-----------------------------------------
感谢大家建议，第一种方法是直观暴力裸搞，确实不太简洁，下面写出我的第二种方法，求模来搞起，代码少了一些，如下：

def josephus(n,k): if k==1: print('survive:',n) return p=0 people=list(range(1,n+1)) while True: if len(people)==1: break p=(p+(k-1))%len(people) print('kill:',people[p]) del people[p] print('survive:',people[0])if __name__=='__main__': josephus(10,4) josephus(10,2) josephus(10,1)

运行结果和上面一样。为了进一步对比性能，我用josephus(100000,4)测试，即n=100000，k=4。为了去掉IO消耗的时间干扰，把"kill:"的print注释掉，只输出最后的"survive:"结果，测试结果如下：

文章图片

结果表明，第一种循环链表的方式比第二种取模运算的方式要快，由于比例不是线性的，不能说是几倍，而且这个测试和python内部实现有关，换作C语言O3优化后结果就不一定一样了，所以测试结果不能说明什么哈~
转载请注明：转自http://blog.csdn.net/littlethunder/article/details/39182631