約瑟夫斯問題（Josephus Problem）是一個經典的數學與電腦科學問題。
傳說中，有 41 個人 被敵軍包圍。為了避免被俘，他們決定圍成一圈，按照固定規則逐一淘汰自己。
問題是：
如果每次從固定位置開始數，每數到第 3 個人就淘汰他，最後一個留下的人應該站在哪個位置？
這就是著名的約瑟夫斯問題。
41 人與位置 19
在經典版本中，41 個人圍成一圈，每數到第 3 個人就淘汰一人。
如果將位置從 1 到 41 編號，按照這個規則不斷淘汰，最後留下的位置是：
位置 31
這個結果可以透過數學遞迴直接計算，而不需要真的逐個模擬淘汰過程。
需要注意的是，不同版本的問題可能採用不同的起點、編號方式與淘汰規則，因此最後的位置也會不同。
為什麼這個故事與電腦科學有關？
約瑟夫斯問題看起來像是一個古老的數學謎題，但它其實揭示了一個非常重要的電腦科學概念：
如何有效處理循環結構中的元素刪除。
如果直接模擬整個過程，就必須：
- 建立一個循環。
- 按照規則找到下一個要淘汰的位置。
- 刪除該元素。
- 重新計算下一個位置。
- 不斷重複，直到只剩下一個元素。
這種方法直觀，但當人數非常大時，模擬過程可能會變得昂貴。
遞迴解法
約瑟夫斯問題最漂亮的地方，在於它可以透過遞迴關係解決。
如果有 n 個人，每次淘汰第 k 個人，令 J(n,k) 表示最後留下的位置，則：
J(1,k) = 0
J(n,k) = (J(n-1,k) + k) mod n
這裡使用的是從 0 開始編號。
最後，如果需要轉換成從 1 開始的位置，只需要：
J(n,k) + 1
function josephus(n, k):
result = 0
for i = 2 to n:
result = (result + k) mod i
return result
時間複雜度為：
O
而且不需要建立整個人員列表。
這就是演算法思維的核心之一：
不要只想著如何一步一步完成問題，也要尋找問題背後的結構。
一句話記住
約瑟夫斯問題表面上是在問「誰最後留下」，實際上是在研究「如何追蹤一個不斷縮小的循環結構」。
從 41 個人圍成一圈，到今天的遞迴公式與電腦演算法，這個兩千年前的數學問題至今仍然是資料結構與演算法中非常經典的一個案例。