约瑟夫环问题

约瑟夫环(Joseph Ring)问题是计算机算法中一道经典的题目,我刚接触编程时曾迷惑了很久(当时还是在小霸王学习机上用FBasic编程)。

问题是这样的:有编号从 1 到 n 的 n 个人坐成一圈报数,报到 m 的人出局,下一位再从 1 开始, 如此持续,直止剩下一位为止,报告此人的编号 X。输入 n, m,求出 X。

经典的解法是使用链表。不过在Python中,我们可以使用列表来简单地求解,比如:

def fun1(n, m):
	lst = range(1, n + 1)
	while len(lst) > 0:
		for i in range(m - 1):
			lst.append(lst.pop(0))
		print lst.pop(0),

fun1(17, 3) # 17个人,每报到 3 的人出局

运行上面的程序,显示结果:3 6 9 12 15 1 5 10 14 2 8 16 7 17 13 4 11,表示依次出局的是 3 号、6 号、9 号……、13 号、4 号,最后一位是 11 号。

如果我们不需要知道中间结果,只想知道最后一位是谁,还有一种比较巧妙的办法。

注意到,一开始有 n 个人,报到 m 的人出局后,如果我们从刚才出局的那人的下一位开始重新从 1 开始编号,原问题就转化为了一个 n – 1 人的问题。如下表所示:

原始编号 第一人出局后的编号
m + 1 1
m + 2 2
m + 3 3
m – 2 n – 2
m – 1 n – 1
m 已出局

不难看出,老的编号 i 与新编号 j 之间的关系为:i = (j + m) % n ,其中“%”为取余数运算。显然,这个过程可以不断重复,n – 1 规模的问题可以继续转化为 n – 2 规模的问题、n – 3 规模的问题,直到最后只剩下一个人。

于是,我们可以总结出如下递推公式:

f(n) = (f(n – 1) + m) % n, (n > 1),其中 f(n) 为当场上还有 n 个人时某个在场的人的编号。

当最后只剩下一个人时,这个人的编号显然只能是 1 ,即 f(1) = 1,这时,我们可以根据上面的公式反推回去,推导出当 n 个人都在场时他的编号。代码如下:

def fun2(n, m):
	j = 0
	for i in range(2, n + 1):
		j = (j + m) % i
	print j + 1

fun2(17, 3) # 17个人,每报到 3 的人出局

执行上面的代码,程序将输出最后场上的人在一开始时的编号 11 ,这种方法比第一种方法更快更节省资源,因为它不需要生成一个长度为 n 的列表,也不需要对列表做插入、弹出操作,并且,当 n 非常大时,还可以使用 xrange 来代替 range 以获得更好的性能。最后,贴一下完整的代码:

# -*- coding: utf-8 -*-
# https://oldj.net/
# Joseph Ring

u"""
问题描述:有编号从1到n的n个人坐成一圈报数,报到m的人出局,下一位再从1开始, 如此持续,直止剩下一位为止,报告此人的编号X。输入n, m,求出X。
"""

def fun1(n, m):
	u"""解法一:打印出整个过程
	@param n: 总人数
	@param m: 每次隔多少人
	"""
	lst = range(1, n + 1)
	while len(lst) > 0:
		for i in range(m - 1):
			lst.append(lst.pop(0))
		print lst.pop(0),

def fun2(n, m):
	u"""解法二:只打印出最终结果
	@param n: 总人数
	@param m: 每次隔多少人
	"""
	j = 0
	for i in range(2, n + 1):
		j = (j + m) % i
	print j + 1

if __name__ == "__main__":
	fun1(17, 3)
	print "n----------"
	fun2(17, 3)

One Reply to “约瑟夫环问题”

  1. 牛叉, 赞顺便请教一个问题, 希望编程解决: 设集合S = {x|typeof(x) == ‘string’, /^[abc]{3}$/.test(x) == true}求最短字符串t, 对于S中的任意元素x, 都有t.indexOf(x) >= 0

评论已关闭。