應用於:UVA151 文科生都懂的演算法系列1-Josephus Problem
N=6情況
假設今天喊到2的人都要被處死,共有6個人,輪流喊「1!」「2!」
可以發現定律:
舊編號(黑) = 2 * 新編號(紅) — 1
N=7
可以發現定律:
舊編號(黑) = 2 * 新編號(紅) + 1
所以
公式彙整如下:
如果參加人數為奇數 舊編號 = 2 * 新編號 + 1
如果參加人數為偶數 舊編號 = 2 * 新編號 - 1
假設當n 個人, W(n) = 保命位置。
W(1) = 1 代表參加人數剩下1人時,那個人永遠只會喊到1!,並不可能喊到2!,因此該人會存活,而保命位置為1。
我們可以利用前面提過的公式。
如果參加人數為奇數
舊編號 = 2 * 新編號 + 1
W(3) = 2*W(1)+1 = 3 代表剩下3人時,最後存活的人的編號是3號。
接者,再繼續回到初始狀態,共有六人的狀況如下。

我們可以利用前面提過的公式。
如果參加人數為偶數
舊編號 = 2 * 新編號 -1
W(6) = 2*W(3) -1 = 5
以此類推可以知道,最後一輪編號為1的人,最一開始編號是5號。
所以當參加人數有6個人的時候,站在編號5的位置可以活著!
推出公式
保命位置=2×(參加人數−2^m)+1
(參加人數−2^m) 其實就等於 a
