主題
題目連結：
題目意譯：
給定 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 左右。
可以看到我們依舊可以再利用棄卻掉的值，再更進一步地降低期望值。這方面就交給讀者繼續推導。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
達人
