---
# System prepended metadata

title: 【C++】競程筆記（約瑟夫問題）
tags: [程式設計, C++, DP, 競程, 演算法, 程式語言, 遞迴, CP]

---

# 【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. 重複上述過程，直到只剩下最後一個人。
- 目標：找出最後倖存者的編號。

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

![Josephus Problem gif](https://hackmd.io/_uploads/Bye5PjrfUWl.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$ 出局時，最後倖存者的索引。

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)