一.线性同余法
随机数在计算机中扮演重要角色,不过现实中往往难以产生真正的随机数,很多教材上都采用了线性同余法,产生的随机数也只是在一定范围内,该范围的一定要比研究所使用的范围大,不能没有完全验证就又循环。
好事者称上面的性质为随机数要具有周期性,又要不具有周期性(晕),所谓周期性指的是到达一个足够大的数后又要重新开始,非周期性实际就是指范围要足够大,就像C/C++中要求RAND_MAX至少要是32767。
其中b >= 0,c >= 0,d <= m。d称为该随机序列的种子。如何选取该方法中的常数b、c和m直接关系到所产生的随机序列的随机性能,不过这是随机性理论研究的内容,不在本文讨论的范围。从直观上看,m应取得充分大,因此可取m为机器大数,另外应取gcd(m, b) = 1,因此可取b为一素数。
具体原理请读者参考《抽象代数》。
二.随机投点法计算PI值
其实我最先想到是蒲丰投针实验……请各位读者尽情发挥想象。
随手谷歌之,发现只要是介绍随机算法的都有这个例子,不过几乎都是C++版本,下面笔者就用Java实现以慰劳广大Java爱好者。
实验设计如下:
设有一半径为r的圆及其外切四边形,向该正方形随机地投掷n个点,设落入圆内的点数为m。由于所投入的点在正方形上均匀分布,因而所投入的点落入圆内的概率为圆面积/正方型面积= PI / 4 (与r无关),所以当n足够大时,k与n之比就逼近这一概率,从而,PI 约等于 (4*m)/n。
Java实现:
/* * 遇到了很奇怪的问题,名字叫CalPI就一直找不到主类 * bin目录下确实没有class文件 * 咋回事 */ public class MyPI { public static void main(String[] args) { int n = 20000000;//进行200w次实验 int count = calCounts(n); double ans = 4.0*count/n; System.out.println(ans); } private static int calCounts(int n) { /* * java中没有类似C/C++中的fabs,不过abs重载了 * 如何让Math.random()生成的随机数包括1? */ int count = 0; for(int i=0; i<n; i++) { double x = Math.random(); double y = Math.random(); //实际有些问题,因为无法生成1.0,目前我也不知道咋办 if((x*x + y*y)<=1.0) { count++; } } return count; } }结果如下:
200 3.1418832
2000 3.088
20000 3.1512
200000 3.14414
2000000 3.140148
20000000 3.1415662观察结果可得并不是试验次数越多结果越精确,而且相同的次数结果也会不同。
三.简单定积分计算
采用概率方法,不以积分公式。
假定f(x)为[0,1]上的连续可积函数(其实什么叫可积我也忘了),现需要计算,实际就等于G。
分析如下:在图所示单位正方形内均匀地作投点试验n次,则随机点落在曲线下面的概率为,如果有m个点落在G内,则概率P=m/n,由古典概型可知I=P。
如果f(x) = ex(x用上标,后面的也在上标里,选中后面的再次单击上标按钮,或者直接在源代码里改<sup>的范围),则只需要把上面的calCounts里的if改成y<x^3并且输出不乘以4就好了。
四. 舍伍德(Sherwood)算法
五.拉斯维加斯(Las Vegas)算法
六.蒙特卡罗(Monte Carlo)算法
注意:上面的属于数值概率算法,四五六准备出独立文章,敬请期待。