470. leetcode题目讲解(Python):用 Rand7() 实现 Rand10()

题目如下:
用 Rand7() 实现 Rand10()

首先需要注意的是,数字1-10应该具有相同的生成概率。由于我们只能使用rand7函数,所以思路必然是组合使用rand7函数。

如果假设:

那么通过 x = a + (b - 1) * 7 可以获取数字 1 到 49:

对于数字x: 1—40,我们可以通过 (x - 1) % 10 + 1 来均等的生成1到10 的整数:

可以看到,每个数都出现了4次。对于41 — 49,比较简单的处理方式是直接抛弃。 直到获取的数字是1到40为止。 每次运行程序会生成1到40的概率p为: 40/49, 根据独立事件的期望公式Ex = np, 程序运行的期望运行次数为 1.225,每次运行会调用2次rand7函数,所以rand7函数的调用次数期望为 2.45。

参考代码如下:


欢迎关注微信公众号“苔原带”
邮箱