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

1、计算值 问题描述 设有一半径为r的圆及其外切四边形。向该正方形随机地投掷n个点。设落入圆内的点数为k。由于所投入的点在正方形上均匀分布，因而所投入的点落入圆内的概率为 。所以当n足够大时，k与n之比就逼近这一概率。从而。 程序具体代码如下：cppview plaincopy1. /随机化算法用随机投点法计算值2. #includestdafx.h3. #includeRandomNumber.h4. #include5. usingnamespacestd;6. 7. doubleDarts(intn);8. 9. intmain()10. 11. intn1=100,n2=1000,n3=1000,n4=10000,n5=10000000;12. coutn1=n1,1=Darts(n1)endl;13. coutn2=n2,2=Darts(n2)endl;14. coutn3=n3,3=Darts(n3)endl;15. coutn4=n4,4=Darts(n4)endl;16. coutn5=n5,5=Darts(n5)endl;17. return0;18. 19. 20. /用随机投点法计算值21. doubleDarts(intn)22. 23. staticRandomNumberdart;24. intk=0;25. 26. for(inti=1;i=n;i+)27. 28. doublex=dart.fRandom();29. doubley=dart.fRandom();30. if(x*x+y*y)=1)31. 32. k+;33. 34. 35. 36. return4*k/double(n);37. 程序运行结果如图： 2、计算定积分 例：设f(x)=x2,求 解： 1)随机投点法计算定积分 基本思想是在矩形区域上随机均匀的投点实现。本算法的基本思想是在积分区间上随机均匀的产生点, 即在a,b上随机均匀的取点, 求出由这些点产生的函数值的算术平均值, 再乘以区间宽度, 即可解出定积分得近似解。 算法具体代码如下：cppview plaincopy1. /随机化算法用随机投点法计算定积分2. #includestdafx.h3. #includeRandomNumber.h4. #include5. usingnamespacestd;6. 7. doubleDarts(intn,doublea,doubleb);8. doublef(doublex);9. 10. intmain()11. 12. intn1=100,n2=1000,n3=1000,n4=10000,n5=10000000;13. doublea=2.0,b=3.0;14. coutn1=n1,r1=Darts(n1,a,b)endl;15. coutn2=n2,r2=Darts(n2,a,b)endl;16. coutn3=n3,r3=Darts(n3,a,b)endl;17. coutn4=n4,r4=Darts(n4,a,b)endl;18. coutn5=n5,r5=Darts(n5,a,b)endl;19. return0;20. 21. 22. /*23. *基本思想是在矩形区域内随机均匀投点，求出由这些点24. *产生的函数值的算术平均值，再乘以区间宽度，即可得25. *出定积分的近似解26. */27. doubleDarts(intn,doublea,doubleb)28. 29. staticRandomNumberdart;30. doublesum=0.0;31. for(inti=0;in;i+)32. 33. doublex=(b-a)*dart.fRandom()+a;/产生a,b)之间的随机数34. sum=sum+f(x);35. 36. return(b-a)*sum/n;37. 38. 39. doublef(doublex)40. 41. returnx*x;42. 程序运行结果如图： 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. #includestdafx.h3. #includeRandomNumber.h4. #include5. usingnamespacestd;6. 7. doubleDarts(intn,doublea,doubleb,doubled);8. doublef(doublex);9. 10. intmain()11. 12. intn1=100,n2=1000,n3=1000,n4=10000,n5=10000000;13. doublea=2.0,b=3.0;14. doubled=f(b);15. coutn1=n1,r1=Darts(n1,a,b,d)endl;16. coutn2=n2,r2=Darts(n2,a,b,d)endl;17. coutn3=n3,r3=Darts(n3,a,b,d)endl;18. coutn4=n4,r4=Darts(n4,a,b,d)endl;19. coutn5=n5,r5=Darts(n5,a,b,d)endl;20. return0;21. 22. 23. /*24. *f为积分函数,n为投镖25. *总数,a,b为积分区间,c,d为函26. *数f的值域的端点值27. */28. doubleDarts(intn,doublea,doubleb,doubled)29. 30. staticRandomNumberdart;31. intk=0;32. for(inti=0;in;i+)33. 34. doublex=(b-a)*dart.fRandom()+a;/产生a,b)之间的随机数35. double