| 被称为利用投飞镖的方法求PI | |
|  | |
| #### 以下总结选自其他网友： | |
| 1. Figure2是Figure1的右上角的部分。 | |
| 2. 向Figure2中投掷飞镖若干次（一个很大的数目），并且每次都仍在不同的点上。 | |
| 3. 如果投掷的次数非常多，Figure2将被刺得“千疮百孔”。 | |
| 4. 这时，“投掷在圆里的次数”除以“总投掷次数”，再乘以4，就是PI的值！（具体的推导过程参见原文） | |
| 在这个算法中，很重要的一点是：如何做到“随机地向Figure2投掷”，就是说如何做到Figure2上的每个点被投中的概率相等。 | |
| 有人总结了一下，这个实际上叫做蒙特卡洛算法，我们取一个单位的正方形（1 x 1） 里面做一个内切圆（单位圆），则 单位正方形面积 ：内切单位圆面积 = 单位正方形内的飞镖数 : 内切单位圆内的飞镖数 ，通过计算飞镖个数就可以把单位圆面积算出来， 通过面积，在把圆周率计算出来。 注意 ，精度和你投掷的飞镖次数成正比。 | |
| #### 我的PHP源码实现： | |
| PHP自带的mt_rand随机函数偏差较大，换成Halton sequence的方法，测试结果见后面 | |
| ~~~.php | |
| <?php | |
| $count = 0; | |
| // 忍受不了运算时间，可以把$num 改小 | |
| // $num 越大，越接近真值 | |
| $num = 100000; | |
| for ($i = 0; $i < $num; $i++) { | |
| // list($x, $y) = array(mt_rand(0, 10000), mt_rand(0, 10000)); | |
| // $x /= 10000; $y /= 10000; | |
| $x = halton($i, 3); | |
| $y = halton($i, 7); | |
| if (($x*$x + $y*$y) < 1) { | |
| $count++; | |
| } | |
| } | |
| $pi = 4.0 * $count / $num; | |
| echo $pi."\n"; | |
| // 参考Halton sequence | |
| // https://en.wikipedia.org/wiki/Halton_sequence | |
| function halton($index, $base) { | |
| $result = 0; | |
| $f = 1; | |
| $i = $index; | |
| while ($i > 0) { | |
| $f /= $base; | |
| $result += $f * ($i % $base); | |
| $i = floor($i / $base); | |
| } | |
| return $result; | |
| } | |
| ~~~ | |
| 源码中halton传入参数是经过几次调整后的，更精确一些，测试PI = 3.14156 | |
| mt_rand误差较大，3次结果如下： | |
| mt_rand-1 => 3.142904 | |
| mt_rand-2 => 3.143196 | |
| mt_rand-3 => 3.139312 |
點擊查看更多內容
為 TA 點贊
評論
評論
共同學習，寫下你的評論
評論加載中...
作者其他優質文章
正在加載中
感謝您的支持，我會繼續努力的～
掃碼打賞，你說多少就多少
贊賞金額會直接到老師賬戶
支付方式
打開微信掃一掃，即可進行掃碼打賞哦