《算法设计编程实验：大学程序设计课程与竞赛训练教材》——第2章 模拟法的编程实验

模拟法原本是科学实验的一种方法，即先在实验室里设计出与研究现象或过程（原型）相似的模型，然后根据模型和原型之间的相似关系，间接地研究原型的规律性。这种实验方法后来被引入到计算机编程。原因是要求编程解决的许多问题具有不确定的性质，有些问题甚至很难建立数学模型，或者很难建立递推、递归、枚举、回溯法等常用算法。在这种情况下，一般采用模拟策略，即编程模拟某个过程，通过改变数学模型的各种参数，进而观察变更这些参数所引起过程状态的变化，由此展开算法设计。计算机模拟一般从形成问题到最后模拟实验需经过七个步骤（如图2-1所示）：

1）形成问题，明确模拟的目的和要求。

2）尽可能收集和处理与问题相关的数据。

3）形成数学模型。找出影响问题解决的各个要素，并描述它们在各时刻的状态的有关变量（一般包括输入变量、状态变量和输出变量）或参数；确定各要素之间相互作用和影响的规则，即描述变量之间的函数关系。选择参数和变量的时候，还须考虑它们能否辨识或求解，以及模型最后是否适于检验。注意，模型一般分为两种：

重现型，即模型能重现真实的过程或性能。

预测型，即模型能有效预测未来的趋势。

由于模拟过程一般是随时间或指令的顺序变化的，因此通常采用按时序模拟或按指令行事的方法。

4）根据收集的数据确定或估计模型中的参数，并选择模型的初始状态。

5）设计算法，编制程序。

6）程序验证，检验程序与数学模型之间的一致性,以及输入量的合理性。

7）进行模拟实验，对给定的输入在计算机上执行程序。分析结果数据，收集和整理实验结果并作出解释。必要时可改变输入量或部分模型结构，重新进行实验。

编程模拟的形式一般有两种：

1）随机模拟：题目给定或者隐含某一概率，设计者利用随机函数设定某一范围的随机值，将符合概率的随机值作为参数。然后根据这一模拟的数学模型展开算法设计。由于解题过程借助了计算机的伪随机数发生数，其随机的意义要比实际问题中真实的随机变量稍差一些，因此模拟效果有不确定的因素。

2）过程模拟：题目不给出概率，要求编程者按照题意设计数学模型的各种参数，观察变更这些参数所引起过程状态的变化，由此展开算法设计。模拟效果完全取决于过程模拟的真实性和算法的正确性，不含任何不确定因素。由于过程模拟的结果无二义性，因此acm竞赛大都采用过程模拟。

本章着重介绍过程模拟，展开三种模拟方法的实验：

1）直叙式模拟。

2）筛选法模拟。

3）构造法模拟。