算法简介

背景知识

算法描述

问题描述

程序描述

算法简介

蒙特·卡罗方法（Monte Carlo method），也称统计模拟方法，是二十世纪四十年代中期由于科学技术的发展和电子计算机的发明，而被提出的一种以概率统计理论为指导的一类非常重要的数值计算方法。是指使用随机数（或更常见的伪随机数）来解决很多计算问题的方法。蒙特·卡罗方法的名字来源于摩纳哥的一个城市蒙地卡罗，该城市以赌博业闻名，而蒙特·卡罗方法正是以概率为基础的方法。

与它对应的是确定性算法。

蒙特·卡罗方法在金融工程学，宏观经济学，计算物理学(如粒子输运计算、量子热力学计算、空气动力学计算)等领域应用广泛。

背景知识

[1946: John von Neumann, Stan Ulam, and Nick Metropolis, all at the Los Alamos Scientific Laboratory, cook up the Metropolis algorithm, also known as the Monte Carlo method.]

1946年，美国拉斯阿莫斯国家实验室的三位科学家John von Neumann,Stan Ulam 和 Nick Metropolis共同发明，被称为蒙特卡洛方法。它的具体定义是：在广场上画一个边长一米的正方形，在正方形内部随意用粉笔画一个不规则的形状，现在要计算这个不规则图形的面积，怎么计算呢?蒙特卡洛(Monte Carlo)方法告诉我们，均匀的向该正方形内撒N（N 是一个很大的自然数）个黄豆，随后数数有多少个黄豆在这个不规则几何形状内部，比如说有M个，那么，这个奇怪形状的面积便近似于M/N，N越大，算出来的值便越精确。在这里我们要假定豆子都在一个平面上，相互之间没有重叠。蒙特卡洛方法可用于近似计算圆周率：让计算机每次随机生成两个0到1之间的数，看这两个实数是否在单位圆内。生成一系列随机点，统计单位圆内的点数与总点数，（圆面积和正方形面积之比为PI:1，PI为圆周率），当随机点取得越多（但即使取10的9次方个随机点时，其结果也仅在前4位与圆周率吻合）时，其结果越接近于圆周率。

摘自《细数二十世纪最伟大的十种算法》CSDN JULY译

算法描述

以概率和统计理论方法为基础的一种计算方法。将所求解的问题同一定的概率模型相联系，用计算机实现统计模拟或抽样，以获得问题的近似解。比如，给定x=a，和x=b，你要求某一曲线f和这两竖线，及x轴围成的面积，你可以起定y轴一横线 y=c 其中c>=f(x)max，很简单的，你可以求出 y=c，x=a，x=b及 x轴围成的矩形面积，然后利用随机产生大量在这个矩形范围之内的点，统计出现在曲线上部点数和出现在曲线下部点的数目，记为：dotUpCount，dotDownCount，然后所要求的面积可以近似为 dotDownCount所占比例*矩形面积。

问题描述

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

程序描述

/**//*

利用蒙特卡洛算法近似求圆周率PI

VC++6.0

ZZH

*/

#include<iostream>

#include<cmath>

#include<ctime>

#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<COUNT;i++)

...{

x=rand()*1.0/RAND_MAX;

y=rand()*1.0/RAND_MAX;

if(InCircle(x,y)) num++;

}

cout<<"PI:"<<(num*4.0)/COUNT<<endl;

}

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

matlab 利用蒙特卡洛算法近似求圆周率PI

function y = metekaro(nums)

% 蒙特卡罗算法的简单模拟，输入nums对绝对值x,y都小于1的数(x,y)，通过落在圆内的点数来求pi

% 产生nums对坐标数据(x,y)

D = unifrnd(-1,1,nums,2);

% 落在圆中的点数

inCircle = 0;

% 获取行数,也即nums的值

rows = size(D,1);

% 对每一对数据进行检测

for i = 1:rows

% 如果落在圆内，圆内的点数+1，落在正方形内的点数就为nums的数值

if (D(i,1)^2 + D(i,2)^2) < 1

inCircle = inCircle + 1;

end

end

% 圆的面积/正方形的面积 = 圆内的点数/正方形内的点数

y = 4*inCircle/rows;

% 输出pi值

disp(['pi的近似值为：' num2str(y)])

计算结果：

>> metekaro(1000);

pi的近似值为：3.088

>> metekaro(100000);

pi的近似值为：3.1409

>> metekaro(10000000);

pi的近似值为：3.1413

python 利用蒙特卡洛算法近似求圆周率PI

import random

import time

random.seed()

nums=100000

i=range(1,nums)

s=0

print nums

print time.strftime('Str:%Y-%m-%d %H:%M:%S',time.localtime(time.time()))

for x in i:

a1=random.random()

a2=random.random()

if (a1*a1+a2*a2)<1:

s=s+1

print 1.0*s/nums*4

print time.strftime('End:%Y-%m-%d %H:%M:%S',time.localtime(time.time()))

运行结果：3.14248