← 目录 / 算法文档 · 模块二基础算法思想 / 2.3 模拟法

2.3　模拟法

题目把整个过程讲得明明白白，那就照着题目说的，一步一步在代码里"演"一遍。

本页目录

①什么是模拟法
②基础模拟：传球游戏
③综合例子：约瑟夫环
④完整代码与小结

① 什么是模拟法

有些题目不需要找什么巧妙的数学规律——题目本身就是一套过程描述："第一步做什么，然后怎么变化，再下一步又做什么"。遇到这种题，最直接的办法就是模拟法：照着题目描述的规则，一步一步在代码里"重新演一遍"这个过程，演完之后，程序里的状态就是答案。

模拟法和 2.1 节的枚举法不一样——枚举法是"不知道答案，把所有可能都试一遍去找"；模拟法是"过程是确定的，照着做一遍，自然就知道结果"。很多综合性强的题目，会同时用到前面学过的数组、循环、分支，甚至要结合 2.2 节的数组标记法——这一节就是把这些工具放在一起，做一次综合演练。

② 基础模拟：传球游戏

6 个人站成一圈，编号 0~5。球一开始在 0 号手里，每一轮都往前传 2 个位置（比如从 0 号传到 2 号）。传了 4 轮之后，球在谁手里？

这道题没有什么公式，照着规则模拟就行——唯一需要注意的技巧是：站成一圈，传到末尾要能绕回到开头。这正好是取余运算最常见的用法之一：用 (当前位置 + 步数) % 总人数，就能让位置自动"绕圈"，超过末尾会自动从头开始算。

C++ · 模拟传球游戏

        
          1int n = 6, k = 2, m = 4;
2int pos = 0;  // 球一开始在0号手里
3for (int i = 0; i < m; i++)
4{
5    pos = (pos + k) % n;  // 往前传k个位置，超出范围自动绕回开头
6}
7cout << "球最后在 " << pos << " 号手里";

      

球的传递轨迹（n=6，每次传2个位置，共传4轮）

轮次	计算	新位置
第1轮	(0+2) % 6	2
第2轮	(2+2) % 6	4
第3轮	(4+2) % 6 = 6 % 6	0　（绕回了开头）
第4轮	(0+2) % 6	2　—— 最终答案

第 3 轮的时候，位置算出了 6，但只有 0~5 六个位置——取余之后自动变成了 0，相当于绕回了一圈的开头。这就是"取余实现循环"的关键：不管加多少次，结果永远落在合法范围内，不需要手动判断"是不是超出范围了，要不要减回去"。

③ 综合例子：约瑟夫环

把"传球游戏"的循环位置技巧，和上一节学的数组标记法结合起来，就能解决一个经典问题——约瑟夫环：n 个人站成一圈，编号 1 到 n，从 1 号开始报数，每数到 k 的那个人出局，然后从下一个人重新开始报数，一直重复，直到只剩下最后一个人——问最后留下来的是几号？

C++ · 约瑟夫环模拟

        
          1int Josephus(int n, int k)
2{
  vector<bool> eliminated(n + 1, false);  // 标记谁已经出局了
  int pos = 0;           // 当前指向的人（用0~n-1表示，真实编号是pos+1）
  int remaining = n;
  int count = 0;         // 当前报到的数字
7
  while (remaining > 1)
  {
      if (!eliminated[pos + 1])  // 这个人还在场，才轮到他报数
      {
          count++;
          if (count == k)  // 报到了k，这个人出局
          {
              eliminated[pos + 1] = true;
              remaining--;
              count = 0;  // 重新从0开始报数
          }
      }
      pos = (pos + 1) % n;  // 移动到下一个位置，绕圈
  }
22
  for (int i = 1; i <= n; i++)
  {
      if (!eliminated[i])  // 找到唯一没出局的人
      {
          return i;
      }
  }
  return -1;  // 不会执行到这里
31}

      

📌

这段代码同时用到了三个前面学过的工具：eliminated 数组是 2.2 节的数组标记法（标记谁出局了）；pos = (pos+1) % n 是这一节刚学的取余绕圈；if (!eliminated[...]) 加 count++ 则是最朴素的条件判断和计数。模拟法经常就是这样——单独看每一部分都不难，难的是把它们正确地组合在一起，照着题目描述的顺序一步步实现。

n=5 人，每数到 k=2 就出局 —— 完整的淘汰过程

初始状态：1 2 3 4 5 全部在场

从1开始报数：1(报1)，2(报2)——2号出局

从3继续：3(报1)，4(报2)——4号出局

从5继续：5(报1)，跳过已出局的2，1(报2)——1号出局

从3继续：跳过已出局的1、2，3(报1)，跳过4，5(报2)——5号出局

只剩 3 号 —— 游戏结束

淘汰顺序是 2 → 4 → 1 → 5，最后留下来的是 3 号。注意已经出局的人不会被重新数到——这正是代码里 if (!eliminated[pos+1]) 这一层判断在做的事：跳过已经离场的人，只给还在场的人报数。

④ 完整代码与小结

用到的工具	对应代码	来自哪一节
循环绕圈	pos = (pos + 1) % n	2.3 节本节内容
状态标记	eliminated[i] = true	2.2 数组标记法
条件计数	count++; if (count == k)	第4、5章分支与循环

🎯

模拟法本身没有什么"算法"可言——它考察的是能不能把题目的文字描述，原原本本翻译成代码。读题的时候，建议先把过程拆成一句一句的步骤（"先做什么""再做什么""什么时候停"），再对照着把每一句翻译成一行或一段代码，往往比想着"要用什么算法"更容易下手。模块二到这里就结束了——枚举试遍可能、标记记录状态、模拟还原过程，这三件事是后面几乎所有复杂算法的地基。

1	int Josephus(int n, int k)
2	{
3	vector<bool> eliminated(n + 1, false); // 标记谁已经出局了
4	int pos = 0; // 当前指向的人（用0~n-1表示，真实编号是pos+1）
5	int remaining = n;
6	int count = 0; // 当前报到的数字
7
8	while (remaining > 1)
9	{
10	if (!eliminated[pos + 1]) // 这个人还在场，才轮到他报数
11	{
12	count++;
13	if (count == k) // 报到了k，这个人出局
14	{
15	eliminated[pos + 1] = true;
16	remaining--;
17	count = 0; // 重新从0开始报数
18	}
19	}
20	pos = (pos + 1) % n; // 移动到下一个位置，绕圈
21	}
22
23	for (int i = 1; i <= n; i++)
24	{
25	if (!eliminated[i]) // 找到唯一没出局的人
26	{
27	return i;
28	}
29	}
30	return -1; // 不会执行到这里
31	}

1	int n = 6, k = 2, m = 4;
2	int pos = 0; // 球一开始在0号手里
3	for (int i = 0; i < m; i++)
4	{
5	pos = (pos + k) % n; // 往前传k个位置，超出范围自动绕回开头
6	}
7	cout << "球最后在 " << pos << " 号手里";