約瑟夫環（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 -*-
# http://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)
