0470. Implement Rand10 Using Rand7

470. Implement Rand10() Using Rand7() #

题目 #

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.

Follow up:

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

题目大意 #

已有方法 rand7 可生成 1 到 7 范围内的均匀随机整数,试写一个方法 rand10 生成 1 到 10 范围内的均匀随机整数。不要使用系统的 Math.random() 方法。

提示:

  • rand7 已定义。
  • 传入参数: n 表示 rand10 的调用次数。

进阶:

  • rand7()调用次数的 期望值 是多少 ?
  • 你能否尽量少调用 rand7() ?

解题思路 #

  • 给出 rand7() 要求实现 rand10()
  • rand7() 等概率地产生1,2,3,4,5,6,7。要想得到 rand10() 即等概率的生成 1-10 。解题思路是先构造一个 randN(),这个 N 必须是 10 的整数倍,然后 randN % 10 就可以得到 rand10() 了。所以可以从 rand7() 先构造出 rand49(),再把 rand49() 中大于等于 40 的都过滤掉,这样就得到了 rand40(),在对 10 取余即可。
  • 具体构造步骤,rand7() --> rand49() --> rand40() --> rand10()
    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]
  • 这道题可以推广到生成任意数的随机数问题。用 randN() 实现 randM()M>N。步骤如下:
    1. randN() 先实现 randX(),其中 X ≥ M,X 是 M 的整数倍。如这题中的 49 > 10;
    2. 再用 randX() 生成 randM(),如这题中的 49 —> 40 —> 10。
  • 举个例子,用 rand3() 生成 rand11(),可以先生成 rand27(),然后变成以 22 为界限,因为 22 是 11 的倍数。生成 rand27() 的方式:3 * 3 * (rand3() - 1) + 3 * (rand3() - 1) + (rand3() - 1),最后生成了 rand11();用 rand7() 生成 rand9(),可以先生成 rand49(),然后变成以 45 为界限,因为 45 是 9 的倍数。生成 rand49() 的方式:(rand7() - 1) * 7 + (rand7() - 1),最后生成了 rand9();用 rand6() 生成 rand13(),可以先生成 rand36(),然后变成以 26 为界限,因为 26 是 13 的倍数。生成 rand36() 的方式:(rand6() - 1) * 6 + (rand6() - 1),最后生成了 rand13()

代码 #


package leetcode

import "math/rand"

func rand10() int {
	rand10 := 10
	for rand10 >= 10 {
		rand10 = (rand7() - 1) + rand7()
	}
	return rand10%10 + 1
}

func rand7() int {
	return rand.Intn(7)
}

func rand101() int {
	rand40 := 40
	for rand40 >= 40 {
		rand40 = (rand7()-1)*7 + rand7() - 1
	}
	return rand40%10 + 1
}


⬅️上一页

下一页➡️

Calendar Sep 6, 2020
Edit Edit this page
本站总访问量:  次 您是本站第  位访问者