已有方法 rand7 可生成 1 到 7 范围内的均匀随机整数,试写一个方法 rand10 生成 1 到 10 范围内的均匀随机整数。
//莫名其妙AC的解法
func rand10() int {
sum := 0
for i:=0; i < 5; i++{
sum += rand7()
}
return sum % 10 + 1
}
//官解
func rand10() int {
for {
row := rand7()
col := rand7()
idx := (row-1)*7 + col //解释见下方
if idx <= 40 { //拒绝
return idx % 10 +1
}
}
}
官解原理:基于这样一个事实
$$ (randX() - 1) \times Y + randY() $$
可以等概率的生成
$$ [1, X \times Y] $$
范围的随机数对于随机数 randN,只要 K 是 N 的约数(或者说 N 是 K 的整数倍),都可以通过randN 一步得到 randK
$$ randK = (randN \mod K) + 1 $$