產(chǎn)生隨機(jī)數(shù)的基本方法

本文中，筆者將介紹c語(yǔ)言所提供的隨機(jī)數(shù)發(fā)生器的用法。現(xiàn)在的c編譯程序都提供了一個(gè)基于一種ANSI標(biāo)準(zhǔn)的偽隨機(jī)數(shù)發(fā)生器函數(shù)，用來(lái)生成隨機(jī)數(shù)。Microsoft和Borland都是通過(guò)rand()和srand()函數(shù)來(lái)支持這種標(biāo)準(zhǔn)的，它們的工作過(guò)程如下：
首先，給srand()提供一個(gè)“種子”，它是一個(gè)unsignde int類型，其取值范圍是從0到65,535 ;
然后，調(diào)用rand()，它會(huì)根據(jù)提供給srand()的“種子”值返回一個(gè)隨機(jī)數(shù)(在0到32，767之間)；
根據(jù)需要多次調(diào)用rand()，從而不斷地得到新的隨機(jī)數(shù)；
無(wú)論什么時(shí)候，你都可以給srand()提供一個(gè)新的“種子”，從而進(jìn)一步“隨機(jī)化"rand()的輸出結(jié)果。

這個(gè)過(guò)程看起來(lái)很簡(jiǎn)單，問(wèn)題是如果你每次調(diào)用srand()時(shí)都提供相同的“種子”值，那么你將會(huì)得到相同的“隨機(jī)”數(shù)序列。例如，在以17為“種子”值調(diào)用srand()之后，在你首次調(diào)用rand()時(shí)，你將得到隨機(jī)數(shù)94；在你第二次和第三次調(diào)用rand()時(shí)，你將分別得到26，602和30，017。這些數(shù)看上去是相當(dāng)隨機(jī)的(盡管這只是一個(gè)很小的數(shù)據(jù)點(diǎn)集合)，但是，在你再次以17為“種子”值調(diào)用srand()之后，在對(duì)rand()的前三次調(diào)用中，所得到的返回值仍然是94、26，602和30，017，并且此后得到的返回值仍然是在對(duì)rand()的第一批調(diào)用中所得到的其余的返回值。因此，只有再次給srand()提供一個(gè)隨機(jī)的“種子”值，才能再次得到一個(gè)隨機(jī)數(shù)。

下面的例子用一種簡(jiǎn)單而有效的辦法來(lái)產(chǎn)生一個(gè)相當(dāng)隨機(jī)的“種子”值——當(dāng)天的時(shí)間值。

# include <stdlib. h>
# include <stdio. h>
# include <sys/types. h>
# include <sys/timeb. h>
void main (void){
  int i ;
  unsigned int seedVal;
  struct_timeb timeBuf ;
  _ftime (&timeBuf) ;
  seedVal = ( ( ( ( (unsigned int)timeBuf, time & 0xFFFF) +
          (unsigned int)timeBuf, millitm) ^
          (unsigned int)timeBuf, millitm) ;
  srand ((unsigned int)seedVal) ;
  for(i=O;i<lO;++i)
    printf (" %6d\n" ,rand ( ) ) ;
}

上例先是調(diào)用_ftime()來(lái)檢索當(dāng)前時(shí)間，并把它的值存入結(jié)構(gòu)成員timeBuf.time中，當(dāng)前時(shí)間的值從1970年1月1日開(kāi)始以秒計(jì)算。在調(diào)用了_ftime()之后，在結(jié)構(gòu)timeBuf的成員millitm中還存入了在當(dāng)前那一秒已經(jīng)度過(guò)的毫秒數(shù)，但在DOS中這個(gè)數(shù)字實(shí)際上是以百分之一秒來(lái)計(jì)算的。然后，把毫秒數(shù)和秒數(shù)相加，再和毫秒數(shù)進(jìn)行一次異或運(yùn)算。你可以對(duì)這兩個(gè)結(jié)構(gòu)成員施加更多的邏輯運(yùn)算，以控制seedVal的取值范圍，并進(jìn)一步加強(qiáng)它的隨機(jī)性，但上例所用的邏輯運(yùn)算已經(jīng)足夠了。

注意，在前面的例子中，rand()的輸出并沒(méi)有被限制在一個(gè)指定的范圍內(nèi)，假設(shè)你想建立一個(gè)彩票選號(hào)器，其取值范圍是從1到44。你可以簡(jiǎn)單地忽略掉rand()所輸出的在該范圍之外的值，但這將花費(fèi)許多時(shí)間去得到所需的全部(例如6個(gè))彩票號(hào)碼。假設(shè)你已經(jīng)建立了一個(gè)令你滿意的隨機(jī)數(shù)發(fā)生器，它所產(chǎn)生的隨機(jī)數(shù)據(jù)范圍是從0到32，767(就象前文中提到過(guò)的那樣)，而你想把輸出限制在1到44之間，下面的例子就說(shuō)明了如何來(lái)完成這項(xiàng)工作：

int i ,k ,range ;
int rain, max ;
double j ;
min=1;  /* 1 is the minimum number allowed */
max=44;  /* 44 is the maximum number allowed */
range=max-min;  /* r is the range allowed; 1 to 44 */
i=rand();  /* use the above example in this slot */
/* Normalize the rand() output (scale to 0 to 1) */
/* RAND_MAX is defined in stdlib, h */
j= ((double)i/(double)RAND_MAX) ;
/* Scale the output to 1 to 44 */
i= (int)(j * (double)range) ;
i+ =min;

上例把輸出的隨機(jī)數(shù)限制在1到44之間，其工作原理如下：
得到一個(gè)在O到RAND_MAX(32，767)之間的隨機(jī)數(shù)，把它除以RAND_MAX，從而產(chǎn)生一個(gè)在0到1之間的校正值；
把校正值乘以所需要的范圍值(在本例中為43，即44減去1)，從而產(chǎn)生一個(gè)在O到43之間的值；
把該值和所要求的最小值相加，從而使該值最終落在正確的取值范圍——1到44之內(nèi)。

你可以用不同的min和max值來(lái)驗(yàn)證這個(gè)例子，你會(huì)發(fā)現(xiàn)它總是會(huì)正確地產(chǎn)生在新的rain和max值之間的隨機(jī)數(shù)。

下面來(lái)看一下隨機(jī)數(shù)的相關(guān)練習(xí)題目

題目
給定了rand7,如何生成rand3？

思路
一個(gè)非常直觀的思路，就是不斷的調(diào)用rand7,直到它產(chǎn)生1-3之間的數(shù)，然后返回。代碼如下：（如果有同學(xué)說(shuō)這里沒(méi)有3,但是不代表我不能判斷和3的大小比較吧）

  #include <stdio.h> 
   
  int rand_3() 
  { 
    int x; 
   
    while (x = rand_7()) { 
      if (x <= 3) { 
        return x; 
      } 
    } 
  } 

接下來(lái)，就是判斷rand_3是否能等概率的產(chǎn)生1,2,3.也就是我們需要計(jì)算產(chǎn)生1,2,3的概率是否都是1/3.

首先，rand_7可以等概率的產(chǎn)生1-7,我們以rand_3生成1為例，假設(shè)：

•     第一次生成1的概率是1/7
•     第二次生存1的概率是4/7 * 1/7，因此第一次肯定是生成了大于3的數(shù)例如4,5,6,7,概率是4/7
•     同理，第三次生成1的概率是(4/7)^2 * 1/7

因此，rand_3生成1的概率是P(x=1)= 1/7 +  (4/7) * 1/7 + (4/7)^2 * 1/7 + ... + (4/7)^n-1 * 1/7 //等比數(shù)列
                                                  =  1/7 * ((1 - (4/7)^n) / 1 - 4/7) = 1/7 * 7/3 = 1/3

同理，可驗(yàn)證生成2,3的概率均為1/3

結(jié)論
上述證明說(shuō)明rand3可以等概率的產(chǎn)生1,2,3.從上面的分析，我們可以得出一個(gè)更一般的結(jié)論：

如果a>b,我們一定可以用rand_a去實(shí)現(xiàn)rand_b.其中，rand_a是等可能的生成1-a,rand_b是等可能的生成1-b

擴(kuò)展

現(xiàn)在給定兩個(gè)生成隨機(jī)數(shù)的函數(shù)rand_a和rand_b，rand_a和rand_b分別產(chǎn)生1-a和1-b的隨機(jī)數(shù)，a和b不相等，現(xiàn)在讓你用rand_a實(shí)現(xiàn)rand_b，方法如下：

•     如果a>b，則可以直接采用上述方法
•     如果a<b, 則構(gòu)造rand_a^2=a * (rand_a - 1) + rand_a，表示生成1-a^2的隨機(jī)數(shù)，如果a^2還小于b，那么繼續(xù)構(gòu)造rand_a^3=a * (rand_a^2 - 1) + rand_a

舉例說(shuō)明
阿里2014年筆試題目，是給定生成1-7的隨即函數(shù)rand_7，看是否能生成其它隨機(jī)數(shù)？

我們先看一下是否能等概率生成1-49,構(gòu)造rand_49 = 7 * (rand_7 - 1) + rand_7 （ps：別問(wèn)我7從哪里來(lái)的，rand_7既然能隨即生成1-7,我當(dāng)然可以獲得到7了）

rand_7 - 1能等概率的生成0, 1, 2, 3, 4, 5, 6，每個(gè)數(shù)的生成概率都是1/7,所以*7之后，可以等概率的生成0,7,14,21,28,35,42,每個(gè)數(shù)的概率都是1/7

既然0,7,14,21,28,35,42每個(gè)數(shù)的概率都是1/7,當(dāng)每個(gè)數(shù)都加上+rand_7之后，則1-49是等概率產(chǎn)生的，1/7 × 1/7 = 1/49,中間不會(huì)出現(xiàn)重復(fù)數(shù)據(jù)

所以，我們用rand_7產(chǎn)生了rand_49，有了rand_49,按照最初上面過(guò)濾的方法，我們當(dāng)然可以獲得任何小于49的隨機(jī)函數(shù)