# 470. Implement Rand10() Using Rand7() 用 Rand7() 实现 Rand10()

@TOC

## # 题目描述

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:

1. rand7 is predefined.
2. Each testcase has one argument: n, the number of times that rand10 is called.

1. What is the expected value for the number of calls to rand7() function?
2. Could you minimize the number of calls to rand7()?

## # 解题方法

1. rand7()等概率地产生1,2,3,4,5,6,7.
2. rand7() - 1等概率地产生[0,6].
3. (rand7() - 1) *7等概率地产生0, 7, 14, 21, 28, 35, 42
4. (rand7() - 1) * 7 + (rand7() - 1)等概率地产生[0, 48]这49个数字
5. 如果步骤4的结果大于等于40，那么就重复步骤4，直到产生的数小于40
6. 把步骤5的结果mod 10 再加1， 就会等概率的随机生成[1, 10]

rand7 --> rand49 --> rand40 --> rand10.

``````7 * (rand7() - 1) + rand7() - 1
``````

``````# The rand7() API is already defined for you.
# def rand7():
# @return a random integer in the range 1 to 7

class Solution:
def rand10(self):
"""
:rtype: int
"""
return self.rand40() % 10 + 1

def rand49(self):
"""
random integer in 0 ~ 48
"""
return 7 * (rand7() - 1) + rand7() - 1

def rand40(self):
"""
random integer in 0 ~ 40
"""
num = self.rand49()
while num >= 40:
num = self.rand49()
return num
``````

C++代码如下：

``````// The rand7() API is already defined for you.
// int rand7();
// @return a random integer in the range 1 to 7

class Solution {
public:
int rand10() {
return rand40() % 10 + 1;
}

int rand49() {
return (rand7() - 1) * 7 + (rand7() - 1);
}

int rand40() {
int r = rand49();
while (r >= 40) {
r = rand49();
}
return r;
}
};
``````

## # 日期

2018 年 8 月 18 日 —— 天在下雨 2019 年 1 月 23 日 —— 又一连过去了几天