算法笔记随机化算法计算值和计算定积分.docx

《算法笔记随机化算法计算值和计算定积分.docx》由会员分享，可在线阅读，更多相关《算法笔记随机化算法计算值和计算定积分.docx（4页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1、计算值 问题描述 设有一半径为r的圆及其外切四边形。向该正方形随机地投掷n个点。设落入圆内的点数为k。由于所投入的点在正方形上均匀分布，因而所投入的点落入圆内的概率为 。所以当n足够大时，k及n之比就逼近这一概率。从而。 程序具体代码如下：cppview plaincopy1. /随机化算法用随机投点法计算值2. #includestdafx.h3. #includeRandomNumber.h4. #include5. usingnamespacestd;6. doubleDarts(intn);7. intmain()8. intn1=100,n2=1000,n3=1000,n4=10

2、000,n5=10000000;9. coutn1=n1,1=Darts(n1)endl;10. coutn2=n2,2=Darts(n2)endl;11. coutn3=n3,3=Darts(n3)endl;12. coutn4=n4,4=Darts(n4)endl;13. coutn5=n5,5=Darts(n5)endl;14. return0;15. /用随机投点法计算值16. doubleDarts(intn)17. staticRandomNumberdart;18. intk=0;19. for(inti=1;i=n;i+)20. doublex=dart.fRandom();2

3、1. doubley=dart.fRandom();22. if(x*x+y*y)=1)23. k+;24. return4*k/double(n); 程序运行结果如图： 2、计算定积分 例：设f(x)=x2,求 解： 1)随机投点法计算定积分 根本思想是在矩形区域上随机均匀的投点实现。本算法的根本思想是在积分区间上随机均匀的产生点, 即在a,b上随机均匀的取点, 求出由这些点产生的函数值的算术平均值, 再乘以区间宽度, 即可解出定积分得近似解。 算法具体代码如下：cppview plaincopy1. /随机化算法用随机投点法计算定积分2. #includestdafx.h3. #inclu

4、deRandomNumber.h4. #include5. usingnamespacestd;6. doubleDarts(intn,doublea,doubleb);7. doublef(doublex);8. intmain()9. intn1=100,n2=1000,n3=1000,n4=10000,n5=10000000;10. doublea=2.0,b=3.0;11. coutn1=n1,r1=Darts(n1,a,b)endl;12. coutn2=n2,r2=Darts(n2,a,b)endl;13. coutn3=n3,r3=Darts(n3,a,b)endl;14. co

5、utn4=n4,r4=Darts(n4,a,b)endl;15. coutn5=n5,r5=Darts(n5,a,b)endl;16. return0;17. *根本思想是在矩形区域内随机均匀投点，求出由这些点18. *产生的函数值的算术平均值，再乘以区间宽度，即可得19. *出定积分的近似解20. doubleDarts(intn,doublea,doubleb)21. staticRandomNumberdart;22. doublesum=0.0;23. for(inti=0;in;i+)24. doublex=(b-a)*dart.fRandom()+a;/产生a,b)之间的随机数25

6、. sum=sum+f(x);26. return(b-a)*sum/n;27. doublef(doublex)28. returnx*x; 程序运行结果如图： 2)概率法法计算定积分 设f:a,bc,d连续函数(如图2 所示), 那么由曲线y=f(x)以及x 轴和直线x=a,x=b 围成的面积由定积分给出。根据几何概型可知。假设向矩形区域随机均匀的投镖n 次, 落入阴影为K次, 又设M为x=a、x=b、y=c、y=d 所围成的矩形面积, s 为定积分面积,那么, 所以s= k/nM。 算法具体代码 如下：cppview plaincopy1. /随机化算法用概率法计算定积分2. #incl

7、udestdafx.h3. #includeRandomNumber.h4. #include5. usingnamespacestd;6. doubleDarts(intn,doublea,doubleb,doubled);7. doublef(doublex);8. intmain()9. intn1=100,n2=1000,n3=1000,n4=10000,n5=10000000;10. doublea=2.0,b=3.0;11. doubled=f(b);12. coutn1=n1,r1=Darts(n1,a,b,d)endl;13. coutn2=n2,r2=Darts(n2,a,b

8、,d)endl;14. coutn3=n3,r3=Darts(n3,a,b,d)endl;15. coutn4=n4,r4=Darts(n4,a,b,d)endl;16. coutn5=n5,r5=Darts(n5,a,b,d)endl;17. return0;18. *f为积分函数,n为投镖19. *总数,a,b为积分区间,c,d为函20. *数f的值域的端点值21. doubleDarts(intn,doublea,doubleb,doubled)22. staticRandomNumberdart;23. intk=0;24. for(inti=0;in;i+)25. doublex=(b-a)*dart.fRandom()+a;/产生a,b)之间的随机数26. doubley=d*dart.fRandom();27. if(y=f(x)28. k+;29. returnd*(b-a)*k/n;30. doublef(doublex)31. returnx*x; 程序运行结果如图：第 4 页