小话随机数

标准函数库中函数rand()可以生成0~RAND_MAX之间的一个随机数,其中RAND_MAX 是stdlib.h中定义的一个整数,它与系统有关。 例如在我的机器上,RAND_MAX=32767。可以使用 printf("%ld",RAND_MAX);查看。

调用rand()可以生成一个随机数,但我们往往需要的是一个有上下界的随机数。

例如 要产生一个[a,b]之间的随机整数x

x = rand()%(b-a+1)+a

产生区间[a,b]上的随机实数

z = ((double)rand()/RAND_MAX)*(b-a) + a

众所周知,计算机产的随机序列实际上是一个有很长周期的序列(通过线性同余算法),这就是伪随机数。随机数产生时需要一个seed(种子),才能产生随机数。

在Pascal 和 Basic 中,都可以使用 randomize;来初始化种子。而在C中,需要用srand(unsigned int)函数给予一个种子。 例如srand(time(NULL));

一般来说在OI中,依靠随机数的算法较为稳定,它不受随机序列的影响(难道有人看过默认的随机序列,专门设计出一组卡随机的测试数据????)。所以srand调用与否没有太大关系。况且time()函数定义在 time.h 中,某些评测系统禁止使用time.h。我一般都是srand(rand());。

线性同余方法(LCG)是个产生伪随机数的方法。
它是根据递归公式:
其中A,B,M是产生器设定的常数。
LCG的周期最大为M,但大部分情况都会少于M。要令LCG达到最大周期,应符合以下条件:
   1. B,M互质;
   2. M的所有质因子的积能整除A − 1;
   3. 若M是4的倍数,A − 1也是;
   4. A,B,N0都比M小;
   5. A,B是正整数。

使用线性同余算法产生伪随机数 转自http://www.blog.edu.cn/user1/20989/archives/2005/989163.html C语言中有个random(n)函数,可以产生0——n-1之间的伪随机数,rand()函数可以产生0——32767之间的伪随机数,一般需要配合使用srand(long)给出随机种子,或者使用randomize()函数来根据系统时间指定随机种子。

     常用的产生伪随机数的算法是线性同余法,下面是我写的代码,相信通过代码,大家可以很容易地明白伪随机数原理:

     算法:an+1=b*an+c mod m;a0=d。d为种子。
int d;/*种子*/
long My_Rand(long b,long c,long m)
{
   return  d=(b*d+c)%m;/*产生随机数,并记录,用来产生下一个伪随机数*/
}

long gcd1(long m,long n)
{/*求最大公约数,算法中的b和m一般取互素*/
   long r;
   while((r=m%n)!=0)
   {
     m=n;
     n=r;
   }
   return n;
}

long gcd(long m)
{/*计算与m互素的b*/
   long i=2;
   while(gcd1(i,m)!=1)
      i++;
   return i;
}

void main()
{
   long b,c,m;
   int count;
   int i;
   m=32767;
   b=gcd(m);
   c=5001;
   d=3;
   count=800;
   for(i=0;i<count;i++)/*产生800个伪随机数*/
   {
      if(i%10==0)
           printf("\n");
      printf("%8ld",My_Rand(b,c,m));
   }
}
当种子d为131时运行结果如下:


    5293   15617    3498   12027   29085   30434     365    5761   16553    5370
   15771    3806   12643   30317     131    5293   15617    3498   12027   29085
   30434     365    5761   16553    5370   15771    3806   12643   30317     131
    5293   15617    3498   12027   29085   30434     365    5761   16553    5370
   15771    3806   12643   30317     131    5293   15617    3498   12027   29085
   30434     365    5761   16553    5370   15771    3806   12643   30317     131
    5293   15617    3498   12027   29085   30434     365    5761   16553    5370
   15771    3806   12643   30317     131    5293   15617    3498   12027   29085
   30434     365    5761   16553    5370   15771    3806   12643   30317     131
    5293   15617    3498   12027   29085   30434     365    5761   16553    5370
   15771    3806   12643   30317     131    5293   15617    3498   12027   29085
   30434     365    5761   16553    5370   15771    3806   12643   30317     131
    5293   15617    3498   12027   29085   30434     365    5761   16553    5370
   15771    3806   12643   30317     131    5293   15617    3498   12027   29085
   30434     365    5761   16553    5370   15771    3806   12643   30317     131
    5293   15617    3498   12027   29085   30434     365    5761   16553    5370
   15771    3806   12643   30317     131    5293   15617    3498   12027   29085
   30434     365    5761   16553    5370   15771    3806   12643   30317     131
    5293   15617    3498   12027   29085   30434     365    5761   16553    5370
   15771    3806   12643   30317     131    5293   15617    3498   12027   29085
   30434     365    5761   16553    5370   15771    3806   12643   30317     131
    5293   15617    3498   12027   29085   30434     365    5761   16553    5370
   15771    3806   12643   30317     131    5293   15617    3498   12027   29085
   30434     365    5761   16553    5370   15771    3806   12643   30317     131
    5293   15617    3498   12027   29085   30434     365    5761   16553    5370
   15771    3806   12643   30317     131    5293   15617    3498   12027   29085
   30434     365    5761   16553    5370   15771    3806   12643   30317     131
    5293   15617    3498   12027   29085   30434     365    5761   16553    5370
   15771    3806   12643   30317     131    5293   15617    3498   12027   29085
   30434     365    5761   16553    5370   15771    3806   12643   30317     131
    5293   15617    3498   12027   29085   30434     365    5761   16553    5370
   15771    3806   12643   30317     131    5293   15617    3498   12027   29085
   30434     365    5761   16553    5370   15771    3806   12643   30317     131
    5293   15617    3498   12027   29085   30434     365    5761   16553    5370
   15771    3806   12643   30317     131    5293   15617    3498   12027   29085
   30434     365    5761   16553    5370   15771    3806   12643   30317     131
    5293   15617    3498   12027   29085   30434     365    5761   16553    5370
   15771    3806   12643   30317     131    5293   15617    3498   12027   29085
   30434     365    5761   16553    5370   15771    3806   12643   30317     131
    5293   15617    3498   12027   29085   30434     365    5761   16553    5370
   15771    3806   12643   30317     131    5293   15617    3498   12027   29085
   30434     365    5761   16553    5370   15771    3806   12643   30317     131
    5293   15617    3498   12027   29085   30434     365    5761   16553    5370
   15771    3806   12643   30317     131    5293   15617    3498   12027   29085
   30434     365    5761   16553    5370   15771    3806   12643   30317     131
    5293   15617    3498   12027   29085   30434     365    5761   16553    5370
   15771    3806   12643   30317     131    5293   15617    3498   12027   29085
   30434     365    5761   16553    5370   15771    3806   12643   30317     131
    5293   15617    3498   12027   29085   30434     365    5761   16553    5370
   15771    3806   12643   30317     131    5293   15617    3498   12027   29085
   30434     365    5761   16553    5370   15771    3806   12643   30317     131
    5293   15617    3498   12027   29085   30434     365    5761   16553    5370
   15771    3806   12643   30317     131    5293   15617    3498   12027   29085
   30434     365    5761   16553    5370   15771    3806   12643   30317     131
    5293   15617    3498   12027   29085   30434     365    5761   16553    5370
   15771    3806   12643   30317     131    5293   15617    3498   12027   29085
   30434     365    5761   16553    5370   15771    3806   12643   30317     131
    5293   15617    3498   12027   29085   30434     365    5761   16553    5370
   15771    3806   12643   30317     131    5293   15617    3498   12027   29085
   30434     365    5761   16553    5370   15771    3806   12643   30317     131
    5293   15617    3498   12027   29085   30434     365    5761   16553    5370
   15771    3806   12643   30317     131    5293   15617    3498   12027   29085
   30434     365    5761   16553    5370   15771    3806   12643   30317     131
    5293   15617    3498   12027   29085   30434     365    5761   16553    5370
   15771    3806   12643   30317     131    5293   15617    3498   12027   29085
   30434     365    5761   16553    5370   15771    3806   12643   30317     131
    5293   15617    3498   12027   29085   30434     365    5761   16553    5370
   15771    3806   12643   30317     131    5293   15617    3498   12027   29085
   30434     365    5761   16553    5370   15771    3806   12643   30317     131
    5293   15617    3498   12027   29085   30434     365    5761   16553    5370
   15771    3806   12643   30317     131    5293   15617    3498   12027   29085
   30434     365    5761   16553    5370   15771    3806   12643   30317     131
    5293   15617    3498   12027   29085   30434     365    5761   16553    5370
   15771    3806   12643   30317     131    5293   15617    3498   12027   29085
   30434     365    5761   16553    5370   15771    3806   12643   30317     131
    5293   15617    3498   12027   29085   30434     365    5761   16553    5370
   15771    3806   12643   30317     131    5293   15617    3498   12027   29085
   30434     365    5761   16553    5370   15771    3806   12643   30317     131
    5293   15617    3498   12027   29085   30434     365    5761   16553    5370
   15771    3806   12643   30317     131    5293   15617    3498   12027   29085

当种子数为151时,运行结果如下:


    5333   15697    3658   12347   29725   31714    2925   10881   26793   25850
   23964   20192   12648   30327     151    5333   15697    3658   12347   29725
   31714    2925   10881   26793   25850   23964   20192   12648   30327     151
    5333   15697    3658   12347   29725   31714    2925   10881   26793   25850
   23964   20192   12648   30327     151    5333   15697    3658   12347   29725
   31714    2925   10881   26793   25850   23964   20192   12648   30327     151
    5333   15697    3658   12347   29725   31714    2925   10881   26793   25850
   23964   20192   12648   30327     151    5333   15697    3658   12347   29725
   31714    2925   10881   26793   25850   23964   20192   12648   30327     151
    5333   15697    3658   12347   29725   31714    2925   10881   26793   25850
   23964   20192   12648   30327     151    5333   15697    3658   12347   29725
   31714    2925   10881   26793   25850   23964   20192   12648   30327     151
    5333   15697    3658   12347   29725   31714    2925   10881   26793   25850
   23964   20192   12648   30327     151    5333   15697    3658   12347   29725
   31714    2925   10881   26793   25850   23964   20192   12648   30327     151
    5333   15697    3658   12347   29725   31714    2925   10881   26793   25850
   23964   20192   12648   30327     151    5333   15697    3658   12347   29725
   31714    2925   10881   26793   25850   23964   20192   12648   30327     151
    5333   15697    3658   12347   29725   31714    2925   10881   26793   25850
   23964   20192   12648   30327     151    5333   15697    3658   12347   29725
   31714    2925   10881   26793   25850   23964   20192   12648   30327     151
    5333   15697    3658   12347   29725   31714    2925   10881   26793   25850
   23964   20192   12648   30327     151    5333   15697    3658   12347   29725
   31714    2925   10881   26793   25850   23964   20192   12648   30327     151
    5333   15697    3658   12347   29725   31714    2925   10881   26793   25850
   23964   20192   12648   30327     151    5333   15697    3658   12347   29725
   31714    2925   10881   26793   25850   23964   20192   12648   30327     151
    5333   15697    3658   12347   29725   31714    2925   10881   26793   25850
   23964   20192   12648   30327     151    5333   15697    3658   12347   29725
   31714    2925   10881   26793   25850   23964   20192   12648   30327     151
    5333   15697    3658   12347   29725   31714    2925   10881   26793   25850
   23964   20192   12648   30327     151    5333   15697    3658   12347   29725
   31714    2925   10881   26793   25850   23964   20192   12648   30327     151
    5333   15697    3658   12347   29725   31714    2925   10881   26793   25850
   23964   20192   12648   30327     151    5333   15697    3658   12347   29725
   31714    2925   10881   26793   25850   23964   20192   12648   30327     151
    5333   15697    3658   12347   29725   31714    2925   10881   26793   25850
   23964   20192   12648   30327     151    5333   15697    3658   12347   29725
   31714    2925   10881   26793   25850   23964   20192   12648   30327     151
    5333   15697    3658   12347   29725   31714    2925   10881   26793   25850
   23964   20192   12648   30327     151    5333   15697    3658   12347   29725
   31714    2925   10881   26793   25850   23964   20192   12648   30327     151
    5333   15697    3658   12347   29725   31714    2925   10881   26793   25850
   23964   20192   12648   30327     151    5333   15697    3658   12347   29725
   31714    2925   10881   26793   25850   23964   20192   12648   30327     151
    5333   15697    3658   12347   29725   31714    2925   10881   26793   25850
   23964   20192   12648   30327     151    5333   15697    3658   12347   29725
   31714    2925   10881   26793   25850   23964   20192   12648   30327     151
    5333   15697    3658   12347   29725   31714    2925   10881   26793   25850
   23964   20192   12648   30327     151    5333   15697    3658   12347   29725
   31714    2925   10881   26793   25850   23964   20192   12648   30327     151
    5333   15697    3658   12347   29725   31714    2925   10881   26793   25850
   23964   20192   12648   30327     151    5333   15697    3658   12347   29725
   31714    2925   10881   26793   25850   23964   20192   12648   30327     151
    5333   15697    3658   12347   29725   31714    2925   10881   26793   25850
   23964   20192   12648   30327     151    5333   15697    3658   12347   29725
   31714    2925   10881   26793   25850   23964   20192   12648   30327     151
    5333   15697    3658   12347   29725   31714    2925   10881   26793   25850
   23964   20192   12648   30327     151    5333   15697    3658   12347   29725
   31714    2925   10881   26793   25850   23964   20192   12648   30327     151
    5333   15697    3658   12347   29725   31714    2925   10881   26793   25850
   23964   20192   12648   30327     151    5333   15697    3658   12347   29725
   31714    2925   10881   26793   25850   23964   20192   12648   30327     151
    5333   15697    3658   12347   29725   31714    2925   10881   26793   25850
   23964   20192   12648   30327     151    5333   15697    3658   12347   29725
   31714    2925   10881   26793   25850   23964   20192   12648   30327     151
    5333   15697    3658   12347   29725   31714    2925   10881   26793   25850
   23964   20192   12648   30327     151    5333   15697    3658   12347   29725
   31714    2925   10881   26793   25850   23964   20192   12648   30327     151
    5333   15697    3658   12347   29725   31714    2925   10881   26793   25850
   23964   20192   12648   30327     151    5333   15697    3658   12347   29725
   31714    2925   10881   26793   25850   23964   20192   12648   30327     151
    5333   15697    3658   12347   29725   31714    2925   10881   26793   25850
   23964   20192   12648   30327     151    5333   15697    3658   12347   29725
   31714    2925   10881   26793   25850   23964   20192   12648   30327     151
    5333   15697    3658   12347   29725   31714    2925   10881   26793   25850
   23964   20192   12648   30327     151    5333   15697    3658   12347   29725
   31714    2925   10881   26793   25850   23964   20192   12648   30327     151
    5333   15697    3658   12347   29725   31714    2925   10881   26793   25850
   23964   20192   12648   30327     151    5333   15697    3658   12347   29725

相关日志