第13章程序设计基础课件.ppt

1、第十三章第十三章 蒙特卡罗法蒙特卡罗法内内 容容 要要 点点 伪随机数的产生 伪随机数的应用 求 的近似值 近似计算几何图形面积蒙特卡罗蒙特卡罗(Monte Carlo)方法方法，或称 计算机随机模拟方法计算机随机模拟方法，是一种基于“随机数”的计算方法。Monte Carlo方法的基本思想很早就被人们发现和利用。早在方法的基本思想很早就被人们发现和利用。早在18世纪，世纪，人们用人们用投针试验投针试验(Buffon needle experiment)的方法计算圆周率的方法计算圆周率。计算机（特别是高速计算机）的出现使得类似的模拟试验成为可能。计算机（特别是高速计算机）的出现使得类似的模拟试

2、验成为可能。考虑平面上一个边长为考虑平面上一个边长为 1 的正方形及其内部的一个形状不规则的的正方形及其内部的一个形状不规则的“图形图形”，如何求这个，如何求这个“图形图形”的面积？的面积？Monte Carlo 方法是这方法是这样一种样一种“随机化随机化”的方法：向该正方形的方法：向该正方形“随机地随机地”投掷投掷 M 个点，个点，其中有其中有N个点落于个点落于“图形图形”内，则该内，则该“图形图形”的面积近似为：的面积近似为：N/M。蒙特卡罗方法在金融工程学、宏观经济学、计算物理学等领域应用蒙特卡罗方法在金融工程学、宏观经济学、计算物理学等领域应用广泛。科技计算中的复杂问题，如金融衍生产品

3、（期权、期货等）广泛。科技计算中的复杂问题，如金融衍生产品（期权、期货等）的定价及交易风险估算，可采用的定价及交易风险估算，可采用Monte Carlo方法加以解决。方法加以解决。#include#include /for rand()using namespace std;int main()int k=0;for(k=0;k10;k+)/循环输出随机数循环输出随机数 cout rand()endl;cout最大随机数为最大随机数为RAND_MAXendl;/输出最大随机数输出最大随机数 return 0;这些数字并不是绝对意义上的随机数字，这些数字并不是绝对意义上的随机数字，常称之为常称之

4、为 伪随机数伪随机数(pseudorandom)例：产生例：产生10个随机整数个随机整数#include#include /for srand()#include /for time()using namespace std;int main()int k=0;srand(unsigned int)time(NULL);for(k=0;k10;k+)cout rand()endl;cout最大随机数为最大随机数为RAND_MAXendl;return 0;例：产生例：产生10个随机整数个随机整数随机数的产生方法：随机数的产生方法：（1）随机数表：）随机数表：事先做好一张包含随机数的表，使用的

5、时候通过查表就可以获得随机数。随机数表在计算机中占很大内存，难以满足蒙特卡罗方法 对随机数需求量非常大的要求。（2）物理方法：）物理方法：利用某些物理现象，在计算机上增加特殊 设备，直接产生随机数。这些特殊设备称为随机数发 生器。用来作为随机数发生器的物理源主要有两种：一种是根据放射性物质的放射性，另一种是利用计算 机的固有噪声。随机数序列无法重复实现，不能进行程序复算，给验证结 果带来很大困难；需要增设附加设备，费用昂贵。（3）通过算法在计算机上产生伪随机数伪随机数随机数的数学定义：随机数的数学定义：在连续型随机变量的分布中，最简单而且最基本的分布是单位均匀分布。由该分布抽取的简单子样称为随

6、机数序列，其中每一个体称为随机数。单位均匀分布即0，1上的均匀分布。由随机数的定义可知，独立性、均匀性是随机数必备的两个特点。独立性、均匀性独立性、均匀性是随机数必备的两个特点。用数学方法产生的随机数存在两个问题：（1）递推公式和初始值确定后，整个随机数序列便被唯一 确定，不满足随机数相互独立的要求。（2）由于随机数序列是由递推公式确定的，而计算机所能 表示的随机数又是有限的，因此产生的随机数序列就 不可能不出现无限重复。伪随机数的产生方法：乘同余方法：乘同余方法：x(i+1)=a*x(i)(MOD M)a 为一常数 乘加同余方法：乘加同余方法：x(i+1)=(a*x(i)+c)(MOD M)

7、a,c 为一常数 1、要产生随机数，需要有头文件#include 2、rand()是产生随机数的函数，它可生成 0 32767 内的整数3、最大随机数为RAND_MAX，值为327674、产生随机数需要设置种子(seed)，即带有时钟 time 参数：srand(unsigned int)time(NULL);因为时间每分每秒不同，第一个随机数就不会固定。5、要使用时钟 time，需要有头文件#include 说明：int rand_int(int a,int b)return a+rand()%(b-a+1);int main()int seed=time(NULL);srand(seed)

8、;for(int k=0;k10;k+)int d1=rand_int(1,6);int d2=rand_int(1,6);cout d1 d2 endl;return 0;例：产生16之间的随机数int main()int k=0;srand(unsigned int)time(NULL);for(k=0;k10;k+)cout (float)rand()/RAND_MAX endl;return 0;例：产生10个随机小数例：求例：求的近似值的近似值正方形的面积 A=1；1/4圆的面积 B=/4。1/4圆的容器内的水重C，正方形中的水重D。CBDA;44CCDD 1 x y 1 0 让计算

9、机产生随机数 x 和 y，x 的范围在 01 之间，y 的范围也在 01 之间。模拟雨点落在正方形中，当然会有雨点落在1/4圆中，数以百万计的雨点累计得到 C 和 D，根据上述公式算出的近似值。如果满足条件：表明雨点落在1/4圆中，则让 C=C+1221xy#include#include#include#include using namespace std;int main()long k=0,c=0,d=0;float pai=0.0,x=0.0,y=0.0;srand(unsigned int)time(NULL);/设置种子设置种子 for(k=1;k=10000000;k+)d=d

10、+1;/累加正方形中落入的雨点累加正方形中落入的雨点 x=(float)rand()/32767;/雨点在雨点在x方向的位置方向的位置 y=(float)rand()/32767;/雨点在雨点在y方向的位置方向的位置 if(sqrt(x*x+y*y)=1)c=c+1;/累加扇形中落入的雨点累加扇形中落入的雨点 pai=4.0f*(float)c/d;/计算计算pai的值的值 coutpai=paiendl;return 0;多次计算下的运行结果：多次计算下的运行结果：k=107k=107k=103k=104k=105 k=106k=107k=108多次计算下的运行结果：多次计算下的运行结果：例

11、：计算图形的面积：1 x y 1 221xy 22(1)1xy 要同时满足公式1和公式2，雨点才能落入阴影内：2211xy公式22(1)1xy公式2为了查看所得结果是否有效，程序中给出了s 的精确值：A A B 30 30 A为1/12的圆面积(半径为1)B为边长是1的等边三角形面积int main()long k=0,d=0,g=0;float s=0.0,x=0.0,y=0.0;srand(unsigned int)time(NULL);for(k=1;k1)&(sqrt(x-1)*(x-1)+y*y)1)g=g+1;/累加阴影面积中落入的雨点累加阴影面积中落入的雨点 s=(float)g/d;/计算计算s的近似值的近似值 cout s的近似值为的近似值为 s endl;cout s的精确值为的精确值为 1.0-(3.14159/6.0+1.73205/4.0)endl;return 0;k=107k=108