4 typical Solutions for Joseph-Problem

这是非常出名且典型的一个问题:

Background

In computer science and mathematics, the Josephus problem (or Josephus permutation) is a theoretical problem related to a certain counting-out game. People are standing in a circle waiting to be executed. Counting begins at a specified point in the circle and proceeds around the circle in a specified direction. After a specified number of people are skipped, the next person is executed. The procedure is repeated with the remaining people, starting with the next person, going in the same direction and skipping the same number of people, until only one person remains, and is freed. The problem, given the number of people, starting point, direction, and number to be skipped, is to choose the position in the initial circle to avoid execution.

The problem is named after Flavius Josephus, a Jewish historian living in the 1st century. According to Josephus’ account of the siege of Yodfat, he and his 40 soldiers were trapped in a cave by Roman soldiers. They chose suicide over capture, and settled on a serial method of committing suicide by drawing lots. Josephus states that by luck or possibly by the hand of God, he and another man remained until the end and surrendered to the Romans rather than killing themselves.

下面给出四种解♂法:

时间复杂度O(n*m),空间复杂度O(1)

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

下面是python语言实现:

class Node(object):
	def __init__(self, value):
		self.value = value 
		self.next = None

def create_linkList(n):
	head = Node(1)
	pre = head
	for i in range(2, n+1):
		newNode = Node(i)
		pre.next= newNode
		pre = newNode
	pre.next = head
	return head

n = 5 #总的个数
m = 2 #数的数目
if m == 1: #如果是1的话，特殊处理，直接输出
	print (n)  
else:
	head = create_linkList(n)
	pre = None
	cur = head
	while cur.next != cur: #终止条件是节点的下一个节点指向本身
		for i in range(m-1):
			pre =  cur
			cur = cur.next
		print (cur.value)
		pre.next = cur.next
		cur.next = None
		cur = pre.next
	print (cur.value)

时间复杂度O(n),空间复杂度O(1)

首先射f(n)为有n个人时最后一个屎的人的编号，则有如下关♂系式: f(n) = (f(n-1) + m) % 5 稍有算法常识的人就能看出，第一轮屎亡后，第m-1个人屎掉，则开始n-1人的约瑟夫游♂戏，只不过整体人的loop圈往时间流逝方向旋转了m个位移，即与初始n-1约瑟夫状态函数f+m相等，实现转圈loop则用膜除m来实现。

下面是python语言实现:

def joseph(n,m):
    f = 0
    for i in range(2,n+1):
        f = (f + m) % i
    return (f)

时间复杂度Olog(n),空间复杂度Olog(n)

To iterate is human,to recurse divine.

考虑一下，把每次循环体变成在一圈约瑟夫游♂戏中最后一个屎亡的状态。此时，已经有 m(n//m) 个人都已经报完数，并且屎了 (n//m) 个人。即问题从n降低到 n-n//m ，根据 n-n//m 时候的答案s算出n时候的答案sn。这个有两种情况, 如果s在最后一个屎亡的人后面，即 s < n%m , 那么 s2 = s-n%m+n ，否则 s2 = s-n%m+(s-n%m)//(m-1) 。 特别地，如果n < m , 即报数完一轮还没有一个人屎, 则问题的规模无法降低到 n-n//m 所以此方法不适用, 需要再借助前文第一种方法。下面是 python 语言的实现:

def joseph(n,m):
    if n == 1:
        return (0)
    if n < m:
        return ((joseph(n-1, m) + m) % n)
    x = joseph(n-n//m, m) - n%m
    if x < 0:
        return (x+n)
    return (x+x//(m-1))                 
                                

时间复杂度Olog(n),空间复杂度O(1)

Explicit is better than implicit.

我们换种思路，不妨把整个报数循环展开, 用第几次报数来表示。第k个屎的人即使第 km+m-1 次报数滴人(亦是从0开始计数), 设第p个报数的人x, 则有 p = m*a+b (0 <= b < m)。且经过前p次报数，一共屎了 p//m = a ，总共loop还剩下 n-a 人。如果x本次没有屎，那下次报数是经过圈子其他人报数之后，即 q = p+n-a = n+(m-1)*a+b 。已知 b < m-1 ，易得结果 p = q-(n-a) = q-n+floor((q-n)/(m-1)) 所以我们要求第 k 个屎的人，是第 km-1 次报数后shi的，由此往前逆推，不断重复这一过程，直到他是第 k 次报数的人，则 k 即是其编号。以下是 python 语言实现:

def joseph(n,m,k):
    k = k*m+m-1
    while k >= n:
        k = k-n+(k-n)//(m-1)
    return (k)                
                                

参考:

11 Jul 2018