0042算法筆記——【隨機化算法】計算π值和計算定積分

1、.1、計算值 問題描述 設(shè)有一半徑為r的圓及其外切四邊形。向該正方形隨機地投擲n個點。設(shè)落入圓內(nèi)的點數(shù)為k。由于所投入的點在正方形上均勻分布，因而所投入的點落入圓內(nèi)的概率為 。所以當(dāng)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,n

2、3=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+

3、)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. 程序運行結(jié)果如圖： 2、計算定積分 例：設(shè)f(x)=x2,求 解： 1)隨機投點法計算定積分 基本思想是在矩形區(qū)域上隨機均勻的投點實現(xiàn)。本算法的基本思想是在積分區(qū)間上隨機均勻的產(chǎn)生點, 即在a,b上隨機均勻的取點, 求出由這些點產(chǎn)生的函數(shù)值的算術(shù)平均值, 再乘以區(qū)間寬度, 即可解出定積分得近似解。 算法具體代碼如下：cppview plain

4、copy1. /隨機化算法用隨機投點法計算定積分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=n

5、2,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. *基本思想是在矩形區(qū)域內(nèi)隨機均勻投點，求出由這些點24. *產(chǎn)生的函數(shù)值的算術(shù)平均值，再乘以區(qū)間寬度，即可得25. *出定積分的近似解26. */27. doubleDarts(intn,doublea,doubleb)28. 29. staticRandomNumberdart;3

6、0. doublesum=0.0;31. for(inti=0;in;i+)32. 33. doublex=(b-a)*dart.fRandom()+a;/產(chǎn)生a,b)之間的隨機數(shù)34. sum=sum+f(x);35. 36. return(b-a)*sum/n;37. 38. 39. doublef(doublex)40. 41. returnx*x;42. 程序運行結(jié)果如圖： 2)概率法法計算定積分 設(shè)f:a,bc,d連續(xù)函數(shù)(如圖2 所示), 則由曲線y=f(x)以及x 軸和直線x=a,x=b 圍成的面積由定積分給出。根據(jù)幾何概型可知。假設(shè)向矩形區(qū)域隨機均勻的投鏢n 次, 落入陰影為K

7、次, 又設(shè)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=10

8、000,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為積分函數(shù),n為投鏢25. *總數(shù),a,b為積分區(qū)間,c,d為函26. *數(shù)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;/產(chǎn)生a,b)之間的隨機數(shù)35. doubley=