题目

蒙特卡罗算法的典型应用之一为求圆周率PI问题。

思想：

一个半径r=1的圆，其面积为：S=PI∗r2=PI/4

一个边长r=1的正方形，其面积为：S=r2=1

那么建立一个坐标系，如果均匀的向正方形内撒点，那么落入圆心在正方形中心，半径为1的圆内的点数与全部点数的比例应该为PI/4，根据概率统计的规律，只要撒的点足够多，那么便会得到圆周率PI的非常近似的值。

蒙特卡罗算法关键

使用蒙特卡罗算法计算圆周率有下面两个关键点：

1. 均匀撒点：在C语言中可用随机函数来实现，产生[0，1)之间随机的坐标值(x,y)；
2. 区域判断：位于圆内的点的特性是其与圆心的距离小于等于1，这样可用x2+y2<=1来判断；

概率算法基本思想

概率算法是依照概率统计的思路来求解问题的算法，它往往不能得到问题的精确解。

执行的基本过程如下：

1. 将问题转换为相应的几何图形S，S的面积是容易计算的，问题的结果往往对应几何图形某一部分S1的面积；
2. 然后，向几何图形中随机撒点；
3. 统计几何图形S和S1中的点数，根据面积关系得结果；
4. 判断精度，满足要求则输出，不满足则返回(2)；

概率算法大致分为以下4类：

1. 数值概率算法
2. 蒙特卡罗（Monte Carlo）算法
3. 拉斯维加斯（Las Vegas）算法
4. 舍伍德（sherwood）算法

代码实现

#include <iostream>

#include <cstdlib>

#include <ctime>

using namespace std;

double MontePI(int n)

{

    double PI;

    double x, y;

    int sum = 0;

    srand(time(NULL));

    for (int i = 0; i < n; i++)

    {

        x = (double)rand() / RAND_MAX; //产生0~1之间的一个随机数

        y = (double)rand() / RAND_MAX; 

        if (x*x + y*y <= 1)

            sum++;

    }//for

    PI = 4.0 * sum / n;

    return PI;

}

int main()

{

    int n;

    double PI;

    cout << "蒙特卡罗算法求圆周率PI：" << endl;

    cout << "输入点数：" << endl;

    while (cin >> n)

    {

        PI = MontePI(n);

        cout << PI << endl;

    }

    system("pause");

    return 0;

}

GitHub源码下载