【C++】競程筆記（約瑟夫問題）

歡迎您點進本篇文章，本系列旨在記錄與筆記個人學習歷程，內容僅供學習用途，斟酌參考。若你喜歡本文，也可以為本篇文章按愛心，或是追蹤我來取得最新文章的資訊。

什麼是約瑟夫問題（Josephus Problem）？

約瑟夫問題（Josephus Problem）是一個經典的數學和演算法問題，而同樣的問題又稱為約瑟夫環。

歷史由來：

這個問題是以弗拉維奧·約瑟夫斯命名的，他是1世紀的一名猶太歷史學家。他在自己的日記中寫道，他和他的40個戰友被羅馬軍隊包圍在洞中。他們討論是自殺還是被俘，最終決定自殺，並以抽籤的方式決定誰殺掉誰。約瑟夫斯和另外一個人是最後兩個留下的人。約瑟夫斯說服了那個人，他們將向羅馬軍隊投降，不再自殺。約瑟夫斯把他的存活歸因於運氣或天意，他不知道是哪一個。
From Wikipedia

問題定義

約瑟夫問題的標準數學模型如下：

總人數（ $n$ ）：有 $n$ 個人圍成一圈，編號為 $1, 2, ..., n$ 。
報數間隔（ $m$ 或 $k$ ）：從第 1 個人開始報數（從 1 報到 $m$ ）。
規則：
1. 報到 $m$ 的人出局（被殺）。
2. 從出局者的下一個人開始，重新從 $1$ 開始報數。
3. 重複上述過程，直到只剩下最後一個人。
目標：找出最後倖存者的編號。

至於這個約瑟夫問題運作起來長什麼樣子？大概就像以下的動圖那樣：

Josephus Problem gif

gif source：https://medium.com/carwow-product-engineering/the-josephus-problem-2ef02b77ada9

解法

模擬法

以陣列（Array）或循環鏈結串列（Circular Linked List）。

邏輯：建立一個包含 $1$ 到 $n$ 的列表，模擬報數過程，每次刪除第 $m$ 個元素，直到列表長度為 1。
缺點：當 $n$ 非常大時（如 $n = 1,000,000$ ），模擬刪除元素的操作非常耗時，時間複雜度通常是 $O(n \cdot m)$ 或 $O(n^2)$ ，效率較低。

遞迴法

此為解決約瑟夫問題最高效的方法，時間複雜度為 $O(n)$ 。

由於每殺掉一個人，問題規模就縮小一次，變成了 $n-1$ 個人的子問題，可透過「舊編號」與「新編號」之間的映射關係來推導公式。

（用 0-based indexing）令 $f(n, m)$ 表示 $n$ 個人，報數到 $m$ 出局時，最後倖存者的索引。

第一個人出局：第一輪報數後，第 $(m-1)$ 號人出局（從 0 開始數，第 $m$ 個人索引是 $m-1$ ），剩餘 $n-1$ 個人組成一個新的圈。
重新編號：刪除元素後，原本的索引會發生位移。

舉例： $n=7, m=3$ $n = 7, m = 3$ （索引 0~6）。
- 第一輪刪掉索引 2（即第3人）。
- 下一個人（原索引 3）變成了下一輪的起點（新索引 0）。
- 原索引 4 就變成新索引 1，以此類推。
- 這種位移關係可表示成： $$\text{OldIndex} = (\text{NewIndex} + m) % n$$

根據這個位移關係，可以得出遞迴式：$$f(n, m) = (f(n-1, m) + m) % n$$

終止條件就是當只剩 1 個人時（ $n=1$ ），其索引必定是 0。$$f(1, m) = 0$$

最終公式（0-based）：$$f(n, m) =
\begin{cases}
0 & \text{if } n = 1 \
(f(n-1, m) + m) % n & \text{if } n > 1
\end{cases}$$

（1-based）：$$f(n, m) =
\begin{cases}
1 & \text{if } n = 1 \
(f(n-1, m) + m - 1) % n + 1 & \text{if } n > 1
\end{cases}$$

LeetCode 1823. Find the Winner of the Circular Game

Problem Source：https://leetcode.com/problems/find-the-winner-of-the-circular-game/description/

注意這題是 1-based indexing。

範例程式碼：

class Solution {
public:
    int findTheWinner(int n, int k) {
        if (n == 1)
            return 1;
        return (findTheWinner(n - 1, k) + k - 1) % n + 1;
    }
};

既然都談到遞迴了對吧，那就不能少了最重要的 Dynamic Programming，以下是 DP 範例程式碼（經滾動 DP 優化）：

class Solution {
public:
    int findTheWinner(int n, int k) {
        int s = 1;
        for (int i = 2; i <= n; ++i){
            s = (s + k - 1) % i + 1;
        }
        return s;
    }
};

該題的 DP 解題三步法：

定義狀態： $dp[i]$ 為當總人數為 $i$ 人，報數間隔為 $m$ 時，最終倖存者的「索引編號」。目標是求出 $dp[n]$ 。
定義轉移式：

設當前有 $i$ 個人，編號為 $0, 1, 2, ..., i-1$ ，報數到 $m$ 的人出局。

第一輪出局的人的索引為 $(m-1) \pmod i$
出局者的下一個人成為新的報數起點（新的索引 0）。

假設 $i$ 個人的倖存者位置是 $P_{old}$ ，而刪掉一人後變成 $i-1$ 個人，倖存者在剩下的人群中相對位置是 $P_{new}$ ，也就是 $dp[i-1]$ 。

根據逆推邏輯得到：原問題的倖存者位置 = (子問題的倖存者位置 + 偏移量 $m$ ) % 當前人數

最後得到完整轉移式：$$dp[i] = (dp[i-1] + m) % i$$

定義初始狀態：當只有 $1$ 個人時 ( $i=1$ )，倖存者索引必定是 0。$$dp[1] = 0$$

由於計算 $dp[i]$ 只需要知道 $dp[i-1]$ ，不需要保留更早之前的紀錄，因此可用一個變數 $s$ 來做更新即可，可將空間複雜度降至 $O(1)$ 。（滾動 DP 優化方法）

Uva 151 - Power Crisis

PDF Source：https://onlinejudge.org/external/1/151.pdf

Uva Online Judge：https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=87

Zerojudge：https://zerojudge.tw/ShowProblem?problemid=q891

該題為約瑟夫問題的變體。

題目架構：

共 $N$ 個地區（ $1$ 到 $N$ ）
地區 $1$ 總是第一個被切斷。
剩下 $N-1$ 個地區，從地區 $2$ 開始，每數到第 $m$ 個地區就切斷它。
目標：找出最小的 $m$ ，使得地區 13 是最後一個被切斷的。

轉化成約瑟夫問題的形式：

首先由於地區 $1$ 都是第一個被切斷的，只需考慮 $N - 1$ 的地區即可，因此就變成長度為 $N - 1$ 的約瑟夫問題。

另外為方便計算，將地區給重新編號：

地區 $2 \rightarrow 0$
地區 $3 \rightarrow 1$
$\cdots$
地區 $13 \rightarrow 11$

這樣就需要找到一個 $m$ ，使得在這 $N-1$ 個人的環中，最後被切斷的索引為 11。

約瑟夫問題公式：$$f(n, m) =
\begin{cases}
0 & \text{if } n = 1 \
(f(n-1, m) + m) % n & \text{if } n > 1
\end{cases}$$

範例程式碼：

#include <iostream>

using namespace std;

int ans(int n, int k){
    int s = 0;
    for (int i = 2; i <= n; ++i){
        s = (s + k) % i;
    }
    return s;
}

int main(){
    ios::sync_with_stdio(false), cin.tie(NULL);
    int N;
    while (cin >> N && N != 0){
        int m = 1;
        while (true){
            int last = ans(N - 1, m);
            if (last == 11){
                cout << m << '\n';
                break;
            }
            m++;
        }
    }
}

總整理

遞迴公式

（0-based）：$$f(n, m) =
\begin{cases}
0 & \text{if } n = 1 \
(f(n-1, m) + m) % n & \text{if } n > 1
\end{cases}$$

（1-based）：$$f(n, m) =
\begin{cases}
1 & \text{if } n = 1 \
(f(n-1, m) + m - 1) % n + 1 & \text{if } n > 1
\end{cases}$$

dp 公式

int ans(int n, int k){
    int s = 0;
    for (int i = 2; i <= n; ++i){
        s = (s + k) % i;
    }
    return s;
}

參考資料（Reference）

約瑟夫問題 - 維基百科，自由的百科全書

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 14: Augmenting Data Structures, pp.318.

Josephus Problem - GeeksforGeeks

The Josephus Problem. …is a famous puzzle in computer science… | by Tom Lord | Carwow Product, Design & Engineering | Medium