算法之4 | 随机数生成算法

欢迎大家来到IT世界,在知识的湖畔探索吧!

一般的算法结果都是确定的，即对于相同的输入总对应着相同的输出。但实际应用中经常用到不确定的算法，比如随机数生成算法，算法的结果是不确定的。

计算机中的随机数都是伪随机数，通过线性同余法得到。

在计算物理学中，随机数被准确地分成了三类：真随机数、准随机数、伪随机数。那么这三种的区别是什么呢？拷贝一段书上的定义：

　　1）真随机数：产生的数不可预计，也不可能重复产生两个相同的真随机数序列。真随机数只能通过某些随机的物理过程来产生，如放射性衰变、电子设备的热噪声等。

　　2）准随机数：其随机数序列不具备随机性质，仅仅是用它来处理问题能够得到正确的结果。

　　3）伪随机数：通过某种数学公式或者算法产生的数值序列。虽然在数学意义上伪随机数是不随机的，但是如果能够通过统计检验，可以当成真随机数使用。

例如，产生伪随机数序列a1, a2, …, an：

欢迎大家来到IT世界,在知识的湖畔探索吧!

其中，b>0, c>=0, d>=m。d为种子；m取值越大越好；m，b互质，常取b为质数；

实际应用中，一般使用当前时间作为随机种子。

代码如下：

public class MonteCarlo {

private static final int MAXN = 1 << 20;

private int[] x;

public MonteCarlo() {

x = new int[MAXN];

}

public void rand() {

x[0] = (int)(Math.random()*100 + 1); // 随机种子(可以用日期产生)

/* 保证m与a互质 */

int m = MAXN;

int a = 9; // a = 4p + 1

int b = 7; // b = 2q + 1

System.out.println(x[0]);

/* 取前1w个数*/

for(int i = 1; i < 10000; ++i) {

x[i] = ( a * x[i-1] + b ) % m;

System.out.println(x[i]);

}

}

public static void main(String[] args) {

MonteCarlo mc = new MonteCarlo();

mc.rand();

}

}

注：凡属于本公众号内容，未经允许不得私自转载，否则将依法追究侵权责任。