問題概述
故事
有一群戰敗的士兵，他們決定寧死不降，因此決定圍成一個圈圈，由第一個人往下數2個，然後開槍殺掉被數中的人，再由被殺掉的下一個人開始，重複此過程
而有一位士兵其實不想自殺，所以他決定站在最後一個被數到的位置(沒有其他人能監督他自殺了)，但他必須在過程開始前選好位置….
下圖是五人的小例子，紅槓數 == 第幾位被選中
定義
通俗化來說，我們可以有n個士兵，與開始數到第k個人被排除
並順時針從1至n進行編號
就可以用J(n,k) 來表示在此情況下最後一個存活的人
舉例來說:
很明顯地 J(1,k) == 1 ，因為總是只有第一人存活
又比如上述故事中，K(5,2) == 4 因為最後由第四個人存活
暴力法
我們可以用一個Queue進行模擬
搭配一個一開始是k的計數器，Queue每次尾端會抽出一位，此時計數器會減一，
如果在抽出時計數器歸零 ==> 被排除 ==> 移出Queue ==> 重置計數器
否則 ==> 繼續數 ==> 放回Queue前端
此過程直到Queue剩下一個
虛擬碼
# initialize
counter = k
Queue = [1,2,3 ... n ]
while Queue.size() > 1 : # repeat until only one element in queue
if counter == 0:
Queue.Dequeue() # never put it back
counter = k # reset
else:
Queue.Enqueue(Queue.Dequeue()) # put tail to head
counter -=1
很明顯的，此方法要排除N-1個元素，而每次排除都必須要數k次
因此時間複雜度為 O(n*k)
遞迴數學解
概念
我們可以由 n-1 個人的解，推到n個人的解
舉例說明，一樣用故事中的例子，我們要求五個人的解
我們可以先求四個人的解
然後先求出五個人中被排除了那個人
然後因為下一個人是 “四個人” 的起點，我們可以直接知道起點就是最後生存的人
因此答案即為4號
問題在於: 如何轉換J(n-1,k)與J(n,k)起始點偏移
也就是上圖(4人解)中，起點是1號，但下圖(5人解)中，剩下四人的起點是4號
換句話說我們需要找到一個一一對應函數 F
使
1 => 4
2 => 5
3 => 1
4 => 2
這樣我們可以將 J(n,k) 遞迴表示為 F(J(n-1,k))
- 注意: F 可以說是被k決定，比如在此例中，k=3決定了3被排除，由此決定了F
一一對應
首先先思考，我們要怎麼在當下回合知道，誰是下一個起點
通常答案是 加上k+1 後 環狀取餘n，這在環狀結構中很常見
但是由於我們編號從1開始，k也是有從被排除的人是從起點自己開始數還是與起點間隔多少，抑或是下一個起點具起點多少… 等表達方法，因此我們將k 定義為最方便的，下一個起點位置 這樣我們可以立刻知道下一個起點是 +k%n
套用這個新定義，我們的問題變成
0 => 3
1 => 4
2 => 0
3 => 1
其中原始問題 n=5,k=3
再來思考在知道下一回合起點後，怎麼找到一一對應關係
從例子可以觀察出似乎也是 +k%n
(0+3)%5 = 3
(1+3)%5 = 4
(2+3)%5 = 0
(3+3)%5 = 1
因此以上例所示範
我們可以很快得到J(5,3)的答案為 F(J(4,3)) = (J(4,3)+3)%5
證明 : 任意n,k之一對一函數為 +k%n
由於第k-1個被排除，並且起點為第k個
因此我們需要找到一個F 使以下對應關係成立
x => y
---------
0 => k
1 => k+1
.
.
n-k-1 => n-1
n-k => 0
n-k+1 => 1
.
.
n-2 => k-2
Case1: 在y 於 k ~ n-1 區段中
其關係可表示為 y = x+k , x為 0 ~ n-k-1
由於 x <= n-k-1
故 (x+k) <= n-1
(x+k)%n == x+k == y，恆成立
Case2: 在y 於 0 ~ k-2 區段
其關係可表示為 y = x-n+k , x 為 n-k ~ n-2
反推 x = y+n-k
由於 n-k <= x
n <= x+k = y+n
(x+k)%n == (y+n)%n == y 恆成立
結論，對任何n,k
+k%n都是可以讓J(n-1,k),J(n,k)編碼對應的函數
遞迴式
因此我們可以列出遞迴式
J(0,k) = 0
J(n,k) = J(n-1,k)+k % n
其中 n 表示人數，並從0開始順時針編碼，k表示被排除的下一個人(下一次起點)
當然我們也可以做調整，使編碼從1開始
J(1,k) = 0
J(n,k) = (J(n-1,k)-1+k ) % n +1
意思是先減一回到0，再通過0開始編碼的一對一函數得到y ，最後再加一回到以1開始邊碼
有點矩陣同構函數的味道
這樣時間複雜度可以降到O(n)
總結
- 想辦法由前項推後項
- 找到前後項編碼的對應方法
變體
leetcode 390. Elimination Game
如下圖
從1開始砍掉所有奇數位置的數
然後倒過來執行
重複直到剩下一個數
由於每回合都會翻轉，因此不能簡單地使用前面推導的式子
但是可以用一樣的概念，找到上下項，找到對應編碼
可以觀察到，第一回合會刪掉所有奇數
所以可簡化成 J(n//2) 的問題
再來是編碼，以例子而言，會先得到
2 4 6 8
而我們知道J(4) == 2 (1,2,3,4 => 2,4 => 2)
所以要將
1 => 8
2 => 6
3 => 4
4 => 2
可以暴力的求得為 8 - i*2 + 2
因此我們有答案了
J(1) = 1 , J(2) = 2
if 奇數:
J(n) = (n-1) - J(n//2)\*2 +2
if 偶數:
J(n) = n - J(n//2)\*2 +2
此法速度79% , 空間利用100%