因为很多数学问题，往往没有或者很难计算解析，这时候便需要通过数值计算来求解近似值.概率算法依照概率统计的思路来求解问题，其往往不能得到问题的精确解，但是在数值计算领域有着广泛应用.
概率算法执行的基本过程如下：
- 将问题转化为相应的几何图形S，S的面积是容易计算的，问题的结果往往对应几何图形中某一部分S1的面积.
- 然后，向几何图形中随机撒点.
- 统计几何图形中S中和S1中的点数，根据S的面积和S1面积的关系以及各图形中的点数来计算得到结果.
- 判断上述结果是否在需要的精度之内，如果未达到精度则进行执行步骤2.如果达到精度，则输出近似结果.
概率算法大致分为如下4中形式：
- 数值概率算法；
- 蒙特卡洛(Monte Carlo)算法；
- 拉斯维加斯(Las Vegas)算法；
- 舍伍德(Sherwood)算法；
下面我们通过一个实例来看看蒙特卡罗概率算法的应用.蒙特卡洛算法的一个典型应用便是计算圆周率pi.
MonteCarlo
对于图中圆的面积有如下公式
而图中阴影部分是一个圆的1/4,因此阴影部分的面积有如下的计算公式
图中正方形的面积为:
此时,如果均匀地向正方形内撒点,那么落入阴影部分的点数与全部的点数之比应该就是:
public class Solution {
public double MontePI(int n) {
double PI = 0;
int sum = 0;
int i = n;
while (i > 0) {
double x = Math.random();
double y = Math.random();
if ((x * x + y * y) < 1) {
++sum;
}
--i;
}
PI = (double) sum / n * 4;
return PI;
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.MontePI(100000000));
}
}
运行结果
