隨機數的組合問題是面試中的常客。比如我曾被問到:「有一個能生成 1-5 隨機數的函數,怎樣把它擴大到 1-7?」
在解決之前,先看一個更簡單的問題:「有一個能生成 1-7 的函數,怎樣把它縮小到 1-5?」下面是生成 1-7 的 random7:
function random7() { return Math.floor(Math.random() * 7 + 1); }
如何把它變成生成 1-5 的函數?很簡單:在循環裡調用 random7,直到返回值小於等於 5 就結束並返回:
function random5() { var r = random7(); while(r > 5) { r = random7(); } return r; }
思路就是:如果生成的隨機數大於 5,就繼續調用 random7,直到它小於等於 5 為止。
回到正題,看看 1-5 如何擴大到 1-7。下面是生成 1-5 的函數:
function random5() { return Math.floor(Math.random() * 5 + 1); }
有一種很自然的想法:random5() 的範圍是 1-5,那兩個相加就是 2-10,再減 1 就是 1-9,於是照著上面的思路加個循環,小於等於 7 就返回:
function random7() { var r = random5() + random5() - 1; while(r > 7) { r = random5() + random5() - 1; } return r; }
這樣確實能把範圍擴大到 1-7,但問題來了:真正的隨機函數要求每個值出現的概率相等,而這種做法並不滿足。用概率論的組合知識算一下:生成 1 只有一種組合(兩個 random5() 都是 1),生成 2 卻有兩種組合(1+2 或 2+1)……顯然各值的概率並不相等,所以這種方法行不通。
要讓每個值概率相等,就得讓每個值的組合數相同。一種可行辦法是讓每個值的組合只有一種:
function random7() { var r = (random5() - 1) * 5 + random5(); while(r > 7) { r = (random5() - 1) * 5 + random5(); } return r; }
為什麼這樣就能保證概率相等?先看 (random5() - 1) * 5,容易算出它生成的可選值是 0、5、10、15、20;再與 random5()(取值 1、2、3、4、5)相加,兩者組合後可得到 1-25 之間的隨機數,而且每個值的組合都只有一種,因此概率彼此相等。
也許有人會問:(random5() - 1) * 5 這裡為什麼偏偏乘以 5?因為乘以 5 之後再與 random5() 相加,得到的數恰好連續且等概率。
以上討論的是 1-5 與 1-7 之間轉換的特殊情形,對於其他一般情形,大家可以自己動手試試。