约瑟夫问题详解

约瑟夫问题详解

约瑟夫问题（Josephus Problem）是一个著名的数学问题，描述如下：

n 个人围成一圈，从第一个人开始报数，每次数到 m 的人出局，然后从下一个人重新开始报数，直到只剩下一个人为止。问最后剩下的人在初始位置中的编号是多少？

---

1. 问题定义

基本设定：

• n 个人编号为 1, 2, …, n
• 从 1 开始报数，数到 m 的人出局
• 出局后从下一个人继续从 1 开始报数
• 求最后剩下的人的编号

两种编号方式：

• 1-based：编号从 1 到 n（常用）
• 0-based：编号从 0 到 n-1（编程中常用）

---

2. 暴力模拟法

最简单的解法是模拟整个过程：

#include <iostream>
#include <vector>
using namespace std;

int josephus_simulation(int n, int m) {
    vector<bool> alive(n, true);
    int count = n; // 剩余人数
    int index = 0; // 当前报数的人
    int step = 0;  // 当前报的数
    while (count > 1) {
        if (alive[index]) {
            step++;
            if (step == m) {
                alive[index] = false;
                count--;
                step = 0;
            }
        }
        index = (index + 1) % n;
    }
    // 找到最后活着的人
    for ( i = ; i < n; i++) {
         (alive[i]) {
             i + ; 
        }
    }
     ;
}