# 【C++】競程筆記（約瑟夫問題）
[TOC]
歡迎您點進本篇文章，本系列旨在記錄與筆記個人學習歷程，內容僅供學習用途，斟酌參考。若你喜歡本文，也可以為本篇文章按愛心，或是追蹤我來取得最新文章的資訊。
最後更新日期：2026/1/25 00:12:02
## 什麼是約瑟夫問題（Josephus Problem）？
約瑟夫問題（Josephus Problem）是一個經典的數學和演算法問題，而同樣的問題又稱為約瑟夫環。
歷史由來：
> 這個問題是以弗拉維奧·約瑟夫斯命名的，他是1世紀的一名猶太歷史學家。他在自己的日記中寫道，他和他的40個戰友被羅馬軍隊包圍在洞中。他們討論是自殺還是被俘，最終決定自殺，並以抽籤的方式決定誰殺掉誰。約瑟夫斯和另外一個人是最後兩個留下的人。約瑟夫斯說服了那個人，他們將向羅馬軍隊投降，不再自殺。約瑟夫斯把他的存活歸因於運氣或天意，他不知道是哪一個。
> From [Wikipedia](https://zh.wikipedia.org/zh-tw/%E7%BA%A6%E7%91%9F%E5%A4%AB%E6%96%AF%E9%97%AE%E9%A2%98)
### 問題定義
約瑟夫問題的標準數學模型如下：
- 總人數（$n$）：有 $n$ 個人圍成一圈，編號為 $1, 2, ..., n$。
- 報數間隔（$m$ 或 $k$）：從第 1 個人開始報數（從 1 報到 $m$）。
- 規則：
1. 報到 $m$ 的人出局（被殺）。
2. 從出局者的下一個人開始，重新從 $1$ 開始報數。
3. 重複上述過程，直到只剩下最後一個人。
- 目標：找出最後倖存者的編號。
至於這個約瑟夫問題運作起來長什麼樣子？大概就像以下的動圖那樣：
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$ 出局時，最後倖存者的索引。
1. 第一個人出局：第一輪報數後，第 $(m-1)$ 號人出局（從 0 開始數，第 $m$ 個人索引是 $m-1$），剩餘 $n-1$ 個人組成一個新的圈。
2. 重新編號：刪除元素後，原本的索引會發生位移。
- 舉例： $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。
範例程式碼：
```cpp=
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 優化）：
```cpp=
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 解題三步法：
1. 定義狀態：$dp[i]$ 為當總人數為 $i$ 人，報數間隔為 $m$ 時，最終倖存者的「索引編號」。目標是求出 $dp[n]$。
2. 定義轉移式：
設當前有 $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$$
3. 定義初始狀態：當只有 $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}$$
範例程式碼：
```cpp=
#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 公式
```cpp=
int ans(int n, int k){
int s = 0;
for (int i = 2; i <= n; ++i){
s = (s + k) % i;
}
return s;
}
```
## 參考資料（Reference）
[約瑟夫問題 - 維基百科，自由的百科全書](https://zh.wikipedia.org/zh-tw/%E7%BA%A6%E7%91%9F%E5%A4%AB%E6%96%AF%E9%97%AE%E9%A2%98)
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](https://www.geeksforgeeks.org/dsa/josephus-problem/)
[The Josephus Problem. …is a famous puzzle in computer science… | by Tom Lord | Carwow Product, Design & Engineering | Medium](https://medium.com/carwow-product-engineering/the-josephus-problem-2ef02b77ada9)
Sign in with Wallet
Connect another wallet