随机化算法——随机数

　　概率算法的一个基本特征是对所求解问题的同一实例用同一概率算法求解两次可能得到完全不同的效果。这两次求解问题所需的时间甚至所得到的结果可能会有相当大的差别。一般情况下，可将概率算法大致分为四类:数值概率算法，蒙特卡罗(Monte Carlo)算法，拉斯维加斯(Las Vegas)算法和舍伍德(Sherwood)算法。

　　随机数在概率算法设计中扮演着十分重要的角色。在现实计算机上无法产生真正的随机数，因此在概率算法中使用的随机数都是一定程度上随机的，即伪随机数。

　　产生随机数最常用的方法是线性同余法。由线性同余法产生的随机序列a1,a2,…,an满足

　　1.a0=d

　　2.an=(b*an-1+c)mod m (n=1,2…….)

　　其中,b>0, c>=0, d>=m。d称为该随机序列的种子。

　　一般情况下，取gcd(m, b)=1，因此可取b为一素数。

　　这是一个随机数类：

　　代码

　　const unsigned long maxshort = 65535L;

　　const unsigned long multiplier = 1194211693L;

　　const unsigned long adder = 12345L;

　　class RandomNumber{

　　private:

　　// 当前种子

　　unsigned long randSeed;

　　public:

　　// 构造函数,默认值0表示由系统自动产生种子

　　RandomNumber(unsigned long s = 0);

　　// 产生0 ~ n-1之间的随机整数

　　unsigned short Random(unsigned long n);

　　// 产生[0, 1) 之间的随机实数

　　double fRandom();

　　};