題目描述：470. 用 Rand7() 實現(xiàn) Rand10()

因為是第一次接觸到這樣的題目，毫無思緒，對官方題解也是“不知道為什么要這么做”?？催^一些題解之后才逐漸明白，現(xiàn)在讓我自己來寫題解，我打算先從簡單的開始講起。

Part 1

假設已知rand2()可以均勻的生成[1,2]的隨機數(shù)，現(xiàn)在想均勻的生成[1,4]的隨機數(shù)，該如何考慮？

我想如果你也像我一樣第一次接觸這個問題，那么很可能會這么考慮——令兩個rand2()相加，再做一些必要的邊角處理。如下：

rand2() + rand2() = ? ==> [2,4]1 ? ?+ ? 1 ? ? = 21 ? ?+ ? 2 ? ? = 32 ? ?+ ? 1 ? ? = 32 ? ?+ ? 2 ? ? = 4

// 為了把生成隨機數(shù)的范圍規(guī)約成[1,n]，于是在上一步的結(jié)果后減1

(rand2()-1) + rand2() = ? ==> [1,3]0 ? ? ? + ? 1 ? ? = 10 ? ? ? + ? 2 ? ? = 21 ? ? ? + ? 1 ? ? = 21 ? ? ? + ? 2 ? ? = 3

可以看到，使用這種方法處理的結(jié)果，最致命的點在于——其生成的結(jié)果不是等概率的。在這個簡單的例子中，產(chǎn)生2的概率是50%，而產(chǎn)生1和3的概率則分別是25%。原因當然也很好理解，由于某些值會有多種組合，因此僅靠簡單的相加處理會導致結(jié)果不是等概率的。

因此，我們需要考慮其他的方法了。

仔細觀察上面的例子，我們嘗試對 (rand2()-1) 這部分乘以 2，改動后如下：

(rand2()-1) × 2 + rand2() = ? ==> [1,3]0 ? ? ? ? ? ?+ ? 1 ? ? = 10 ? ? ? ? ? ?+ ? 2 ? ? = 22 ? ? ? ? ? ?+ ? 1 ? ? = 32 ? ? ? ? ? ?+ ? 2 ? ? = 4

神奇的事情發(fā)生了，奇怪的知識增加了。通過這樣的處理，得到的結(jié)果恰是[1,4]的范圍，并且每個數(shù)都是等概率取到的。因此，使用這種方法，可以通過rand2()實現(xiàn)rand4()。

也許這么處理只是我運氣好，而不具有普適性？那就多來嘗試幾個例子。比如：

(rand9()-1) × 7 + rand7() = resulta ? ? ? ? ? ? ? b

為了表示方便，現(xiàn)將rand9()-1表示為a，將rand7()表示為b。計算過程表示成二維矩陣，如下：

可以看到，這個例子可以等概率的生成[1,63]范圍的隨機數(shù)。再提煉一下，可以得到這樣一個規(guī)律：
已知 rand_N() 可以等概率的生成[1, N]范圍的隨機數(shù)
那么：
(rand_X() - 1) × Y + rand_Y() ==> 可以等概率的生成[1, X * Y]范圍的隨機數(shù)
即實現(xiàn)了 rand_XY()
?

part2

那么想到通過rand4()來實現(xiàn)rand2()呢？這個就很簡單了，已知rand4()會均勻產(chǎn)生[1,4]的隨機數(shù)，通過取余，再加1就可以了。如下所示，結(jié)果也是等概率的。

rand4() % 2 + 1 = ?1 % 2 ? ?+ 1 = 22 % 2 ? ?+ 1 = 13 % 2 ? ?+ 1 = 24 % 2 ? ?+ 1 = 1

事實上，只要rand_N()中N是2的倍數(shù)，就都可以用來實現(xiàn)rand2()，反之，若N不是2的倍數(shù)，則產(chǎn)生的結(jié)果不是等概率的。比如：

rand6() % 2 + 1 = ?1 % 2 ? ?+ 1 = 22 % 2 ? ?+ 1 = 13 % 2 ? ?+ 1 = 24 % 2 ? ?+ 1 = 15 % 2 ? ?+ 1 = 26 % 2 ? ?+ 1 = 1 rand5() % 2 + 1 = ?1 % 2 ? ?+ 1 = 22 % 2 ? ?+ 1 = 13 % 2 ? ?+ 1 = 24 % 2 ? ?+ 1 = 15 % 2 ? ?+ 1 = 2

Part 3

ok，現(xiàn)在回到本題中。已知rand7()，要求通過rand7()來實現(xiàn)rand10()。

有了前面的分析，要實現(xiàn)rand10()，就需要先實現(xiàn)rand_N()，并且保證N大于10且是10的倍數(shù)。這樣再通過rand_N() % 10 + 1 就可以得到[1,10]范圍的隨機數(shù)了。

而實現(xiàn)rand_N()，我們可以通過part 1中所講的方法對rand7()進行改造，如下：

(rand7()-1) × 7 + rand7() ?==> rand49()
但是這樣實現(xiàn)的N不是10的倍數(shù)啊！這該怎么處理？這里就涉及到了“拒絕采樣”的知識了，也就是說，如果某個采樣結(jié)果不在要求的范圍內(nèi)，則丟棄它。基于上面的這些分析，再回頭看下面的代碼，想必是不難理解了。

class Solution extends SolBase {public int rand10() {while(true) {int num = (rand7() - 1) * 7 + rand7(); // 等概率生成[1,49]范圍的隨機數(shù)if(num <= 40) return num % 10 + 1; // 拒絕采樣，并返回[1,10]范圍的隨機數(shù)}} }

Part 4: 優(yōu)化

這部分具體的代碼是參考官方題解的，不過是我自己在理解了part 1和part 2之后才看懂的，一開始看真不知道為什么（/(ㄒoㄒ)/~~...

根據(jù)part 1的分析，我們已經(jīng)知道(rand7() - 1) * 7 + rand7() 等概率生成[1,49]范圍的隨機數(shù)。而由于我們需要的是10的倍數(shù)，因此，不得不舍棄掉[41, 49]這9個數(shù)。優(yōu)化的點就始于——我們能否利用這些范圍外的數(shù)字，以減少丟棄的值，提高命中率總而提高隨機數(shù)生成效率。

class Solution extends SolBase {public int rand10() {while(true) {int a = rand7();int b = rand7();int num = (a-1)*7 + b; // rand 49if(num <= 40) return num % 10 + 1; // 拒絕采樣a = num - 40; // rand 9b = rand7();num = (a-1)*7 + b; // rand 63if(num <= 60) return num % 10 + 1;a = num - 60; // rand 3b = rand7();num = (a-1)*7 + b; // rand 21if(num <= 20) return num % 10 + 1;}} }

作者：kkbill
鏈接：https://leetcode-cn.com/problems/implement-rand10-using-rand7/solution/cong-zui-ji-chu-de-jiang-qi-ru-he-zuo-dao-jun-yun-/
來源：力扣（LeetCode）
著作權歸作者所有。商業(yè)轉(zhuǎn)載請聯(lián)系作者獲得授權，非商業(yè)轉(zhuǎn)載請注明出處。

總結(jié)

以上是生活随笔為你收集整理的从最基础的讲起如何做到均匀的生成随机数的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。