近日在做一個入職練習中，我遇到了隨機數的問題，將分析過程做些整理。
本文主要討論大范圍內隨機數的產生辦法，討論在隨機范圍內的等概率問題。 一，要求 1， 產生一個比較大的隨機數。 2， 產生的隨機數在隨機范圍內等概率。 二，知識背景 我們知道在C語言中有rand()函數可以提供隨機數，rand()函數的范圍為0到32727。我們假定認為rand()產生的隨機數在0到32727范圍內是等概率的。如果我們需要得到一個小范圍內的隨機數，比如0到55之間的隨機數，那我們可以采用rand()%55。但是對於我們要得到一個更大范圍內的隨機數，rand()便滿足不了我們的要求。 三，探討過程 1，兩個rand相乘 假設我們要產生一個10億內的隨機數，想到rand()可以產生0到32727，那麼我們可以采用rand()*rand()，剛好能達到10億的范圍。 可是我們不難發現rand()*rand()會有問題，最大的問題是在規定范圍內產生的隨機數概率不等，比如一個大於32727的素數，就永遠產生不了。而對於很多合數，出現的頻率會非常高。 2，按位組合 首先我們找到上限數字的位數，然後對每一位產生一個0到9的隨機數，並將產生的一系列0到9的數字組合起來。假設我們要產生一個10億內的隨機數，也就是我們需要產生0到999999999之間的隨機數，我們首先求得999999999的位數是9位，然後我們產生9個數字，並將他們組合成一個9位數。比如：872345671，023478652。 看上去沒有什麼問題，我們很好地解決了一個特別的隨即范圍，即10億內。假如我們現在要產生一個60000內的隨機數，也就是需要產生一個0到59999之間的數。如果我們按照上述辦法，如果產生的數字大於59999，同時也是5位數，比如97863，我們該怎麼辦？ 3，求余法 我們最先想到的是，如果產生的數字98763）對范圍60000）求余，對一個數字求余，所得到的結果肯定是落在該數字的范圍內。 不難發現，我們這裡同樣有概率問題。對於40000到60000之間的數字，出現的概率為1/100000，對於0到40000之間的數字，出現的概率為2/100000，因此概率不等。 4，逐位檢驗法 我們將上限數字的逐位取出來，我們逐個產生0到該數字的隨機數。對於產生0到59999只的隨機數，我們先取第一位：5，我們產生一個0到5之間的隨機數，第二位：9，我們產生0到9之間的隨機數，最終組合出的5位則是0到59999之間。 我們發現，這也只能解決特殊的數字范圍。如果我們要產生一個0到51782之間的隨數，這個方法就失效了。比如33216這個數字就產生不了，因為33216第二位3比范圍51782）第二位1大，永遠產生不了。 5，丟棄法 同樣地，我們首先依然采用組合法產生一個規定位數的數據，如果我們發現我們產生的數字在我們的范圍之外，那我們選擇丟棄該數據，繼續產生隨機數，一直到我們產生我們在范圍內的隨機數。不難證明，丟棄一個不正確的數字本身並不影響產生正確數字的概率。 因此，采用按位組合法+丟棄法能滿足我們的要求。 這裡只討論了隨機數的上線，對於隨機數的下限同理。 四，源碼實現
- //產生一個0到9的隨機數
- static __inline int min_rand()
- {
- return rand()%10;
- }
- /*************************************************************/
- /* 函數作用：產生一個range范圍內的隨機數 */
- /* 參數1，range：取隨機數的范圍 */
- /* 返回：返回取得的數據 */
- /*************************************************************/
- int my_rand(const int range)
- {
- short bit = 0; //紀錄位數
- int tempt = range;
- int rand_data = 0;
- while ( tempt > 0 )
- {
- bit++;
- tempt = tempt/10;
- }
- while (bit--)
- rand_data = 10*rand_data + min_rand();//組合隨機數
- if (rand_data >= range)
- return my_rand(range);//產生隨機數不符合范圍，繼續
- return rand_data;
- }
本文出自 “鄒輝” 博客，請務必保留此出處http://zouhui.blog.51cto.com/3827922/869779
