实验5 蒙特卡罗法求PI及排序算法

《实验5 蒙特卡罗法求PI及排序算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、浙江大学城市学院实验报告课程名称多核与并行程序设计实验项目名称实验五蒙特卡罗法求PI及排序算法学生姓名专业班级学号实验成绩指导老师（签名）日期【实验环境】硬件平台：联想4核,4GZ内存编译器：MicrosoftVisualStudioC++6.0操作系统：Windows2003serversp2测试数据集合：由随机数函数产生的数据集合【实验1】一、问题描述蒙特卡洛算法可理解为通过大量实验，模拟实际行为，来收集统计数据。本例中，算法随机产生一系列点，模拟这些点落在如下图所示的正方形区域内的情况。其几何解释如下图

2、1如图1所示，正方形边长为1，左下顶点与原点重合，两边分别与x，y轴重合。曲线为1/4圆弧，圆心位于原点，与正方形左下定点重合，半径为1。正方形面积S1=1，圆弧内面积S2=。算法模拟大量点随机落在此正方形区域内，落在圆弧内的点的数量（n2）与点的总数（n1）的比例与面积成正比关系。即9（1）由此可得（2）因此，只要计算出落在圆弧内的点的数量在点总数中所占的比例，就能求出的值。由图1可知，所有点均落在正方形范围内，因此点的x坐标满足。又，当点落在圆弧范围内，则点的二维坐标关系满足。检验每一个点是否满足此关系即

3、可判定改点是否落在圆弧内。二、串行算法描述本项目中使用了标准C语言库中的产生随机数函数。该函数原型为：intrand(void);此函数产生随机数列，每次调用时均返回0到RAND_MAX之间的一个整数。voidsrand(unsignedintseed);此函数为rand（）函数所生成的伪随机数序列设置起始点，使之产生不同的伪随机数。算法：产生2n个随机数据，范围[0，1]，对每个数据点计算其坐标是否满足，统计满足此关系的点的数量count，则三、并行算法3.1并行算法描述算法步骤：1、确定需要产生的点的个数

4、n，参与运行的处理器数m；2、对每一个处理器，生成两个随机数x，y，范围[0，1]；3、判断两个随机数x，y是否满足；94、若满足，则变量COUNTi++；5、重复步骤2-4，直至每个处理器均生成n/m个随机点；6、收集COUNTi的值，并累加至变量COUNT中，此即为随机点落在圆弧内的数量；7、通过（2）式计算的值。3.2并行算法在Windows下的一个例子#include#include#include//#include#in

5、clude#include#includeusingnamespacestd;HANDLEevFinish;longcs=0;//总循环次数longcount=0;//主线程有效次数longcount_thread=0;//thread线程有效次数time_tstart,finish;//定义开始结束时间//thread线程计算量为总数的一半DWORDWINAPIthread(LPVOIDparam)//这个函数在PDF里WaitForSingleOb

6、ject(evFinish,INFINITE);//两线程同步count+=count_thread;finish=time(NULL);//记录结束时间printf("并行情况：");printf("用时=%f秒",difftime(finish,start));//计算时间差printf("总共的循环次数=%d次",cs);printf("线程有效次数=%d次",count);printf("pi=%f",4*(double)count/(double)cs);printf("串行

7、行情况：");count=0;start=time(NULL);//记录开始时间for(i=0;i

8、,difftime(finish,start));printf("总共的循环次数=%d次",cs);printf("线程有效次数=%d次",count);printf("pi=%f",4*(double)count/(double)cs);return(0);}四、实验结果1、实验运行结果是多少2、本例中加速比（串行时间/并行时间）：S=【实验2】一、问题描述在单核计算环境中，排序算法关