一、蒙特·卡罗(Monte Carlo)方法简介

图2：蒙卡程序模块简图

蒙特卡罗方法(Monte Carlo Method)也称为计算机随机模拟方法，是一种基于"随机数"的计算方法，是一类随机方法的统称。这类方法的特点是，可以在随机采样上计算得到近似结果，随着采样的增多，得到的结果是正确结果的概率逐渐加大，但在(放弃随机采样，而采用类似全采样这样的确定性方法)获得真正的结果之前，无法知道目前得到的结果是不是真正的结果。

1946年，美国拉斯阿莫斯国家实验室(Los Alamos National Lab)的三位科学家John von Neumann(冯诺依曼)，Stan Ulam(斯坦乌尔姆)和Nick Metropolis(尼克梅特珀利斯)共同发明，被称为蒙特卡洛方法。具体定义是：在广场上画一个边长一米的正方形，在正方形内部随意用粉笔画一个不规则的形，现在要计算这个不规则图形的面积，蒙特卡洛(Monte Carlo)方法告诉我们，均匀的向该正方形内撒N(N是一个很大的自然数)个黄豆，随后数数有多少个黄豆在这个不规则几何形状内部，比如说有M个，那么，这个奇怪形积与正方形的面积之比便近似于M/N，N越大，算出来的值便越精确。在这里我们要假定豆子都在一个平面上，相互之间没有重叠。

举例说明，一个有10000个整数的集合，要求其中位数，可以从中抽取m