1.问题描述

这是一道我于 20220706 周三上午于深圳科兴科学园 D1 参与富图社招二面遇到的算法题。

给定一个函数 rand1 会 50% 的概率输出 0 和 1，请利用 rand1 实现 rand9，等概率地输出 0~9 这 10 个数字。

2.难度级别

难度应该是 middle。

3.解决思路

从题目来看，有个已知条件，rand1() 会 50% 的概率输出 0 和 1，在已知条件的基础上实现一个新的函数 rand9()，所以相当于基于 50% 概率发生器创建一个 10% 的概率发生器。

怎么创建一个 10% 的事件发生器呢，我们从公式可知，rand1 产生事件概率 P(0)=50%，P(1)=50%，那么 rand1 执行两次，也就是两次结果都是 1 的概率为 25%，三次结果都是 1 的概率为 12.5%，四次执行都为1的概率为 6.25%，相当于四次产生的 1111 组合的概率为6.25%，也就是 1/16。

这个数据是不是很熟悉？我们用程序生成一下四次 0 和 1 产生的组合数：

0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111

就是个二进制数，转换成十进制之后，就是0~15，相当于 16 个数每个数发生的概率都是 1/16；也就是说，产生 0 到 9 的概率是相等的，虽然概率不是 1/10。

所以该问题解法是拒绝采样法：调用 4 次 rand1，生成 4 位的二进制数，然后再转换成 10 进制数，如果这个数大于 9，再重新生成即可。

4.实现示例

下面使用 Golang 给出实现示例。

首先我们实现 rand1。

package main

import (
	"math/rand"
)

// rand1 等概率输出 0 和 1。
func rand1() int {
    
	return rand.Intn(2)
}

再根据 rand1 实现 rand9：

// rand9 等概率输出 0 ~ 9。
func rand9() int {
    
	for {
    
		n := rand1()<<3 + rand1()<<2 + rand1()<<1 + rand1()
		if n < 10 {
    
			return n
		}
	}
}

rand9 输出示例：

1
4
8
6
9
3
2
2
8
5

参考文献

已知f(x) 传入的值 等概率 输出0 or 1，如果写一个f1(x）实现等概率输出0-9？| segmentfault
用 Rand7() 实现 Rand10() | LeetCode