python小练习（058）：10来行代码求解约瑟夫环问题

jerryxjr1220

约瑟夫环问题的历史背景：

这个问题是以弗拉维奥·约瑟夫斯命名的，它是1世纪的一名犹太历史学家。他在自己的日记中写道，他和他的40个战友被罗马军队包围在洞中。他们讨论是自杀还是被俘，最终决定自杀，并以抽签的方式决定谁杀掉谁。约瑟夫斯和另外一个人是最后两个留下的人。约瑟夫斯说服了那个人，他们将向罗马军队投降，不再自杀。约瑟夫斯把他的存活归因于运气或天意，他不知道是哪一个。

约瑟夫环的问题描述：

约瑟夫斯问题（有时也称为约瑟夫斯置换），是一个出现在计算机科学和数学中的问题。在计算机编程的算法中，类似问题又称为约瑟夫环。
有 n个囚犯站成一个圆圈，准备处决。首先从一个人开始，越过  k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过 k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。
问题是，给定了n和 k，一开始要站在什么地方才能避免被处决？

比较简单的做法是用循环单链表模拟整个过程，时间复杂度是O(n*m)。如果只是想求得最后剩下的人，则可以用数学推导的方式得出公式。且先看看模拟过程的解法。

本帖的解法就是用循环单链表模拟的整个过程，如果当n和m比较大是，速度会比较慢，但是程序很简洁。

源代码：

游客，如果您要查看本帖隐藏内容请回复

比如总共有100个人，每3个人必须被处死一个，则整个被处死的队列是：
3 6 9 12 15 18 21 24 27 30 33 36 39 42 45 48 51 54 57 60 63 66 69 72 75 78 81 84 87 90 93 96 99 2 7 11 16 20 25 29 34 38 43 47 52 56 61 65 70 74 79 83 88 92 97 1 8 14 22 28 35 41 49 55 62 68 76 82 89 95 4 13 23 32 44 53 64 73 85 94 5 19 37 50 67 80 98 17 40 59 86 10 46 77 26 71 31 100 58 91

如果最后一个可以存活，那么你应该站在第91个的位置。

brokenbone

看下

小Q学Python

看看大大的

比较自己写的。。。

def YSF(n ,k):
    index = 0
    counts = 1
    a = list(range(1, n+1))
    while len(a) > 1:
        counts += 1
        index += 1
        if index == len(a):
            index = 0
        if counts == k:
            a.remove(a[index])
            counts = 1
            if index == len(a):
                index = 0
        print(index, len(a), a)


YSF(100,3)

Remorseless

学习了

daxia

学习！！！

优等生

学习一下

小银锤

学习

Jonin616

def Josephloop(m,k):
    i = 0
    step = 0
    Joseph = []
    flag = 0
    n = 0
    for each in range(m):
        Joseph.append(1)
    while flag != m:
        if m - flag > 2:
            if Joseph[i] == 1:
                step = step + 1
            i = i+1
            if i == m:
                i = 0
            if step == k:
                Joseph[i - 1] = 0
                flag = flag + 1
                step = 0
        else:
            for each in range(m):
                if Joseph[each] == 1:
                    flag = flag + 1
                    print(each)

类十三

好厉害

zcr林枫

厉害

余欲渔

n=100
k=3
sl=[i for i in range(n)]
def ysf(sl,k,qsw):
    n=len(sl)
    nqsw=(qsw+n)%k
    if n<k:
        for i in sl:
            print(i+1,end=' ')
        return 1
    nsl=sl[k-qsw-1::k]
    for i in nsl:
        sl.remove(i)
    ysf(sl,k,nqsw)

ysf(sl,k,0)

ooxx7788

看看答案呢

ggshen

23333333333333333333333333333

shigure_takimi

def f(n, k):
    if n >= 1:
        persons = list(range(1, n+1))
        quitList = []
        currentNumber = 1
        while len(persons) != 1:
            if currentNumber == k:
                quitList.append(persons[0])
                del persons[0]
                currentNumber = 1
            else:
                persons.append(persons.pop(0))
                currentNumber += 1
        print('--> 原来第%d号人将留下来…' % persons[0])
        print('--> 被杀死的人是：', quitList)

f(100, 3)

willLin

学习一下

和vvv

不错哦

bush牛

试着写了一下，但感觉我写的不符合The Zen of Python.学习下你的方法。

suloman

n=100
k=3
x=[]
for i in range(n):
    x.append(i+1)
a=0
temp=0


for i in x:
    a+=1
    if a==k :
        a=0
        print(i)
    else:
        x.append(i)
    if temp==i :
        break
    temp=i
print(x[-1])


每次把没死的人  填到序列的结尾  
每数k个人 跳过
直到最后 序列出现重复为止

suloman

学习了  精简一下
n=100
k=3
x=list(range(1,n+1))
a=0
for i in x:
    a+=1
    if a==k :
        a=0
        print(i)
    else:
        x.append(i)
print("最后一人",x[-1])
跟大神  还差很多  到最后我的这个 列表会很长