约瑟夫问题：数学原理与C++高效实现

1. 约瑟夫问题解析：从数学原理到C++实现

作为一名长期从事信息学竞赛辅导的教练，我发现约瑟夫问题几乎是每年各类竞赛的必考题型。2025年厦门市小学生计算机C++语言竞赛初赛试卷中出现的这道题（31-33题），正是经典约瑟夫问题的变种。让我们先看题目给出的核心代码：

cpp复制int n, m = 3, s = 0;
for (int i = 2; i <= n; i++)
    s = (s + m) % i;
printf("%d\n", s + 1);

这段简洁的代码背后隐藏着精妙的数学原理。它解决的是这样一个问题：n个人围成一圈，从某个人开始报数，每数到第3个人就将其淘汰出局，然后从下一个人重新开始报数，直到所有人都被淘汰，问最后剩下的人初始位置编号是多少？

1.1 约瑟夫问题的数学本质

约瑟夫问题（Josephus Problem）得名于古罗马历史学家弗拉维奥·约瑟夫斯的传奇故事。在计算机科学中，它成为了研究递归和模运算的经典案例。

对于步长m=3的情况（如题目所示），递推公式为：
f(1) = 0
f(k) = (f(k-1) + m) % k, 其中k从2到n

这个递推关系式的精妙之处在于：

1. 它通过模运算自动处理了"围成圆圈"的循环特性
2. 每次迭代都相当于将问题规模缩小1（淘汰一个人）
3. 最终结果f(n)表示的是0-based的编号，所以输出时需要+1

1.2 代码逐行解析

让我们深入分析题目给出的代码：

1. int n, m = 3, s = 0;

   • 定义总人数n（由输入决定）
   • 固定步长m=3（每隔2人淘汰第3人）
   • 初始化结果s=0（当n=1时的解）

2. for (int i = 2; i <= n; i++)

   • 从2人情况开始递推，直到n人
   • 每次循环相当于解决i人规模的子问题

3. s = (s + m) % i;

   • 核心递推公式
   • 新的解=(上一轮解+步长) mod 当前人数

4. printf("%d\n", s + 1);

   • 输出1-based的结果（因为s是0-based）

注意：这段代码的时间复杂度是O(n)，空间复杂度是O(1)，是解决约瑟夫问题最高效的算法之一。