應用於: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