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

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

已注册用户请登录

这是一个创建于 1928 天前的主题，其中的信息可能已经有所发展或是发生改变。

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

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

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

 在线评测地址：LintCode 领扣
 样例 1:
 输入：1 输出：[7] 
 样例 2:
 输入：2 输出：[8,4] 
 样例 3:
 输入：3 输出：[8,1,10] 
 [题解]
 考点：
  随机数
 
 题解：
  [1,7] 的随机数， 减一-> [0,6] 的随机数，乘以 7 -> {0,7,14,21,28,35,42} 中的随机数
 [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; } } } } 
 更多语言代码参见：九章算法

  
  
 随机
 rand7
 rand10
 样例
8 条回复    2020-07-03 17:36:59 +08:00 
           1
 
 churchmice   
   2020-07-03 10:07:03 +08:00 via Android 
 你这玩意说得有模有样，其实是错的吧
你带个乘法，乘完之后你觉得 0-42 的概率是一样的吗？你不觉得 0 的概率大了点吗？这样的水平还搞什么九章算法，赶紧关门吧


老老实实 rand7 两次，排列组合合计 49 种可能，随即取 10 种结果就好了
  
 
 
           2
 
 lance6716   
   2020-07-03 10:17:37 +08:00 via Android 
 @churchmice 你理解错了，乘法不是两个随机数在乘
  
 
 
           3
 
 agegcn   
   2020-07-03 10:44:00 +08:00 
 解法没问题。看成是 7 进制。2 次 rand7，有 49 种可能，取 40 种，因为 40 是 10 的倍数，丢弃剩下的 9 种可能
  
 
 
           4
 
 alan0liang   
   2020-07-03 11:51:09 +08:00 via Android 
 我很好奇这道题(或者说这种题) spj 是怎么做的……我给个 return rand7() 竟然就给 AC 了，但是 return 1 会 WA
  
 
 
           5
 
 jeffdeng   
   2020-07-03 15:31:26 +08:00 
 rand7()*10/7 行不行
  
 
 
     
          6
 
 hakunamatata11   OP
   2020-07-03 17:32:11 +08:00 
 更多算法真题讲解可以试听 7/12 上午 9：30 的九章算法班噢： https://www.jiuzhang.com/course/71/?utm_source=sc-v2ex-fks
    
           7
 
 zkname   
   2020-07-03 17:34:45 +08:00 
 反手就是一个广告。
  
 
 
           8
 
 Keyes   
   2020-07-03 17:36:59 +08:00 via iPhone 
 @kinsou 哈哈哈哈看到这种先拉到最底下看看有没有推广再看正文就对了

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