九章算法 | 字节跳动面试题：用 Rand7()实现 Rand10()

[hakunamatata11]

已有方法rand7 可生成 1 到 7 范围内的均匀随机整数，试写一个方法 rand10生成 1 到 10 范围内的均匀随机整数。

不要使用系统的Math.random()方法

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

在线评测地址：LintCode 领扣

样例 1:

输入：1
输出：[7]

样例 2:

输入：2
输出：[8,4]

样例 3:

输入：3
输出：[8,1,10]

[题解]

考点：

• 随机数

题解：

1. [1,7] 的随机数， 减一-> [0,6] 的随机数，乘以 7 -> {0,7,14,21,28,35,42} 中的随机数
2. [1,7]的随机数 1+2 是[1,49]的随机数，且均匀生成 -> [0,48]的随机数 取出[0,39]区间 取到的概率是 1/49 除以 4-> [0,9]的随机数 加一->[1,10]的随机数

public class Solution extends SolBase{
    public  int rand10() {
        while(true){
           int rand49 = (rand7() - 1) * 7 + rand7() - 1;
            if(rand49 <= 39) {
                return rand49 / 4 + 1;
            }
        }
    }
}

更多语言代码参见：九章算法

[churchmice]

你这玩意说得有模有样，其实是错的吧
你带个乘法，乘完之后你觉得 0-42 的概率是一样的吗？你不觉得 0 的概率大了点吗？这样的水平还搞什么九章算法，赶紧关门吧


老老实实 rand7 两次，排列组合合计 49 种可能，随即取 10 种结果就好了

[lance6716]

@churchmice 你理解错了，乘法不是两个随机数在乘

[agegcn]

解法没问题。看成是 7 进制。2 次 rand7，有 49 种可能，取 40 种，因为 40 是 10 的倍数，丢弃剩下的 9 种可能

[alan0liang]

我很好奇这道题(或者说这种题) spj 是怎么做的……我给个 return rand7() 竟然就给 AC 了，但是 return 1 会 WA

[jeffdeng]

rand7()*10/7 行不行

[hakunamatata11]

更多算法真题讲解可以试听 7/12 上午 9：30 的九章算法班噢： https://www.jiuzhang.com/course/71/?utm_source=sc-v2ex-fks

[kinsou]

反手就是一个广告。

[Keyes]

@kinsou 哈哈哈哈看到这种先拉到最底下看看有没有推广再看正文就对了

推广就推广呗，非要整这些没用的