【GESP】C++三级考试大纲知识点梳理, (7) (8) 枚举算法、模拟算法

发表于 2025/01/07 更新于 2025/01/08

作者 OneCoder

次浏览 16 分钟阅读

GESP C++三级官方考试大纲中，共有8条考点，之前已对前4个考点进行了总结梳理，5，6号考点是关于C++语言一维数据和字符串应用的，属于基本语言语法和应用范围，网上的资料很多，不再赘述（后续考纲中关于语言语法本身的要求，都不再赘述）。本文针对C++ (7) (8)号知识点进行总结梳理。

(7) (8) 理解枚举算法、模拟算法的原理及特点，可以解决实际问题。

在编程中，枚举算法和模拟算法都是常用的解决实际问题的方法，尤其是在面对复杂的组合、排列或者状态空间时。了解它们的原理和特点，能够帮助你在实际问题中灵活运用。下面，我将详细讲解这两种算法的原理、特点，以及如何应用它们来解决实际问题。

一、枚举算法

（一）枚举算法的原理

枚举算法（Exhaustive Search 或 Brute Force）是一种通过列举所有可能的解，检查每个解是否满足问题要求的算法。枚举算法的核心思想是遍历所有的可能性，找出符合条件的结果。枚举算法常用于解空间有限且可以直接遍历的场景。

（二）枚举算法的特点

简单易懂：实现简单，通常通过穷举每一种可能的方案来解决问题。
暴力求解：由于直接列举所有解，复杂度较高，可能会导致性能问题，尤其在解空间非常大的时候。
适用于小规模问题：在问题规模较小、解空间较小时，枚举算法能够快速找到解。
不一定高效：因为是遍历所有可能的解，所以时间复杂度通常很高。

（三）枚举算法的应用举例

旅行商问题：可以通过枚举所有可能的路径来求解最短路径。
数独问题：通过枚举所有可能的数字填充，判断是否符合数独规则。
密码破解：当密码的可能组合数量不多时，可以使用枚举算法尝试所有可能的密码。

枚举算法的代码示例：背包问题：

经典的 0-1 背包问题可以使用枚举法进行求解。我们可以列举出所有可能的物品选择方案，计算每个方案的总重量和总价值，从而选择最优方案。

0-1 背包问题（0/1 Knapsack Problem）是计算机科学中的一个经典的组合优化问题。它的基本形式是：给定一组物品，每个物品都有一个重量和一个价值，要求选择一些物品放入背包中，使得这些物品的总重量不超过背包的容量，并且它们的总价值最大化。每个物品只能选择一次，即放入背包或不放入背包，因此称为“0-1”背包问题。

  
#include <iostream>
#include <vector>
#include <algorithm>

struct Item {
    int weight;
    int value;
};

int knapsack(int W, const std::vector<Item>& items) {
    int n = items.size();
    int max_value = 0;

    // 枚举所有可能的选择方案
    for (int i = 0; i < (1 << n); ++i) {
        int total_weight = 0, total_value = 0;
        
        // 枚举每一位，决定是否选择物品
        for (int j = 0; j < n; ++j) {
            if (i & (1 << j)) {  // 如果第j个物品被选择
                total_weight += items[j].weight;
                total_value += items[j].value;
            }
        }

        // 如果选择的物品不超过背包容量，更新最大价值
        if (total_weight <= W) {
            max_value = std::max(max_value, total_value);
        }
    }

    return max_value;
}

int main() {
    int W = 50;  // 背包容量
    
    std::vector<Item> items = {{10, 60}, {20, 100}, {30, 120}};  // 物品的重量和价值
    

    int max_value = knapsack(W, items);
    std::cout << "Max value: " << max_value << std::endl;  // 输出最大价值

    return 0;
}

在这个示例中，我们枚举所有可能的物品选择方案，并计算每种方案的总重量和总价值，最终输出最大价值。

二、模拟算法

（一）模拟算法的原理

模拟算法是一种通过模拟系统或过程的执行来求解问题的方法。它通常不求解问题的精确解，而是通过模拟实际过程或者状态转移来获得近似的解。模拟算法适用于难以通过数学模型精确求解的问题，尤其是那些具有随机性或者复杂状态转移的问题。

（二）模拟算法的特点

处理复杂系统：模拟算法适合模拟复杂的动态系统，尤其是状态空间非常大、无法用精确数学方法求解的情况。
求解近似解：模拟算法通常能找到一个合理的近似解，而不是精确解。
灵活性高：模拟算法可以根据问题的特定要求进行灵活的调整和优化。
随机性：许多模拟算法（如蒙特卡罗方法）依赖于随机性，结果可能是概率性的。

（三）模拟算法的应用举例

蒙特卡罗方法：广泛应用于计算积分、模拟随机过程、优化问题等。
模拟退火：用于求解优化问题，特别是组合优化问题，例如旅行商问题。
遗传算法：模拟自然选择和基因遗传，用于寻找问题的最优解。

模拟算法的代码示例：蒙特卡罗方法估算圆周率：

蒙特卡罗方法是一种基于随机模拟的算法，常用于估算数值积分或者概率问题。利用蒙特卡罗方法估算圆周率 ${\pi}$ 是一个经典的应用实例。简要说明如下：

我们知道圆的周长和直径的比值就是圆周率 ${\pi}$。蒙特卡罗方法可以通过概率统计来估算圆周率。具体的做法是：通过随机生成点，并计算落入圆内的点的比例，从而间接计算出圆周率。

1.设置坐标系

假设我们在一个边长为 2 的正方形内进行随机撒点，这个正方形的左下角坐标是 $(-1, -1)$，右上角坐标是 $(1, 1)$，所以正方形的面积为 $4$。
在这个正方形内，内切一个半径为 1 的圆，圆心位于 $(0, 0)$，圆的面积为 $\pi$（因为半径为 1 的圆的面积是 $\pi \times r^2 = \pi \times 1^2 = \pi$）。

2.随机撒点

我们随机生成 $N$ 个点，每个点的坐标是 $(x, y)$，其中 $x$ 和 $y$ 的值都是在区间 $[-1, 1]$ 之间随机取值的。
对于每个点，我们可以用一个简单的条件来判断这个点是否在圆内：如果点 $(x, y)$ 满足 $x^2 + y^2 \leq 1$，则该点在圆内。

3.比例关系

圆的面积占正方形面积的比例是 $\frac{\pi}{4}$。
如果我们随机撒了 $N$ 个点，并且有 $M$ 个点落在圆内，那么落在圆内的点的比例是 $\frac{M}{N}$。
由于这个比例大约等于圆的面积与正方形面积的比值 $\frac{\pi}{4}$，因此我们可以通过以下公式来估算圆周率 $\pi$：

\[\frac{M}{N} \approx \frac{\pi}{4}\]

从而得到：

\[{\pi} \approx 4 \times \frac{M}{N}\]

4. 蒙特卡罗方法估算圆周率的步骤

初始化：设置总的随机点数 $N$，初始化计数器 $M$ 来记录落在圆内的点数。
随机撒点：在正方形内随机生成 $N$ 个点，每个点的坐标是 $(x, y)$，其中 $x$ 和 $y$ 都在 $[-1, 1]$ 区间内。
判断点是否在圆内：对于每个点，检查其是否满足条件 $x^2 + y^2 \leq 1$，如果满足，则认为该点落在圆内，增加计数器 $M$。
估算圆周率：使用公式 $\pi \approx 4 \times \frac{M}{N}$ 来估算圆周率。

代码示例：

  
#include <iostream>
#include <cstdlib>
#include <ctime>

int main() {
    int N = 1000000;  // 总的随机点数
    int M = 0;        // 落在圆内的点数
    srand(time(0));   // 设置随机数种子

    for (int i = 0; i < N; ++i) {
        // 随机生成 (-1, 1) 之间的 x 和 y 坐标
        double x = 2.0 * rand() / RAND_MAX - 1.0;
        double y = 2.0 * rand() / RAND_MAX - 1.0;

        // 判断点是否在圆内
        if (x * x + y * y <= 1.0) {
            ++M;  // 落在圆内的点数
        }
    }

    // 估算圆周率
    double pi = 4.0 * M / N;
    std::cout << "Estimated Pi = " << pi << std::endl;

    return 0;
}

5.结果分析

误差：由于这是基于随机抽样的估算，结果会存在误差。随着 $N$ 的增加，估算结果会更接近真实值，但由于是随机的，误差是不可避免的。
精度：通过增大点的数量 $N$，可以提高估算的精度。理论上，增加随机点的数量 $N$ 会使得结果越来越接近真实的圆周率值。

蒙特卡罗方法估算圆周率的核心思想是通过概率统计来估算几何图形的面积，进而推算圆周率。它通过随机生成点并计算落在圆内的点的比例来进行估算。随着随机点数的增加，估算结果会更加精确。虽然这种方法不如精确算法快，但它展现了随机模拟在数值计算中的强大应用。

三、总结：枚举算法 vs 模拟算法

特点	枚举算法	模拟算法
原理	列举所有可能的解，逐个检查并选出最优解	通过模拟系统过程或状态转移，获得近似解
适用场景	解空间较小或可以枚举的组合、排列问题	复杂的、状态空间巨大的问题，特别是无法精确求解的问题
计算复杂度	高，尤其是解空间大时	通常是近似算法，计算复杂度较低
结果	精确解	近似解，且有一定的误差
典型应用	背包问题、排列组合、密码破解等	蒙特卡罗方法、模拟退火、遗传算法等

枚举算法适合解决那些解空间较小、可以通过直接遍历所有可能性来找到最优解的问题。
模拟算法则适用于解空间巨大或问题本身复杂难以精确求解的情况，通常能提供一个近似解。

在实际应用中，选择哪种算法取决于问题的规模、精确度要求以及计算资源。如果问题规模较小且解空间有限，枚举算法是一个合适的选择；如果问题规模庞大或不易精确求解，则模拟算法可能更加合适。

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
GESP各级别考纲要点、知识拓展和练习题目清单详见C++学习项目主页
“luogu-”系列题目已加入洛谷Java、C++初学团队，作业清单，可在线评测，团队名额有限，欢迎加入。
“bcqm-”系列题目可在编程启蒙题库进行在线评测。

GESP, 三级

GESP C++

本文由作者按照 CC BY 4.0 进行授权