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

看看大大的

比较自己写的。。。

1. def YSF(n ,k):
   
2.     index = 0
   
3.     counts = 1
   
4.     a = list(range(1, n+1))
   
5.     while len(a) > 1:
   
6.         counts += 1
   
7.         index += 1
   
8.         if index == len(a):
   
9.             index = 0
   
10.         if counts == k:
    
11.             a.remove(a[index])
    
12.             counts = 1
    
13.             if index == len(a):
    
14.                 index = 0
    
15.         print(index, len(a), a)
    
16. 
    
17. 
    
18. YSF(100,3)
    

复制代码

Remorseless

学习了

daxia

学习！！！

优等生

学习一下

小银锤

学习

Jonin616

1. def Josephloop(m,k):
   
2.     i = 0
   
3.     step = 0
   
4.     Joseph = []
   
5.     flag = 0
   
6.     n = 0
   
7.     for each in range(m):
   
8.         Joseph.append(1)
   
9.     while flag != m:
   
10.         if m - flag > 2:
    
11.             if Joseph[i] == 1:
    
12.                 step = step + 1
    
13.             i = i+1
    
14.             if i == m:
    
15.                 i = 0
    
16.             if step == k:
    
17.                 Joseph[i - 1] = 0
    
18.                 flag = flag + 1
    
19.                 step = 0
    
20.         else:
    
21.             for each in range(m):
    
22.                 if Joseph[each] == 1:
    
23.                     flag = flag + 1
    
24.                     print(each)
    

复制代码

类十三

好厉害

zcr林枫

厉害

余欲渔

1. n=100
   
2. k=3
   
3. sl=[i for i in range(n)]
   
4. def ysf(sl,k,qsw):
   
5.     n=len(sl)
   
6.     nqsw=(qsw+n)%k
   
7.     if n<k:
   
8.         for i in sl:
   
9.             print(i+1,end=' ')
   
10.         return 1
    
11.     nsl=sl[k-qsw-1::k]
    
12.     for i in nsl:
    
13.         sl.remove(i)
    
14.     ysf(sl,k,nqsw)
    
15. 
    
16. ysf(sl,k,0)

复制代码

ooxx7788

看看答案呢

ggshen

23333333333333333333333333333

shigure_takimi

1. def f(n, k):
   
2.     if n >= 1:
   
3.         persons = list(range(1, n+1))
   
4.         quitList = []
   
5.         currentNumber = 1
   
6.         while len(persons) != 1:
   
7.             if currentNumber == k:
   
8.                 quitList.append(persons[0])
   
9.                 del persons[0]
   
10.                 currentNumber = 1
    
11.             else:
    
12.                 persons.append(persons.pop(0))
    
13.                 currentNumber += 1
    
14.         print('--> 原来第%d号人将留下来…' % persons[0])
    
15.         print('--> 被杀死的人是：', quitList)
    
16. 
    
17. 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])
跟大神  还差很多  到最后我的这个 列表会很长