演算法知識 - Josephus problem 約瑟夫問題 遞迴公式說明與應用

Josephus problem 約瑟夫問題介紹

約瑟夫問題是一個非常黑暗的問題XD，主要是殘兵們不想被對方軍團俘虜，而想出一種自殺方式，其內容大概如下

• 全部人圍成一個圓圈，編號 \(1,2,3,…,n\)
• 定義一個數字 \(k\)，只要數到第 k 個數字，那麼那個人就自殺。
• 接下來，從死掉的那個人開始在數 k 個數字，再來第 \(2k\) 的人自殺。
• 不斷數著 k、不斷地自殺，不斷循環，直到最後只剩下一個人為止。

而我們的主角 Josephus 則不想要自殺，於是他必須找到一個位置，並且是最後剩下的那個人。

表達大致上的意思，並沒有全部完整表達。

下方我的證明可能並沒有很好閱讀，因此不懂的讀者可以參考约瑟夫环——公式法（递推公式） by 陈浅墨

模擬操作解法

時間複雜度為 \(O(nm)\)，當 n,m 大於一百萬時，必會耗時許久。

但如果題目有說必須依序輸出被殺死的人時，那我們就必須使用此方法。

遞迴公式 - 求出最後一位生還者

時間複雜度為 \(O(n)\)，快了超級多！ 但我們只能夠求出最後一位生還者。

詳細的說明請看 YT
上面影片中約瑟夫問題 說明的 excel 文件 pdf 檔案
上面影片中約瑟夫問題 說明的 excel 文件 excel 檔案

程式碼說明

int josephus(int n, int k){
    int s = 0; //一開始的編號
    for(int i = 2; i <= n; i++) s = (s+k) % i; //第 i 輪中，他的位置是第 s 
    return s+1; //如果題目的編號一開始是 1，那我們就加一
}

相關題目

• UVa10774 - Repeated Josephus(數論 Math theorm、Josephus problem 約瑟夫問題) by 大衞的筆記
• UVa11531 - Last Man Standing(數論 Math theorm、Josephus problem 約瑟夫問題) by 大衞的筆記

參考連結

约瑟夫环——公式法（递推公式） by 陈浅墨
約瑟夫斯問題 by wiki

心得

其實這題我學習很久…，主要是他的證明比較抽象化，不太好在腦內思考，後來是找到一篇很棒的文章！幫助了我思考XD。

约瑟夫环——公式法（递推公式） by 陈浅墨這篇文章非常好懂，大力推！
只是他的 Q1 必須看留言會更好懂些。不愧是大佬，可以用文字敘述就表達此題！我這次想要用文字敘述來表達都表達不出來QQQ。

有稍微讓自己的腦袋運動了一下，希望腦袋經過這次的摧殘後又變得越來越聰明XD。

不過有時候還是會覺得，花了這麼多時間在讓自己證明這些東西，結果以後如果要是忘記了就覺得好可惜QQ。

總之，希望我可以在這份證明學習到的知識，應用在任何一個可以應用的地方上。
我最怕的就學會卻不會應用。

學習紀錄

我有用紙筆來進行學習，現在拍下照片來記錄！

這邊為我之前原本想要用文字進行說明，卻發現我沒辦法很明顯用文字進行說明，但我這邊留下來進行紀錄

我們來舉個例：有 8 個人，依序並且不斷循環，只要數到第 3 個人，那他則必須自殺，最後存活下來的人是誰？

• 來個想法，我們可以簡單的看的出來 \(n=8, k=3\) 的情況下，最後存活的人是誰嗎？
• 我們來把題目稍微簡單化
  • 在 \(n = 1, k = 3\) 的情況下，會有人死掉嗎？
    不會，因為她是倖存的最後一位，因此存活的會是 1。
  • 在 \(n = 2, k = 3\) 的情況下，哪一個人可以活到最後呢？
    2，因為數到 3 剛好是 1。
  • 在 \(n = 3, k = 3\) 的情況下，哪一個人可以活到最後呢？
    2，第一次數到 3 時位置在第 3、第二次數到 3 時位置在 1。
• 在剛剛的應用中，我們大概知道一些規則，這時候我們用 \(n = 3, k = 3\) 來舉例
  • 定義隊伍為 \(1,2,3,…\)，且不斷循環，因此可以寫成 \(1,2,3,1,2,3,…\)
  • 由於是循環排序，因此前面的數字會被移到隊伍最後方，我們永遠只需要從數列第一個開始計算第 k 個
  • 如果我們移除了數字 a，那們我們的隊伍則不可以再有數字 a
  • 因此順序是

    pos: 1 2 3 4 5 6 7 8 9
    val: 1 2 3 1 2 3 1 2 3

  • 當我們數到第三個位置時， 3 必須被移除，不再排序中，因此我們將隊伍中所有的 3 移除

            ^
    pos:1 2 3 4 5 6
    val:1 2 1 2 1 2
    #我們將 pos 3 的數字全部刪除，並且將空缺位置補上。
    # ^ 為下一次數列的開始位置

  • 我們再來數到第三個位置時，將他移除，這邊我們會移除的則是 1，因此我們將隊伍中所有的 1 移除

            ^
    pos:1 2 3 
    val:2 2 2
    # 我們將 pos 3 的數字全部刪除，並且將空缺位置補上。
    # ^ 為下一次數列的開始位置

  • 現在隊伍裡面只剩下一個數字了，那就是 2。
• 剛剛我們舉例了 n 從 3 -> 1，發現這是一種模擬操作對吧？現在我們換個角度來看，來算算看 n 從 1 -> 3
  • 定義存活的數字為 2，英文為 alive。
  • \(n = 1\)的隊伍是 \(2(alive),2,2,…,2\)，我們並不需要移除，因為只剩下一個數字
  • 剛剛我們是將前面的數字移到隊伍最後方，現在我們則將後面的數字移到隊伍最前方，還原操作
  • \(n = 2\)的隊伍是 \(1(k = 1),2(k = 2),1(被移除的數字, k = 3),2(alive),…,1,2\)
  • \(n = 3\)的隊伍是 \(1(k=1),2(k=2),3(被移除的數字,k=3),1(n=2,k=1),2(n=2,k=2),3(n= 2, 數字被移除),1(被移除的數字, n = 2,k = 3,),2,,…,1,2,3\)