產生隨機數的基本方法

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

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

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

# 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 ( ) ) ;}

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

注意，在前面的例子中，rand()的輸出并沒有被限制在一個指定的范圍內，假設你想建立一個彩票選號器，其取值范圍是從1到44。你可以簡單地忽略掉rand()所輸出的在該范圍之外的值，但這將花費許多時間去得到所需的全部(例如6個)彩票號碼。假設你已經建立了一個令你滿意的隨機數發生器，它所產生的隨機數據范圍是從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;

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

你可以用不同的min和max值來驗證這個例子，你會發現它總是會正確地產生在新的rain和max值之間的隨機數。

下面來看一下隨機數的相關練習題目

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

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

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

接下來，就是判斷rand_3是否能等概率的產生1,2,3.也就是我們需要計算產生1,2,3的概率是否都是1/3.

首先，rand_7可以等概率的產生1-7,我們以rand_3生成1為例，假設：

•     第一次生成1的概率是1/7
•     第二次生存1的概率是4/7 * 1/7，因此第一次肯定是生成了大于3的數例如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 //等比數列
                                                  =  1/7 * ((1 - (4/7)^n) / 1 - 4/7) = 1/7 * 7/3 = 1/3

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

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

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

擴展

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

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

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

我們先看一下是否能等概率生成1-49,構造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，每個數的生成概率都是1/7,所以*7之后，可以等概率的生成0,7,14,21,28,35,42,每個數的概率都是1/7

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

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