首页 > 代码库 > Josephus排列问题

Josephus排列问题

据说著名犹太历史学家 Josephus有过以下的故事:在罗马人占领乔塔帕特後,39 个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被人抓到,于是决定了一个自杀方式,41个人排成一个圆圈,由第1个人开始报数,每报数到第3人该人就必须自杀,然后再由下一个重新报数,直到所有人都自杀身亡为止。
然而Josephus 和他的朋友并不想遵从,Josephus要他的朋友先假装遵从,他将朋友与自己安排在第16个与第31个位置,于是逃过了这场死亡游戏。
Python代码如下:
#encoding:utf-8#!usr/bin/pythonimport sysdef winner(n,m):    s = 0    for i in range(1,n+1):        s = (s+m)%i    print The last winner is: ,s+1    def josephus(n,m):    a = []    b = []    for i in range(n):        a.append(i+1)    print The orignal sequence:    print a        j = 0    i = m - 1    while (j < n):                for k in range(len(a)):            if i >=len(a):                i = i - len(a)                break            b.append(a[i])            a.remove(a[i])            i += m-1                j += 1    print Josephus sequence(,n,people,space num is:,m,):        print b    if __name__ == "__main__":    josephus(41,3)    winner(41,3)

 

Josephus排列问题