基于Mapreduce的蒙特卡洛算法 李小兵组

                   

                                    蒙特卡洛算法

                

                                 组员  李小兵 周立 冯俊 李继华 艾海提

                    

                       应用举例和程序

问题描述

　　在数值积分法中，利用求单位圆的1/4的面积来求得Pi/4，从而得到Pi。单位圆的1/4面积是一个扇形，它是边长为1单位正方形的一部分。只要能求出扇形面积S1在正方形面积S中占的比例K=S1/S就立即能得到S1，从而得到Pi的值。怎样求出扇形面积在正方形面积中占的比例K呢？一个办法是在正方形中随机投入很多点，使所投的点落在正方形中每一个位置的机会相等看其中有多少个点落在扇形内。将落在扇形内的点数m与所投点的总数n的比m/n作为k的近似值。Pi=4m/n。P落在扇形内的充要条件是x^2+y^2<=1。

程序

 利用蒙特卡洛算法近似求圆周率PI
 VC++6.0
 ZZH
#include
#include
#include
#define COUNT 500000 //循环取样次数

using namespace std;

bool InCircle(double x,double y)//是否在1/4圆范围之内
...{
    if((x*x+y*y)<=1)return true;
    return false;
}
void main()
...{
    double x,y;
    int num=0;
    int i;

    srand((unsigned)time(NULL));
    for(i=0;i    ...{
        x=rand()*1.0/RAND_MAX;
        y=rand()*1.0/RAND_MAX;
        if(InCircle(x,y)) num++;
    }
    cout<<"PI:"<<(num*4.0)/COUNT<}

 

结果：测试5次的结果显示：3.13958，3.14041，3.13729，3.13859，3.14186

 

蒙塔卡洛算法的其他应用：比较简单的有随机抽样，通过坐标的变换产生球面，圆面，正方体面等等所需要的抽样。在某些计算机模拟过程中，可以随机产生噪声，比如说水中花粉随机行走之类的问题，可以用来随机产生外界水分子的作用力，用来模拟现实情况。当然也可以用这种方式来近似某些科学计算，最简单的例子就是近似计算积分。对于某些计算机无法完全枚举的优化问题，也可以用蒙特卡洛方法得到较好的解，常见的比如模拟退火，量子退火等优化方法，都用到了蒙特卡洛算法。

下次将步入主题，运用并行算法来测试蒙特卡洛算法，敬请期待。