信奥赛C++编程之模拟算法的思想和实现要点

我是邹城怡悦编程万万,今天我们来说一下模拟算法的思想和实现要点.

1.模拟算法的思想

现实中,有一些问题很难找到公示或者规律,只能按照一定的步骤,不停的”模拟”最后才能得到答案.对于这类问题,用计算机求解非常合适,只要让计算机模拟人在解决此类问题时的行为即可.这种求解问题的方法,可以称为”模拟算法”

模拟是算法竞赛时经常采用的方法.适合这种算法的题目大多带有游戏性质.关键在于理解游戏的规则和过程,用程序实现时采用适当的数据结构表达题目的状态,然后按照游戏规则模拟游戏过程.

所以说,模拟算法的本质,是采用合适的数据结构,模拟游戏的过程或者问题求解的过程,在此过程中,一般要进行一定的判断或者记录

2.模拟算法的实现要点

(1).采用合适的数据结构来表示问题.比如,迷宫问题可以采用二维数组存储迷宫地图.常用的数据结构包括数组,结构体,队列,栈,树,二叉树,图等等.最简单,最适合问题求解的数据结构,就是最好的数据结构

(2)在模拟的过程中,通常要记录或者更新问题的中间状态,方便下一步在此状态的基础上继续模拟

(3)采用模拟法求解问题时,可能出现一种情况,就是当问题规模很小时,可以直接模拟,当问题规模较大时直接模拟会超时或者内存超过限制.这时候要分析问题的规律,可以把问题的规模变小再模拟.

(4)如果采用普通的模拟思路求解,提交答案被评判为超时,那就要分析题目是否符合分治,动态规划,贪心等优化算法的条件,可能需要这些算法解决.