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

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

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

下面的例子用一種簡單而有效的辦法來產(chǎn)生一個相當隨機的“種子”值——當天的時間值。

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

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

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;

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

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

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

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

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

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

接下來，就是判斷rand_3是否能等概率的產(chǎn)生1,2,3.也就是我們需要計算產(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

同理，可驗證生成2,3的概率均為1/3

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

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

擴展

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

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

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

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

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

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

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