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

问题是这样的：

编号从 1 到 n 的 n 个人坐成一圈，从 1 开始报数，报到 m 的人出局，下一位再从 1 开始报数， 如此持续，直到只剩下最后一人，问此人的初始编号 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 人的问题。如下表所示：

不难看出，老的编号 i 与新编号 j 之间的关系为：

\[i = (j+m)\mod n\]

其中 mod 为取余数运算。显然，这个过程可以不断重复，n - 1 规模的问题可以继续转化为 n - 2 规模的问题、n - 3 规模的问题，直到最后只剩下一个人。

于是，我们可以总结出如下递推公式：

\[ \begin{equation} f(n) = \begin{cases} 1& \text{(n=1)}\\ (f(n-1)+m) \mod n & \text{(n>1)}\\ \end{cases} \end{equation} \]

其中 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)