下面我们建立一个随机数类RadomNumber,该类包含一个由用户初始化的种子randSeed。给定种子之后,既可产生与之相应的随机数序列。randseed是一个无符号长整型数,既可由用户指定也可由系统时间自动产生。 const unsigned long maxshort=65536L;
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(void);
};
RandomNumber::RandomNumber(unsigned long s)
{
if(s==0)
randseed=time(0);
else
randseed=s;
}
unsigned short RandomNumber::Random(unsigned long n)
{
randseed=multiplier*randseed+adder;
return (unsigned short)((randseed>>16)%n);
}
Type Select(Type a[], int n, int k)
{
if(k<1||k>n)
throw OutOfBounds();
return select(a, 0, n-1, k);
}
平时我们一般开始考虑的是一个有着很好平均性能的选择算法,但在最坏情况下对某些实例算法效率较低。这时候我们用概率算法,将上述算法改造成一个舍伍德型算法,使得该算法对任何实例均有效。