close

中文翻譯

注意，srand 正常而言一份程式碼(專案)只能執行一次，如果它放在 for loop 裡，每次進行 rand 前就用 srand，會發現每次取出來的亂數是統一個數字。

洗牌 (shuffle) 法的概念是，方才的 [low, up] ，每個數字都視為撲克牌裡的一張牌，所以這副撲克牌共有 (up-low+1) 張，於是開陣列 Poker[up-low+1]，並填入 1: 100。

程式碼示意以下。

 

一樣的議題，若欲產生的整數亂數規模超過 RAND_MAX 時，這類方法也是有些數字沒辦法產生到。只是這類方式沒辦法產生的數字，是被打散到各區塊裡，而不是像取模運算子全擠在後半段。總之就是建議要額外處置懲罰翻譯

 

7.  不平均亂數問題

 

Code Snippet
  1. // 產生 [low翻譯社 up] 之隨機整數亂數
  2. int rand_int(int low翻譯社 int up)
  3. {
  4.     return (int)((rand() / (RAND_MAX+1.0)) * (up - low + 1.0) + low);
  5. }

Q1 : 為什麼要迥殊在 rand() 前面轉型成 double ?
A1 : 簡單的說，我怕有人雞婆，把後面的 1.0 自己寫成 1 ，這時候不加上 (double) 的話成果除出來必然是 0 ；若後面的 1.0 都不動它的話，前面的 double 可以拿掉無誤翻譯

要產生 20 個 [1,100] 不重覆之亂數，怎麼做？

再強迫轉型成整數資料型態。

乃至可包成副函式 或寫成一行。

9. 不重覆亂數問題 < 洗牌法 >

 

概念是 [low, up) 亂數，等於 (low~up 距離) * ( [0,1) 亂數 ) + (下限 low)。

 

 

 

 

另一種體式格局是用累計機率，我們先做累計機率的表出來

機率比較低的 rst ，都被安排到 rst 可能呈現之值的後半段。

 

 

double precision = 1.0 / RAND_MAX = 1.0 / 32767 = 3.05 * 10-5

Code Snippet
  1. void KnuthShuffle(int *arr, int n, int low, int up)
  2. {
  3.     int i, pos1, pos2, tmp;
  4.     int Size = up-low + 1; // 整份 poker 巨細
  5.  
  6.     // 設置裝備擺設一份 poker[Size]
  7.     int * Poker = (int*)malloc(sizeof(int) * Size);
  8.     for(i=0 ; i<Size; ++i) // 填入 low~up
  9.         Poker[i] = i+low;
  10.     // 入手下手洗牌
  11.     for(i=Size-1; i>0; --i){
  12.         // 隨機掏出 [0, i] 之 poker
  13.         pos = (int)(rand() / (RAND_MAX+1.0) * (i+1));
  14.         // 交換這兩張牌
  15.         tmp = Poker[pos];
  16.         Poker[pos] = Poker[i];
  17.         Poker[i]=tmp;
  18.     }
  19.     // 洗完牌, 前面的 n 張再給 Arr
  20.     for(i=0; i<n; ++i)
  21.         arr[i] = Poker[i];
  22.     free(Poker); // 釋放 poker    
  23. }

以無號數二進位而言，n bits 可表達之最大數為 2n-1 ，故可列下以下不等式

1~100 有 100 個元素，排序法體例是直接開兩個陣列 : int Rst[100], int Rnd[100]，

將上述的程式多履行幾回會發現，怎麼每次亂數產生的都一樣？緣由是沒設亂數種子。

 上面這段碼可以正確跑出結果無誤。

4. 產生固定局限的整數亂數

 

 

如許就不需暫存 seed 變數。

13. 其他

 

大亂數問題在上面有先提過了，假定要產生的整數亂數局限是 [0, 50000]，或產生的浮點數亂數精度為 1e-6，怎麼處理？

5. 產生浮點數亂數

 

 竣事以後，這只能產生 [0,240-1] 之亂數產生器，要再產生 [0,1] 之浮點亂數，就再除上 240-1。

像是 記憶體利用量、process id 、CPU 使用率 等，這些都是會隨情況更改，

step 1 : 較量爭論 所需 NEW_RAND_MAX  

 

 

組合出的亂數最大值最少要 1012 才可知足。

 

那什麼叫亂數種子？

 

 

rand() = 0, 1, 2, 3    : rst = 0
rand() = 4, 5, 6        : rst = 1
rand() = 7, 8, 9, 10  : rst = 2
rand() = 11, 12, 13  : rst = 3 

這部份只是簡單的數學推導，已知該怎麼做的可略過不看。

[0] 10 : 機率 = 0.123 ，累計機率 = 0.123，令為 CP[0]

而在 srand 那段，經常有人這麼寫

故環節程式碼換如下翻譯

 

一種委曲可接管 ( 其實也是大多還不太會用 library 之 coder 的解決方案 ) 之體式格局為：一次取兩個亂數，將數值擴大翻譯假定 RAND_MAX = 32767，佔了 15 bits( 111111111111111(2) = 32767(10) )，試斟酌以下程式碼。

 

那如果小數點後面加到 10 位數，不就要設一個巨細為 10^10 的陣列了？

 

憑據以上之論述，觀查可納出一結論：當要產生出 [low, up] 之整數亂數時，可有另一種方式，

我們先假定一種環境，若某個亂數產生器，他的 RAND_MAX = 13，目前要產生 [0,3] 之整數亂數。

產生浮點數亂數，凡是都是先獲得  [0翻譯社 1) 之浮點數亂數 ( 可以包括零，但不包含 1 )翻譯

[HomeWork] 依上述的數字出現之機率，做 10萬 次測試，最後真正現實上1翻譯社 2, 3, 4 泛起之次數、機率為何？是否接近於當初設定之機率？

1 泛起機率為 0.4 ;  2 泛起機率為 0.1 ;

3 呈現機率為 0.3 ;  4 出現機率為 0.2 ;

剛剛已給出了 rndf = [0, 1) 之公式，所以要擴展到 [low, up) 時，只要做點點竄就行，

 

 

Code Snippet
  1. #include <stdio.h>
  2. #include <time.h>
  3. #include <stdlib.h>
  4.  
  5. int main()
  6. {
  7.     int n = 20; // 找 20 個相異亂數
  8.     int i, cnt, num, Arr[20];
  9.     int find;
  11.     srand( (unsigned)time(NULL));
  12.     cnt = 0; // 已有不重覆亂數之個數
  13.     while(cnt < n){
  14.         
  15.         // 產生 [1, 100] 之整數亂數
  16.         // rand() / (RAND_MAX+1.0)) * (up - low + 1.0) + low
  17.         // num = rand()/(RAND_MAX+1.0)*(100-1+1.0) + 1;
  18.         num = (int)( rand() /(RAND_MAX+1.0)*100.0 + 1);
  19.  
  20.         // 到 Arr 裡查有無重覆產生
  21.         find = 0; // 假定沒發現
  22.         for(i=0; i<cnt; ++i){
  23.             if(Arr[i]==num) { // 有發現
  24.                 find = 1;
  25.                 break;
  26.             }
  27.         }
  28.         //
  29.         if(find==0) {     // 真的沒發現
  30.             Arr[cnt]=num; // 插足 Arr 裡
  31.             ++cnt;        // 找到個數 +1
  32.         }
  33.     }
  34.     // 最後輸出
  35.     for(i=0; i<n; ++i){
  36.         if(i%10==0) puts("");
  37.         printf("%3d "翻譯社 Arr[i]);
  38.     }
  39.     getchar();
  40.     return 0;
  41. }

 

(2) 依序填入 4 個 1、1個2、3個3、2個4。

(3) 隨機產生 [0翻譯社 9] 之整數亂數 , pos，再獲得 Arr[pos] 出來即可。

一種作法是先開巨細為 20 的陣列 Arr[20]，每產生一個亂數的時候，就到 Arr 裡面看有無重覆，假如沒有重覆才加進去，有重覆的話就再取下一個亂數。示例碼以下 < 贅變數良多，像 find 是可以完全拿掉的 >翻譯

 

硬要從函式裡面改的話，就是先產生 [low, up) 之浮點亂數後，

 

現假定一種情形是，希望不是每一個數泛起的機率都一樣，假設有 4 個數，

先講講整數亂數 [0, 50000]，倘若 RAND_MAX 只到 32767 時，以 % 體例而言，不管怎麼產生，[0,32767] 可正常產生，但 [32768,50000] ，共 17234 個數完全產生不了。即使先產生 [0,1) 浮點數，即用 rand() / RAND_MAX 這體例，也一樣會有 17233 個數產生不了，只是這 17233 個數不是最後的那幾個，而是被平均打散到 [0翻譯社50000] 裡面罷了。

以取模運算子撰之， rst = rand() % 4，看一下數值分佈的環境翻譯

Code Snippet
  1. #include <stdio.h>
  2. #include <time.h>
  3. #include <stdlib.h>
  4. int main()
  5. {
  6.     int result;
  7.     double r01, rnd;
  8.  
  9.     // 亂數種子
  10.     srand((unsigned)time(NULL));
  12.     // 產生 [0,1) 之亂數
  13.     r01 = (double)(rand()) / (RAND_MAX + 1.0) ;
  14.     // 產生 [1,7) 之亂數
  15.     rnd = r01 * (7.0 - 1.0) + 1.0;
  16.     // 強迫轉型給 result
  17.     result = (int)(rnd);
  18.     printf("result = %d ", result); // 輸出結果
  19.     getchar();
  20.     return 0;
  21. }

(2) shuffle_2 : 為確保每張牌最少被換過一次，依序拿第 i 張牌出來，隨機取出第 pos1 張牌，第 i 張牌與第 pos 張牌交換。

 

 

Code Snippet
  1. #include <stdio.h>
  2. #include <time.h>
  3. #include <stdlib.h> // RAND_MAX
  4. int main()
  5. {
  6.     int i;
  7.     srand( (unsigned)time(NULL));
  8.     for(i=0; i<10 ; ++i){
  9.         printf("%d ", rand() % 6 + 1);
  10.     }
  11.     getchar();
  12.     return 0;
  13. }

 

再斟酌 

result = (up - low) * rand() / (RAND_MAX + 1.0) + low;

再怎麼給亂數這組公式一個初始值？用 srand( ) 翻譯

所以 rst = 2 與 rst = 3 泛起的機率比力低，

rand() % (up - low + 1) + low 

所以要到達 10-12 精度時

機率比力低的 rst ，都被平均打散到 rst 可能呈現之值範圍內翻譯

result = (up - low) * rndf + low;  // 產生 [low翻譯社 up) 浮點亂數

C/C++ 之亂數函式放在 stdlib.h / cstdlib 裡面，在利用時直接呼喚 rand() 即可。以下典範為產生 5 個亂數，並輸出。

不平均亂數還有許多非凡的狀態，遇到時建議再念念機率統計，若是已有的機率模子，必可找到現有符合該機率模子之亂數產生器(像 tr1, boost , c++11 都有了) ，不然，只能從較特殊、列出來的機率模子那裡下手。

 

最後請注意本文在區間表達裡，開區間與閉區間 括號的利用，也就是，

2. 亂數種子

 

11. 大亂數問題 (I)

 

   int rst = ( rand() << 15 ) | rand();

Code Snippet
  1. typedef unsigned long long u64; // typedef
  2.  
  3. u64 rand40() {
  4.     return ( \
  5.         ( (u64)(rand() >> 1) << 26 ) | // high 14翻譯社 L shift 26bits
  6.         ( (u64)(rand() >> 2) << 13 ) | // high 13翻譯社 L shift 13bits
  7.         ( (u64)(rand() >> 2)       )); // high 13翻譯社 L shift 0bits
  8. }
  9.  
  10. double randf40() {
  11.     const u64 NEW_RAND_MAX = (1ULL << 40) - 1ULL;
  12.     return (double)rand40() / NEW_RAND_MAX;
  13. }

 

回到最初的問題，從 [1翻譯社100] 裡挑出 20 個不重覆之亂數，成績填到 Array 裡。這裡天成翻譯公司們先為這些數字做點符號界說表示。

 

假定 RAND_MAX = 32767 (15 bits) , 先想一想一般的亂數精度可以怎麼求

首先，1~6 恰好有 6 個數字，所以可以這麼寫

 

 

這四個示意的意義不同，

 

 

累計機率算出來以後，天成翻譯公司們只需要產生 [0, 1) 之随機浮點數亂數 rndf，

Knuth Shuffle 在洗牌的進程重點在於：

double low = 5.1 翻譯社 up = 7.3, result;

所以 rst = 1 和 rst = 3 出現的機率比較低，

現假定一問題為，該若何產生  [0, 1] 之間，10-12 精度之浮點亂數產生器。

Code Snippet
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <time.h>
  4.  
  5. void shuffle_1(int *arr, int n, int low, int up)
  6. {
  7.     int i, pos1, pos2, tmp;
  8.     int Size = up-low + 1; // 整份 poker 巨細
  9.  
  10.     // 設置裝備擺設一份 poker[Size]
  11.     int * Poker = (int*)malloc(sizeof(int) * Size);
  12.     for(i=0 ; i<Size; ++i) // 填入 low~up
  13.         Poker[i] = i+low;
  14.     // 起頭洗牌
  15.     for(i=0; i<Size; ++i){
  16.         // 隨機掏出兩張 [0,Size) 之 poker
  17.         pos1 = (int)(rand() / (RAND_MAX+1.0) * Size);
  18.         pos2 = (int)(rand() / (RAND_MAX+1.0) * Size);
  19.         // 交換這兩張牌
  20.         tmp = Poker[pos1];
  21.         Poker[pos1] = Poker[pos2];
  22.         Poker[pos2]=tmp;
  23.     }
  24.     // 洗完牌, 前面的 n 張再給 Arr
  25.     for(i=0; i<n; ++i)
  26.         arr[i] = Poker[i];
  27.     free(Poker); // 釋放 poker
  28.     
  29. }
  30. int main()
  31. {
  32.     int low = 1, up=100;
  33.     int i翻譯社 n = 20;
  34.     int arr[20];
  35.     srand((unsigned)time(NULL));
  36.     shuffle_1(arr, n翻譯社 low翻譯社 up); // 洗牌
  37.     for(i=0; i<n; ++i) // 顯示成績
  38.         printf("%d "翻譯社 arr[i]);
  39.     getchar();
  40.     return 0;
  41. }

 

看碼最清晰。

另使用 % 取亂數，個人感覺較不當，緣由在 6. 再談整數亂數 申明並給方法。

接下來可以認真討論，為什麼大大都較不建議用取模運算子 (mod , %) 來求浮點亂數了。

(1) 從後面洗回來。for (j=size-1 ; j>0 ; --j) 注意，辨別式裡沒有等於零翻譯

鑑於亂數應符合平均之特征，故較多人建議別用取模 (mod) 方式取整數亂數。

 

Code Snippet
  1. #include <stdio.h>
  2. #include <stdlib.h> // RAND_MAX
  3. int main()
  4. {
  5.     printf("%d ", RAND_MAX);
  6.     getchar();
  7.     return 0;
  8. }

 

 

Q4 : 上面規範都是在計議不含上界的情況，如果要含上界的話呢？
A4 : 很簡單，把上面的 RAND_MAX + 1.0 部分，全都改成 RAND_MAX 便可，這樣就有機遇出現上界。

交換時連 Rst 也一路交換 Swap(Rst[i], Rst[j])，程式碼約如下述 < 排序法用較低效之排序 > 翻譯

但有些變更性可能不大，而最經常使用來給初始值的，是時候，所以上述程式改如下。

概念上之程式碼約以下述 < 這只是一份示例，會有更好的寫法 >翻譯

 

Q3 : 那除加上 1.0 這數字外，可以改成加其他數字啊！諸如 2.0 , 100.0, 10000.0 之類的。
A3 : 又如我方才所說，是要產生 [0,1) 之間的浮點數亂數，假定 RAND_MAX = 32767，如果加上 10000.0 的話，這個結果最大值會釀成了 32767 / (32767+10000) = 0.247，顯著 [0.25, 1.0) 都沒機遇生成了。但如果改成 0.5 , 之類，小於 1 較大的小數，到是可接受，不外這類數字幾近沒人在用。

step 3 : 由 bit 數產生亂數

 

3 顆骰子點數最小為 3 ，最大為 18，所以輸出時只要判定 3~18 呈現的次數便可。下面程式碼沒優化過，對初學者而言較易懂。

 

這裡要提醒，假如亂數產生的規模已跨越 RAND_MAX 的話，如產生 [-1000, +50000] 之亂數，必須額外進行處置懲罰，這類撰寫，只有前面的 RAND_MAX 數字有機遇呈現，其他後面的數字全都沒機遇看到翻譯

 

由於 n 必為大於等於1之整數，故取 40。

另本文附程式碼，不附執行了局，有興趣自己跑一遍。

 

 

 

Code Snippet
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <time.h>
  4. int main()
  5. {
  6.     int i;
  7.     unsigned seed;
  8.     seed = (unsigned)time(NULL); // 取得時候序列
  9.     srand(seed); // 以時候序列當亂數種子
  10.     for(i=0; i<5; ++i)
  11.         printf("%d ", rand());
  12.     getchar();
  13.     return 0;
  14. }

這個記憶體底子就放不下翻譯

 

 

如斯下來可產生 30 bits 之亂數，局限從 [0, 215-1] 釀成了 [0翻譯社 230-1]。如有需要，可再取二次、取三次、取四次等等，但這會有潛伏問題存在，一方面利用 rand() 之亂數產生器，平常週期其實不特別很是長 ( 像 vc, gcc 之 rand 週期只到 231 閣下)，且平均度也有待測試，這也是筆者建議直接再找另外一支亂數產生器之緣由。

填完之後，對 Rnd 做排序，而在排序過程當中有效到交換，Swap (Rnd[i], Rnd[j])

Code Snippet
  1. int low = -5 翻譯社 up = 10 ; // 上下限
  2. int result; // 結果
  3. double r01 翻譯社 r ;
  4. r01 = (double)rand() / (RAND_MAX+1.0); // 產生 [0翻譯社 1) 浮點亂數
  5. r = r01 * (up - low + 1.0) + low ; // 產生 [low, up+1) 浮點亂數
  6. result = (int)r;  // 最後強制轉型翻譯

 筆者所知只有這兩種方式，有其他方法迎接接洽翻譯

別的亂數道理也全都跳過 < 重點是亂數的產生道理也不只一種 >。

 

針對這類較簡單的機率數字，1 2 3 4 呈現的比率為 4 : 1 : 3 : 2，加總為 10，

也由於是指導初學者，所以在某些用詞上會較不准確，

Q1 : 為什麼是產生 [1翻譯社 7) 之浮點數亂數，而不是產生 [1,6] 之浮點數亂數？
A1 : 重點在後半段還要強制轉型。若一起頭就產生 [1, 6] 之浮點亂數時，要使得轉型後了局為 6 只有一種前提可達成：rand() 必須是 RAND_MAX翻譯這部分道理很簡單，但建議本身想想比較有收成。

 

 

那初始值該給多少？初始值給固定的值都沒用，要會跟著環境變動的值才成心義，

rst = (int)( rand() / 14.0 * 4 ) ;

10-12 = 1.0 / NEW_RAND_MAX
NEW_RAND_MAX = 1012

[1] 20 : 機率 = 0.234 ，累計機率 = 0.123 + 0.234 = 0.357，令為 CP[1]

Code Snippet
  1. // 開始洗牌
  2. for(i=0; i<Size; ++i){
  3.     // 隨機取出 [0,Size) 之 poker
  4.     pos = (int)(rand() / (RAND_MAX+1.0) * Size);
  5.     // 互換這兩張牌
  6.     tmp = Poker[pos];
  7.     Poker[pos] = Poker[i];
  8.     Poker[i]=tmp;
  9. }

 

step 2 :  從 NEW_RAND_MAX 較量爭論所需 bits 數

 

實際上產生 [low翻譯社 up) 之整數亂數，就是產生 [low, up-1] 之整數亂數，

 

那，產生出 [low, up) 之浮點數隨機亂數(不含 up )怎做？

Q2 : 為什麼要加上 low ?
A2 : 不加 low 的話現實上產生的是 [0 翻譯社 up-low]，加上 low 的話才是 [low翻譯社 up]。

這裡是個重點，請別認為用不到很無聊跳過 < 如果熟的話大概也不會看這篇文章了吧。>

 

 

常見的不重覆亂數解決方案，大致上就這三種。

接下來就是細節了翻譯今朝撒佈的洗牌體例有幾項

 

 

rst = (int)((rand() / (RAND_MAX+1.0)) * (up - low + 1.0) + low);

 

我們以擲骰子為例，一個骰子有 6 個面，點數分別為1~6，要隨機擲一顆骰子怎麼做？

 

寫成一行型式

道理天成翻譯公司不講了 < 因目標是要 "會" 用就好 >，簡單的說產生器是一組公式，公式要給「初始值」。

rand() = 0, 4, 8, 12  : rst = 0
rand() = 1, 5, 9, 13  : rst = 1
rand() = 2翻譯社 6翻譯社 10      : rst = 2
rand() = 3翻譯社 7, 11      : rst = 3 

用乘、除法的環境

(2) 取整數亂數 pos，局限為 [0, j] ，交換 poker[j]翻譯社 poker[pos]

 

因陣列有 N 個元素，規模只能是 [0翻譯社 N) ，而不能是 [0翻譯社 N]翻譯

srand( (unsigned)time(NULL) );

 

rndf = (double) rand() / (RAND_MAX + 1.0); // 產生 [0, 1) 浮點亂數

 

(double) rand() / (RAND_MAX + 1.0 );

最快完全解決這問題的體式格局，是直接換一套亂數產生器的函式庫，這些在 C++11 翻譯社 boost, tr1 裡面已有異常富厚，乃至也有專門在寫亂數函式庫的 library，甚至較有水準的數值闡發函式庫也大多會有較佳品質的亂數函式庫泛起翻譯拿到時注意幾個點：RAND_MAX 是若幹？若以浮點亂數呈現的話，其精度是若幹？還有亂數重覆周期是多少。更主要的是，注意他們的亂數函式庫支不支援多行緒？最好找支援多行緒的函式庫，將來移植才對照沒問題。這幾點很主要。 

int high = rand() << 15; 
int low  = rand();
int rst  = high | low;

甚至三行可寫成一行

 

 

假如是要產生 [low翻譯社 up) 之隨機整數亂數的話呢？這在做陣列索引很常見，

double low = 5.1 , up = 7.3, rndf, result;

所以有種做法如下

% 叫取模運算子，不懂的話歸去翻書。如許下來可以肯定，result 只有 {0, 1翻譯社 2, 3, 4翻譯社 5} 6 種可能而已。但實際上骰子的範圍是  1~6，而不是 0~5，怎麼辦？很簡單，只要把成果 + 1 就好了翻譯本來的結果是 0~5 ，加1後了局變成 1~6。

亂數其他議題相當多，有些也欠好實作出來，本篇所提是較為基礎之部分，其他諸如 蒙地卡邏 MAMC、其他亂數散佈等議題，便不於此文探討。

Code Snippet
  1. #include <stdio.h>
  2. #include <time.h>
  3. #include <stdlib.h>
  4.  
  5. int main()
  6. {
  7.     int i翻譯社 pos翻譯社 n=4; // 4 個元素
  8.     int Num[4] = {10翻譯社 20翻譯社 30, 40}; // 欲泛起之數字
  9.     double Prob[4]= {0.123, 0.234, 0.345, 0.298}; // 數字對應之泛起機率
  10.     double CP[4];
  11.     double rf; // 隨機機率
  12.  
  13.     srand( (unsigned)time(NULL));
  14.     // step 1 : 做累計機率計算
  15.     CP[0] = Prob[0];
  16.     for(i=1; i<n; ++i)
  17.         CP[i] = CP[i-1] + Prob[i];
  18.  
  19.     for(i=0; i<10; ++i) { // 做 10 次測試
  20.         rf = rand() / (RAND_MAX + 1.0) ; // 產生 [0, 1) 亂數
  21.         
  22.         for(pos=0; pos < n; ++pos) // 查詢地點區間
  23.             if(rf <= CP[pos]) break;
  24.         printf("%d ", Num[pos]); // 輸出數字
  25.     }
  26.     getchar();
  27.     return 0;
  28. }

 

[3] 40 : 機率 = 0.298，累計機率 = 0.702 + 0.298 = 1.000，令為 CP[3]

 

切割體式格局為 15 + 15 + 10 = 40 bits，左移 bits 數依序為 [15+10翻譯社 10, 0]。 但斟酌到高位元之輪回率較低位元輪回率小，所以將 40 切割成 14 + 13 + 13，且掏出時取高 bits 為主，依序應當左移 bits 數為 [13+13翻譯社13翻譯社0]。

有些數字可能不會呈現 < 因為也才擲十次罷了 >，但多履行幾次應會泛起，且局限必然是 1~6 翻譯

去查抄 rndf 落在哪段區間，rndf < CP[i] 之最小 i 即為所求。

 

總合以上說明，事實上我們可以給出一組公式，若要產生 [low翻譯社 up]  之整數亂數，我們可以這麼做

這怎麼產生？還記得 RAND_MAX 是什麼意思吧？是 rand() 可能產生的最大值，

12. 大亂數問題 (II)

 

最大被界說在 stdlib.h / cstdlib 裡面的 RAND_MAX，所以要得知最大是幾多的話

這篇文章主要指導初學者利用亂數，同時附上常被翻出來計議的議題，C/C++合用，唯以 C 說話撰之。

再來是模擬洗牌的過程，洗牌體例異常非常多！第一種是，隨機抽出第 pos1 張，再隨機抽出第 pos2 張，再將這兩張牌互換翻譯進行 low-up+1 (100) 次。全部動作做完後，再把 poker 前面的 20 (n, 欲取幾個亂數) 張牌，放到 Arr 裡面，就是謎底了。

[a翻譯社 b]  翻譯社   (a翻譯社 b]  翻譯社 [a, b) ,  (a, b) 

今朝可以確定的是，RAND_MAX 至少會是 32767，最大會是若幹紛歧定。但以筆者手邊的 Visual C++ 2010 情況而言，這個值是 32767翻譯現實上 VC6.0 , VC2002 / 2003 , VC2008, VC2010 , gcc, Dev-C++ , Code::Blocks (with mingw) ，這個值也都剛好是 32767，只是他們實作的亂數細節分歧罷了。至於往後其他改版會不會讓 RAND_MAX 更大？那就看那些軟體( compiler ) 若何實作了。

試再想另外一種景遇，若 

 

Code Snippet
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <time.h>
  4.  
  5. #define SWAP(a翻譯社b){int t=a; a=b; b=t;}
  6. void SortShuffle(int *arr翻譯社 int n翻譯社 int low, int up)
  7. {
  8.     int i, j;
  9.     int Size = (up-low+1);
  10.     int *Rst = (int*)malloc(sizeof(int) * Size);
  11.     int *Rnd = (int*)malloc(sizeof(int) * Size);
  12.  
  13.     if(Rst==NULL || Rnd==NULL) return;
  14.  
  15.     for(i=0; i<Size; ++i){
  16.         Rst[i] = low + i; // 依序填入數值到 Rst
  17.         Rnd[i] = rand();  // 對 Rnd 取亂數
  18.     }
  19.     // 對 Rnd 做排序
  20.     for(i=0; i<Size-1; ++i){
  21.         for(j=i+1; j<Size; ++j){
  22.             if(Rnd[i] > Rnd[j]) {
  23.                 // 交換時連 Rst 也一路交流
  24.                 SWAP(Rnd[i],Rnd[j]);
  25.                 SWAP(Rst[i], Rst[j]);
  26.             }
  27.         }
  28.     }
  29.     // Rst 前 n 筆存入 arr
  30.     for(i=0; i<n; ++i)
  31.         arr[i] = Rst[i];
  32.     // 釋放記憶體
  33.     free(Rnd), free(Rst);
  34. }
  35. int main()
  36. {
  37.     int low = 1, up=100;
  38.     int i, n = 20;
  39.     int arr[20];
  40.     srand((unsigned)time(NULL));
  41.     SortShuffle(arr, n, low, up); // 洗牌
  42.     for(i=0; i<n; ++i) // 顯示後果
  43.         printf("%d ", arr[i]);
  44.     getchar();
  45.     return 0;
  46. }

2n-1 >= 1012  ，疏忽 1 所帶來之影響，雙方取 log10
log10(2n) >= 12，
n log10(2) >= 12
n >= 12 / log10(2) = 39.86

Ex 2 : 摸擬擲 3 顆骰子 500 次，記載點數和泛起的次數，最後輸出每個點數共出現幾回翻譯

 

程式碼約以下述。

再回到擲骰子的問題上，要產生 [1, 6] 之間的整數亂數，事實上有另外一種方法，就是先產生 [1, 7) 的浮點數亂數，之後再強迫轉型成整數，所以程式碼以下所示翻譯

Ex 1 : 摹擬擲一顆骰子擲 10 次，並輸出其效果。

1. 根基利用

 

這種體式格局大多被納為暴力法之一種模式，但本色上在某些環境它是蠻合適用的。若是只是要用2、三個相異的亂數，這方式很合適，直接用 do-while 做，甚至不需要開陣列便可完成翻譯

(1) 開巨細為 10 的陣列 Arr[10]，

 

10 出現機率為 0.123， 20 泛起機率為  0.234，

30 泛起機率為 0.345， 40 出現機率為  0.298，

(1) shuffle_1 : 隨機掏出第 pos1 張、pos2 張，再進行交換，也就是上面的體例翻譯

 

即是產生 [low, up+1) 之浮點數亂數後，再進行強迫轉型成整數。以下。

[1翻譯社32767]，挑32767個不重覆亂數，它的履行時候就頗費時了，這時候就不斟酌利用這方法。

再來看浮點數亂數，要到達1e-6 精度問題，這只是不異問題換個型態泛起而已。若 RAND_MAX 只到 32767，產生的亂數最小精度是 1/32767，約為 3.1 E -5 ，達不到精度要求為 1e-6 之需求翻譯

Code Snippet
  1. typedef unsigned long long u64;       // typedef
  2. u64 rst = ( (u64)(rand()) << 25 ) |   // bit[39:25]
  3.     (u64)(rand()) << 10 ) |           // bit[24:10]
  4.     (u64)(rand()& 0x3ffULL ) ;        // bit[9:0]

 8. 不重覆亂數問題 < 暴力法 >

 

照上面的方式，不就要設一個巨細為 1000 的陣列了嗎？

後面會講為什麼要知道亂數最大值，這是一個主要的值。

再續上個問題，從 [1,100] 裡挑出 20 個不重覆之亂數，成果填到 Array 裡翻譯

利用 shuffle 必需額外再多設置裝備擺設一份 (up-low+1) 之記憶體空間，若自己 poker 張數許多 ( 欲遴選的局限很大)，但欲取得的值很小 ( n 很小 ) ，事實上也不合適用 shuffle，除鋪張空間之外，還揮霍了一最先填數字的時間，此時反而以暴力法來做較為得當。像是在 [1,20000] 掏出 10 個相異亂數時，此時用暴力法便較為得當。

 大亂數問題至此竣事翻譯提示，一般簡單統計用的亂數可以用此法產生沒錯 ( 像一些演變式演算法，或蒙地卡羅演算法)，若用於加解密等，每每不會再用 rand() 方式進行亂數產生。

像 compiler、IDE 會有心混為一談翻譯

Rst[100] 從 1 填到 100，Rnd[100] 是陸續取100個亂數填進去，

Code Snippet
  1. #include <stdio.h>
  2. #include <time.h>
  3. #include <stdlib.h> // RAND_MAX
  4. int main()
  5. {
  6.     int RunTimes = 500  ; // 測試次數
  7.     int SumTimes[20]={0}; // 紀錄點數出現的次數翻譯社 全歸零
  8.     int i翻譯社 sum翻譯社 rnd;
  9.  
  10.     // 進行測試
  11.     for(i=0; i<RunTimes; ++i) {// 測試 RunTimes 次
  12.         rnd = rand() % 6 + 1 ; // 第一顆骰子出現點數
  13.         sum = rnd;             // 記載總合
  14.         rnd = rand() % 6 + 1 ; // 第二顆骰子呈現點數
  15.         sum = sum + rnd;       // 記載總合
  16.         rnd = rand() % 6 + 1 ; // 第三顆骰子泛起點數
  17.         sum = sum + rnd;       // 紀錄總合
  18.  
  19.         // 將呈現 sum 點數之次數加1
  20.         SumTimes[sum] = SumTimes[sum]+1;
  21.     }
  22.  
  23.     // 輸出成果
  24.     sum = 0;
  25.     for(i=3; i<=18; ++i) {
  26.         printf(" %2d 點泛起了 %3d 次 "翻譯社 i翻譯社 SumTimes[i]);
  27.         sum = sum + SumTimes[i]; // 再驗證總合是不是500次
  28.     }
  29.     printf("共  %3d 次 ", sum);
  30.     getchar();
  31.     return 0;
  32. }

 

 

 

 

 

result = rand() % 6 

6. 再談整數亂數

 

Code Snippet
  1. typedef unsigned long long u64; // typedef
  2. u64 rst = ( \
  3.      ( (u64)(rand() >> 1) << 26 ) | // high 14, L shift 26bits
  4.      ( (u64)(rand() >> 2) << 13 ) | // high 13, L shift 13bits
  5.      ( (u64)(rand() >> 2)       )); // high 13, L shift 0bits

< 加起來恰好等於 1 沒錯 >

Code Snippet
  1. // 產生 [low, up) 之隨機亂數
  2. int rand_int2(int low, int up)
  3. {
  4.     return (int)((rand() / (RAND_MAX+1.0)) * (up - low) + low);
  5. }

 

[2] 30 : 機率 = 0.345，累計機率 = 0.357 + 0.345 = 0.702，令為 CP[2]

Q2 :  那為什麼分母還要希奇加上 1.0 ?
A2  : 前面有說過了，rand() 最大值可到 RAND_MAX， 不加上 1.0 的話會使得 (double) rand() / RAND_MAX ，成效有機率釀成 1 ，但這與我的前提：不包括 1 是相違的。

C/C++ 供給的 rand() ，它有局限限制，最小是 0 ，最大是多少？

 

這類作法較少人用。緣由是它記憶體空間比其他方法最少多出兩倍，別的時候也大多花在排序法上面 (較佳也是 nlogn 複雜度)，故幾乎沒人用。

真正顛末證實「怎麼洗較好」的是楊氏洗牌法 ( 或稱 Knuth Shuffle )翻譯

怎麼做？

Code Snippet
  1. #include <stdio.h>
  2. #include <time.h>
  3. #include <stdlib.h>
  4.  
  5. int main()
  6. {
  7.     int i, j, pos;
  8.     int Arr[10]; // 開巨細為 10 的陣列 Arr[10]
  9.     
  10.     //  依序填入 4 個 1、1個2、3個3、2個4
  11.     Arr[0]=Arr[1]=Arr[2]=Arr[3] = 1; // 4 個 1
  12.     Arr[4]=2 ; // 1 個 2
  13.     Arr[5] = Arr[6] = Arr[7] = 3 ; // 3 個 3
  14.     Arr[8] = Arr[9] = 4; // 2 個 4
  15.    
  16.     srand( (unsigned) time(NULL) );
  17.     // 隨機產生 [0, 9] 之整數亂數 翻譯社 pos，再取得 Arr[pos] 出來
  18.     for(i=0; i<10; ++i) {// 取 10 次
  19.         // 產生 [0翻譯社9] 整數亂數 pos
  20.         pos = (int)(rand() / (RAND_MAX+1.0) * 10) ;
  21.         // 掏出 Array[pos]
  22.         printf("%d "翻譯社 Arr[pos]);
  23.     }
  24.     getchar();
  25.     return 0;
  26. }

筆者不知道上面這兩問題的謎底。因這兩種洗牌體式格局沒被顛末證實怎麼洗對照「亂」，

Code Snippet
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. int main()
  4. {
  5.     int i;
  6.     for(i=0; i<5; ++i)
  7.         printf("%d ", rand());
  8.     getchar();
  9.     return 0;
  10. }

Q1 : 為什麼是 % (up-low+1) 翻譯社 而不是 % (up-low) ?
A1 : 因 low~up 一共有 (up-low+1) 個數。拿產生 [1翻譯社6] 來說，現實上共有 6-1+1 = 6 個數。

10. 不重覆亂數問題 < 排序法 >

 

3. 得知亂數最大值

 

在假定 RAND_MAX = 32767 之情形下，取一次 rand() 有 15 bits，故要到 40 bits 最少要取 3 次才可到達翻譯但以筆者手邊環境而言，int / unsigned int 只有 32 bits ，沒設施到達 40 bits 之要求，故改用資料型態 unsigned long long ( 更好的做法是用 uint64_t ) 去存後果，下面是一種作法。

方才的典範是，[1翻譯社100]，100 個數，挑 20 個相異亂數翻譯但如果把前提改過：

陸陸續續寫了 EA  一、二年，之前亂數指導文回頭看時才發現，怎麼有這麼多細節的毛病、沒系統翻譯

 

一個方式是直接以 rand_int(low, up-1) 體式格局代入上式；

從 [low翻譯社 up] 裡，挑出 n 個不重覆之亂數，結果填到 Array 裡。

 

所以寫出這段碼出來翻譯

有幾個議題曾被評論辯論過：(1) 多洗幾次牌是否是會比力亂？ (2) 最好的洗牌次數是洗幾回？



引用自: http://edisonx.pixnet.net/blog/post/91314418-%5b%e4%ba%82%e6%95%b8%5d-%3c%e7%b4%b0%e8%aa%aa%3e-c-c%2有關各國語文翻譯公證的問題歡迎諮詢天成翻譯公司02-77260931
arrow
arrow
    文章標籤
    翻譯社
    全站熱搜
    創作者介紹
    創作者 vickieg11m1 的頭像
    vickieg11m1

    waynepearlep

    vickieg11m1 發表在 痞客邦 留言(0) 人氣()

    E-mail轉寄