3.6　概率算法思想

概率算法依照概率统计的思路来求解问题，其往往不能得到问题的精确解，但是在数值计算领域得到了广泛的应用。因为很多数学问题，往往没有或者很难计算解析，此时便需要通过数值计算来求解近似值。

3.6.1　概率算法基本思想

概率算法执行的基本过程如下：

（1）将问题转化为相应的几何图形S，S的面积容易计算，问题的结果往往对应几何图形中某一部分S1的面积。

（2）然后，向几何图形中随机撒点。

（3）统计几何图形S和S1中的点数。根据S和S1面积的关系及各图形中的点数来计算得到结果。

（4）判断上述结果是否在需要的精度之内，如果未达到精度则执行步骤（2）。如果达到精度，则输出近似结果。

概率算法大致分为如下4种形式：

・数值概率算法；

・蒙特卡罗（Monte Carlo）算法；

・拉斯维加斯（Las Vegas）算法；

・舍伍德（Sherwood）算法；

3.6.2　概率算法实例

下面通过一个实例来分析蒙特卡罗（Monte Carlo）概率算法的应用。蒙特卡罗算法的一个典型应用便是计算圆周率π。

1.蒙特卡罗π算法思想

使用蒙特卡罗算法计算圆周率π的思想其实比较简单。首先分析一个半径为1的圆，如图3-5所示。图中圆的面积的计算公式如下：

S圆=π*r2

图中阴影部分是一个圆的1/4，因此阴影部分的面积的计算公式如下：

图中正方形的面积为：

S正方形=r2=1

按照图示建立一个坐标系。如果均匀地向正方形内撒点，那么落入阴影部分的点数与全部的点数之比为：

S阴影/S正方形=π/4

根据概率统计的规律，只要撒点数足够多，那么将得到近似的结果。通过这个原理便可以计算圆周率π的近似值，这就是蒙特卡罗π算法。

使用蒙特卡罗算法计算圆周率π有如下两个关键点。

・均匀撒点：在C语言中可以使用随机方法来实现，产生[0，1]之间随机的坐标值[x，y]。

・区域判断：图中阴影部分的特点是距离坐标原点的距离小于等于1，因此，可以通过计算判断x2+y2≤1来实现。

使用蒙特卡罗算法计算圆周率π的代码示例如下：

其中，输入参数n为撒点数。该方法完全遵循了前面的蒙特卡罗算法过程，返回值便是圆周率π的近似值。

2.蒙特卡罗概率算法计算π实例

下面结合例子来分析蒙特卡罗概率算法在计算π时的使用。完整的程序代码示例如下：

【程序3-5】

在程序中，主方法首先接收用户输入的撒点数，然后调用MontePI（）算法方法计算圆周率π的近似值。该程序执行的结果，如图3-6所示。

读者可以多次执行该程序，会发现撒点数越多，圆周率π计算的精度也就越高。同时，由于概率算法的随机性，在不同的运行时间，即使输入同样的撒点数，得到的结果也是不相同的。