主題

LeetCode - 470. Implement Rand10() Using Rand7() 解題心得

Not In My Back Yard | 2021-08-18 00:00:01 | 巴幣 0 | 人氣 56

題目連結:


題目意譯:
給定 API rand7() 其產生均勻地隨機整數於範圍 [1, 7] 之中,撰寫一個函式 rand10() 其產生其產生均勻地隨機整數於範圍 [1, 10]。你只能呼叫 API rand7(),且你不能呼叫任何其他 API 。請不要使用程式語言中的內建 random API。

每個測試資料會有一個內部參數 n ,代表著測試中的你實作的函式 rand10() 呼叫次數。注意該數字不是會傳入 rand10() 的參數。

進階:
函式 rand7() 的呼叫次數之期望值為何?
你會怎麼最小化 rand7() 的呼叫次數?

限制:
1 ≦ n ≦ 10 ^ 5



範例測資:
範例 1:
輸入: n = 1
輸出: [2]

範例 2:
輸入: n = 2
輸出: [2,8]

範例 3:
輸入: n = 3
輸出: [3,8,10]


解題思維:
利用這題提過的棄卻抽樣(Rejection Sampling)之策略——每次生成一個數字 R 為 rand7() + rand7() * 7 。

可以看到 R 將落於範圍 [8, 56] 這 49 個數字之中。而 49 無法被 10 整除,所以我們棄卻掉其中的 9 個數字(在此為範圍 [48, 56])。也就是我們重複生成 R 值直到其位於 [8, 47] 中。

可以看到此時的 R 值取 10 的餘數後,每個餘數(0 ~ 9)出現的機率將是均勻分布的。因此我們便得到了一個 1 ~ 10 之隨機數 (R % 10) + 1 (「%」為取餘數之操作)。



因為我們將重複地產生 R 值直到我們成功產出位於 [8, 47] 中的 R 值。因此「成功」的機率為 40 ÷ 49 、「失敗」的機率則為 9 ÷ 49。

可以看到這個試驗符合幾何分布(Geometric Distribution),所以「成功」所需的次數之期望值恰好為 1 ÷ (「成功」的機率) = 49 ÷ 40 = 1.225。

而每次我們會呼叫兩次的 rand7() ,所以呼叫次數期望值為 2 × 1.225 = 2.45 。

那我們要怎麼減少呼叫次數期望值呢?我們可以善加利用先前被我們拋棄的數字範圍 [48, 56] ,將位於此範圍中的 R 值 × 7 之後再呼叫一次 rand7() 並將兩者相加。

此時我們便會產生新的數字範圍 [337, 399] 總共 63 個數字,然後一樣按照先前的邏輯捨棄掉最後的 3 個數字 [397, 399],落於 [337, 396] 範圍之中的 R 值,可得 1 ~ 10 之隨機數 (R % 10) + 1。

這時候呼叫次數期望值將降低至 2.20 左右。

可以看到我們依舊可以再利用棄卻掉的值,再更進一步地降低期望值。這方面就交給讀者繼續推導。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

相關創作

更多創作