---
title: "模拟法"
description: "枚举、模拟、贪心、递归、二分、动态规划、图论等经典算法。"
---

> Documentation Index
> Fetch the complete documentation index at: https://cppguide.xyz/llms.txt
> Use this file to discover all available pages before exploring further.

# 模拟法

![](https://img.dailyup.xyz/originals/8208463019652-b97af088-4db9-442a-a796-2da195ab3276.png)

模拟法（Simulation Method） 是一种朴素的算法思想，也最直观的算法之一，其核心思想是对问题进行描述，按照问题发生的先后、逻辑顺序，对问题的过程进行编码实现，最终解决该问题，简单来说就是，题目怎么说，你就怎么做。

想像一下，你要组装一个模型，最直接的方法是什么，就是严格按照说明书上的步骤，一步一步地操作：找到零件 A，连接到零件 B，再与部件 C 组合在一起 ...

模拟法的核心思想与此类似，就是直接地、按照题目描述的过程或规则，一步一步地在计算程序中“重现”这个过程。

模拟法的特点是直观，通常并不需要特别复杂的算法设计，只要把问题描述清楚，按照问题的逻辑编码实现即可，对于初学者来说非常适合。

然而，有的问题本身细节错综复杂，模拟写的过程很容易犯错误，非常考查编程人员的**阅读理解能力**（能否准确理解题目规则）、**逻辑思维能力**（能否把规则转化为清晰的步骤）和**编程实现能力**（能否把步骤用正确的代码实现）。

## 模拟法解决什么样的问题

模拟法主要用于解决那些过程明确、规则具体的问题，比如说：
- 描述一个场景、一个游戏、一个物理过程或一套操作流程。
- 给出明确的初始状态。
- 定义状态如何随着时间、事件或操作而变化。
- 要求你计算最终状态、过程中的某个特定值或判断是否达到某个条件。

主要应用场景：

- **游戏模拟：** 棋类游戏（如判断胜负）、卡牌游戏、俄罗斯方块等。
- **物理过程模拟：** 小球运动、粒子碰撞等（通常简化）。
- **指令执行：** 模拟计算机指令、机器人移动指令等。
- **日期和时间计算：** 模拟日历变化、时间流逝。
- **按照特定规则处理数据：** 例如，按照一套复杂的规则格式化文本、处理字符串等。

## 如何使用模拟法

使用模拟法解决问题，通常遵循以下步骤：

【补充内容】

## 示例：机器人移动

一个机器人在一个无限大的二维平面上，初始位置在 (0, 0)。给定一个操作字符串，包含 'U', 'D', 'L', 'R' 四种字符，分别代表向上、向下、向左、向右移动一个单位。编程计算机器人在执行完所有操作后的最终位置。

例如，输入数据

```
UDDDRLRRDUR
```

应该输出：

```
3 -2
```

**问题分析**

题目并不复杂，规则也很简单，就是根据指令移动，整个变化的状态就是机器人的 `x` 坐标与 `y` 坐标，遍历输入的操作字符串，根据每个字符来更新 `x` 或 `y` 即可。

**参考代码**

```cpp
#include <bits/stdc++.h> // 万能头文件
using namespace std;     // 使用 std 命名空间

int main() {
	// 初始化状态
	int x = 0;
	int y = 0;
	
	// 读取输入的操作字符串
	string ops;
	cin >> ops;
	
	//按操作序列分解，模拟执行每一步
	
	for (int i = 0; i < ops.size(); ++i) {
		char op = ops[i]; // 获取当前操作
	
		// 根据规则更新状态
		if (op == 'U') {
			y++; // 向上移动，y 坐标增加
		} else if (op == 'D') {
			y--; // 向下移动，y 坐标减少
		} else if (op == 'L') {
			x--; // 向左移动，x 坐标减少
		} else if (op == 'R') {
			x++; // 向右移动，x 坐标增加
		} 
	}
	
	// 输出最终结果
	cout << x << " " << y << endl;
	
	return 0;
}

```
## 示例：角谷猜想

**题目描述**

日本一位中学生发现一个奇妙的定理，请角谷教授证明，而教授无能为力，于是产生了角谷猜想。

猜想的内容：任给一个自然数，若为偶数则除以 2 ，若为奇数则乘 3 加 1 ，得到一个新的自然数后按上面的法则继续演算。若干次后得到的结果必为 1 。

请编写代码验证该猜想：求经过多少次运算可得到自然数 1 。

如：输入 22 ，则计算过程为。

```
22/2=11
11*3+1=34
34/2=17
17*3+1=52
52/2=26
26/2=13
13*3+1=40
40/2=20
20/2=10
10/2=5
5*3+1=16
16/2=8
8/2=4
4/2=2
2/2=1
```

经过 15 次运算得到自然数 1 。

**输入描述**

一行，一个正整数 $n$ 。（$1 \le n \le 20000$）

**输出描述**

一行，一个整数，表示得到 1 所用的运算次数。

**输入输出样例**

输入数据

```
22
```

输出数据

```
15
```

**代码实现**

```cpp
#include <iostream>
using namespace std;

int main() {
    int n, cnt = 0;
    cin >> n;
    
    while (n != 1) {
      if (n % 2 == 0) n = n / 2;
      else n = n * 3 + 1;
      cnt++;
    }
    
    cout << cnt << endl;
    
    return 0;
}
```

## 模拟法的挑战

使用模拟法通常比较直接，只要理解了题目，就可以往下做，适合那些没有明显数学规律或算法套路的问题。

但如果题目规则复杂，使用模拟法实现的代码可能会很长，细节也比较多，容易在小地方出错，比如边界条件、更新顺序等。

另外，时间限制通常是模拟法的最大敌人，如果要模拟的步数非常多，而每一步操作又需要一定时间，那么总的时间复杂度可能会很高，超出题目允许的时间限制。因此在使用模拟法前，**一定要根据数据范围估算总操作次数，判断是否会超时**。如果预估会超时，那么就需要寻找更优化的算法（比如数学方法、动态规划、数据结构优化等）。

## 对竞赛选手的建议

- **永远先读题，再思考：** 不要没完全理解题目就开始写代码。模拟题尤其考验细心。
- **估算复杂度是习惯：** 看到题目给的数据范围，立刻估算模拟的总计算量，判断是否可行。`10^8` 大约是 1 秒的计算量上限，要留有余地。
- **从简单例子开始：** 先手动模拟样例，再写代码跑样例。
- **代码风格要清晰：** 使用有意义的变量名，适当添加注释，将复杂的逻辑封装成函数，有助于减少错误和方便调试。
- **注意边界：** 特别关注循环的起始和结束条件，数组是否越界，特殊值（0, 1, 最大值）的处理。
- **模拟是保底手段：** 如果想不到更优的算法，或者时间紧张，写一个正确的模拟通常能拿到一部分分数。但要时刻警惕 TLE 的风险。

## 小结

模拟，是解决很多问题的起点，很多复杂算法也是在理解了基本模拟过程的基础进行优化得来的。因此，模拟法也是竞赛中一个必备的基础技能，熟练掌握模拟，并能准确判断其是否适用（特别是时间复杂度），也是一名竞赛选手成长路上的重要一步。

Source: https://cppguide.xyz/algorithm/simulation/index.mdx