基本算法思想之概率

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

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

1. 将问题转化为相应的几何图形S，S的面积是容易计算的，问题的结果往往对应几何图形中某一部分S1的面积.
2. 然后，向几何图形中随机撒点.
3. 统计几何图形中S中和S1中的点数，根据S的面积和S1面积的关系以及各图形中的点数来计算得到结果.
4. 判断上述结果是否在需要的精度之内，如果未达到精度则进行执行步骤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));
    }
}

运行结果