0042算法笔记【随机化算法】计算π值和计算定积分.docxVIP

1、计算π值? ??问题描述? ? 设有一半径为r的圆及其外切四边形。向该正方形随机地投掷n个点。设落入圆内的点数为k。由于所投入的点在正方形上均匀分布，因而所投入的点落入圆内的概率为 ? ? ? ? ??。所以当n足够大时，k与n之比就逼近这一概率。从而。? ? 程序具体代码如下：[cpp]?view plain?copy//随机化算法?用随机投点法计算π值??#include?stdafx.h??#include?RandomNumber.h??#include?iostream??using?namespace?std;????double?Darts(int?n);????int?main()??{??????int?n1?=?100,n2?=?1000,n3?=?1000,n4?=?10000,n5?=??????coutn1=n1,π1=Darts(n1)endl;??????coutn2=n2,π2=Darts(n2)endl;??????coutn3=n3,π3=Darts(n3)endl;??????coutn4=n4,π4=Darts(n4)endl;??????coutn5=n5,π5=Darts(n5)endl;??????return?0;??}????//用随机投点法计算π值??double?Darts(int?n)??{??????static?RandomNumber?dart;??????int?k?=?0;????????for(int?i=1;?i=n;?i++)??????{??????????double?x?=?dart.fRandom();??????????double?y?=?dart.fRandom();??????????if((x*x?+?y*y)=1)??????????{??????????????k++;??????????}??????}????????return?4*k/double(n);??}??? ? ?程序运行结果如图：? ? 2、计算定积分? ??例：设f(x)=x^2,求? ? 解：? ??1)随机投点法计算定积分??? ?基本思想是在矩形区域上随机均匀的投点实现。本算法的基本思想是在积分区间上随机均匀的产生点, 即在[a,b]上随机均匀的取点, 求出由这些点产生的函数值的算术平均值, 再乘以区间宽度, 即可解出定积分得近似解。? ? 算法具体代码如下：[cpp]?view plain?copy//随机化算法?用随机投点法计算定积分??#include?stdafx.h??#include?RandomNumber.h??#include?iostream??using?namespace?std;????double?Darts(int?n,double?a,double?b);??double?f(double?x);????int?main()??{??????int?n1?=?100,n2?=?1000,n3?=?1000,n4?=?10000,n5?=??????double?a?=?2.0,b?=?3.0;??????coutn1=n1,r1=Darts(n1,a,b)endl;??????coutn2=n2,r2=Darts(n2,a,b)endl;??????coutn3=n3,r3=Darts(n3,a,b)endl;??????coutn4=n4,r4=Darts(n4,a,b)endl;??????coutn5=n5,r5=Darts(n5,a,b)endl;??????return?0;??}????/*??*?基本思想是在矩形区域内随机均匀投点，求出由这些点??*?产生的函数值的算术平均值，再乘以区间宽度，即可得??*?出定积分的近似解??*/??double?Darts(int?n,double?a,double?b)??{??????static?RandomNumber?dart;??????double?sum?=?0.0;??????for(int?i=0;?in;?i++)??????{??????????double?x?=?(b-a)*dart.fRandom()?+?a;//产生[a,b)之间的随机数??????????sum?=?sum?+?f(x);??????}??????return?(b-a)*sum/n;??}????double?f(double?x)??{??????return?x*x;??}??? ? 程序运行结果如图：? ??2)概率法法计算定积分? ??设f:[a,b]→[c,d]连续函数(如图2 所示), 则由曲线y=f(x)以及x 轴和直