论坛 › Python交流 › python小练习（058）：10来行代码求解约瑟夫环问题

jerryxjr1220 发表于 2017-1-6 12:43:50

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

本帖最后由 jerryxjr1220 于 2017-1-10 12:59 编辑

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

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

约瑟夫环的问题描述：

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

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

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

源代码：
**** Hidden Message *****

比如总共有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 发表于 2017-1-6 15:14:37

看下{:10_249:}

小Q学Python 发表于 2017-1-6 17:04:53

本帖最后由 小Q学Python 于 2017-1-6 17:10 编辑

看看大大的

比较自己写的。。。

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)
            counts = 1
            if index == len(a):
                index = 0
      print(index, len(a), a)


YSF(100,3)

Remorseless 发表于 2017-1-6 17:40:32

学习了

daxia 发表于 2017-1-7 23:46:22

学习！！！

优等生 发表于 2017-1-7 23:55:12

学习一下

小银锤 发表于 2017-1-10 23:46:19

学习

Jonin616 发表于 2017-2-11 13:01:38

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 == 1:
                step = step + 1
            i = i+1
            if i == m:
                i = 0
            if step == k:
                Joseph = 0
                flag = flag + 1
                step = 0
      else:
            for each in range(m):
                if Joseph == 1:
                  flag = flag + 1
                  print(each)

类十三 发表于 2017-2-24 00:23:02

好厉害

zcr林枫 发表于 2017-3-17 08:37:02

厉害

余欲渔 发表于 2017-3-17 10:45:20

n=100
k=3
sl=
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
    for i in nsl:
      sl.remove(i)
    ysf(sl,k,nqsw)

ysf(sl,k,0)

ooxx7788 发表于 2017-4-1 13:57:47

看看答案呢

ggshen 发表于 2017-4-1 15:22:43

23333333333333333333333333333

shigure_takimi 发表于 2017-4-9 18:07:35

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)
                del persons
                currentNumber = 1
            else:
                persons.append(persons.pop(0))
                currentNumber += 1
      print('--> 原来第%d号人将留下来…' % persons)
      print('--> 被杀死的人是：', quitList)

f(100, 3)

willLin 发表于 2017-4-26 14:24:59

学习一下

和vvv 发表于 2017-6-18 12:16:11

不错哦

P先生 发表于 2017-6-26 09:35:07

bush牛 发表于 2017-9-16 21:49:04

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

suloman 发表于 2017-9-17 00:59:09

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 发表于 2017-9-17 01:09:49

本帖最后由 suloman 于 2017-9-17 01:21 编辑

学习了精简一下
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])
跟大神还差很多到最后我的这个 列表会很长

查看完整版本: python小练习（058）：10来行代码求解约瑟夫环问题