---

---

※ 引述《gauss760220 (章魚)》之銘言：
: 各位好
: 我剛學C++
: 目前學到有關亂數rand()的寫法
: 看了幾次還是不太懂
: 所以想po上來跟大家討論
: rand()是否為0~32767的數值?(這部分我不知有無理解錯誤)
: 以下為想問的程式
: randomize an integer in [0,100) :
: const int bucket = RAND_MAX / 100;
: do {r=rand()/bucket;} while (r>= 100);
: 就我的想法是
: RAND_MAX為32767 除以100後 bucket=327(因為整數除法)
: 接下來的do~while loop就看不太懂他在做什麼動作了
: 請高手指點
: 謝謝
這原理其實還是一樣簡單

假設我們想要一個 [0,x) 之間的隨機亂整數好了

那麼它的做法就是把 0 到 RAND_MAX 之間切成一樣長的 x 段  每段代表一個值

0       bucket   2*bucket  3*bucket  (x-1)*bucket  RAND_MAX = x*bucket
┌────┬────┬────┬          ┬────┐
│        │        │        │ ………… │        │
└────┴────┴────┴          ┴────┘
     0         1         2                    x-1

大概像這種感覺

要達成這樣的最簡單的解法就是把 rand() 值除以 bucket (就是每段的長度)

這樣這個分布就會自然讓各個數字平均出現 (因為每段一樣長)

不過這個圖只有在 RAND_MAX 能被 x 整除時才會像上面這樣

如果不能整除的時候會變成這樣：

0       bucket   2*bucket  3*bucket (x-1)*bucket x*bucket RAND_MAX
┌────┬────┬────┬          ┬────┬──┐
│        │        │        │ ………… │        │    │
└────┴────┴────┴          ┴────┴──┘
     0         1         2                    x-1      x

右邊有一小段 rand() 的結果直接除以 bucket 後會得到 x

所以就需要這個 while 迴圈來把這段的結果給濾掉

以原 PO 的例子來看  RAND_MAX = 32767  x = 100

那右邊那一段就相當於 rand() 得到 32700~32767 這個範圍

那個 while 迴圈只不過就是把這段給濾掉而已

---
至於另一種常用的 mod 做法只不過是把分布弄成這個樣子而已:

0                                                RAND_MAX
┌───────────────          ─────┐
│                               …………           │
└───────────────          ─────┘
0123...(x-1)0123...(x-1)0123...(x-1).........

那在 RAND_MAX 能被 x 整除時  最右邊會停在 x-1

這樣每個數字的機率就都是一樣的

但如果 RAND_MAX 不能被 x 整除時  最右邊會停在 (RAND_MAX % x) - 1

這就會造成 0 到這個數的出現機率比其他數多了那麼一點點

(這應該就是有些地方在說不要用 mod 取亂整數的原因...)

改法同樣簡單  把最右邊那一段不到 x 的切掉就好

(也就是當 rand() 出現比 RAND_MAX - (RAND_MAX % x) 大的數字時就重取)

計算上也不會複雜到哪裡去就是了...

(所以我實在搞不懂那些只會叫說別用 mod 取亂數而不提怎麼改進的文章在想什麼)

--
"LPH" is for "Let Program Heal us"....

--
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.28.92

--
Shaken, Not Stirred.
--
※ 作者: TL 時間: 2013-01-27 17:50:26