随机算法 之随机数的产生

随机算法 之随机数的产生

编写随机算法程序的基础就是编写一个随机数产生器，实践过程中发现很多同学在使用c++的随机数产生函数
的时候都犯一个相同的错误——srand多次使用，我想那是因为对随机数产生过程不够了解造成的
产生随机数常用的有两种方法：
线性同余：
 x(0) = d
 x(n) = (b*x(n-1)+c)mod m
 这里有一个经验公式：x(n) = (314159269x(n-1)[phone])mod 2^31
斐波那契发生器：
 x(n+1) = (x(n)+x(n-1))mod m （参考自张德福老师的《算法设计与分析-高级教程》）
所谓的srand播撒随机种子，其实就是产生一个初始的x(0)，所以如果每一次使用rand的时候都用一次srand
那么必然会产生的结果就是如果两次srand过程是相继发生的，那么很有可能rand出来的结果都一样，这样当然
不会有好的随机数序列发生了。
下面是我用的一个随机数发生类，可以产生，任意【a b】区间的随机整数、浮点数。还可以通过构造函数提高
浮点数发声精度。（本类仅供参考）

#include<iostream>
#include<ctime>

using namespace std;

class Random {
 
 public:
  
  Random(int a,int b);
  
  Random();
  
  int random();
  
  int random(int a,int b);
  
  double randomf(int a,int b);
  
 private:
  
  double random1();
  int low;
  int high;
};

Random::Random()
{
 low = 0;
 high = 1000;
 srand((unsigned)clock());
}

Random::Random(int a,int b)
{
 low = min(a,b);
 high = max(a,b);
 srand((unsigned)clock());
}
 
int Random::random(int a,int b)
{ 
 int t = rand();
 
 return a+t%(b-a)+1;
} 

int Random::random()
{
 return random(low,high);
}

double Random::random1() //0-1的随机数
{
 double m = (double)random();
 double n = (double)random();
 
 if(m==0&&n==0)return 0;
 else return (m<n)?(m/n):(n/m);
}  

double Random::randomf(int a,int b)
{
 return a+(b-a)*random1();
}