Implement Rand10() Using Rand7() (M)
題目
Given a function rand7 which generates a uniform random integer in the range 1 to 7, write a function rand10 which generates a uniform random integer in the range 1 to 10.
Do NOT use system's Math.random().
Example 1:
Input: 1
Output: [7]
Example 2:
Input: 2
Output: [8,4]
Example 3:
Input: 3
Output: [8,1,10]
Note:
rand7is predefined.- Each testcase has one argument:
n, the number of times thatrand10is called.
Follow up:
- What is the expected value for the number of calls to
rand7()function? - Could you minimize the number of calls to
rand7()?
題意
使用能夠隨機生成整數1-7的函式rand7()，來寫一個新的函式rand10()，使其能夠隨機生成整數1-10，
思路
- \(rand7()-1\) 生成整數 0-6
- \((rand7()-1)\times7\) 生成整數 [0, 7, 14, ..., 42]
- \((rand7()-1)\times7+rand7()\) 生成整數 1-49，即得到 rand49()
- 利用拒絕采樣來得到 1-40 范圍內的隨機整數num：通過rand49()得到一個數，如果大于40，則重新運行rand49()，否則賦值給num
- \(num\ \%\ 10+1\) 得到 1-10 范圍內的整數
代碼實作
Java
/**
* The rand7() API is already defined in the parent class SolBase. public int
* rand7();
*
* @return a random integer in the range 1 to 7
*/
class Solution extends SolBase {
public int rand10() {
int num = (rand7() - 1) * 7 + rand7();
return num <= 40 ? num % 10 + 1 : rand10();
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/144605.html
標籤：其他