用一个骰子生成1到7的随机数?

  数学 概率论    浏览次数:2380        分享
5

如何用一个骰子等概率地生成1到7的随机数?

骰子就是正常的6面的骰子,扔到每面的概率都是1/6。


一道面试题,当场跪,完全没有思路。

谢谢各位!


 

信春哥   2017-09-18 12:36



   5个回答 
19

将一个筛子扔两次可以得到36种组合,每五种组合代表一个数字,剩下的一种表示重扔。


第一步:

将这个筛子扔两次,假设第一次扔的时候得到a,第二次是b,表示为(a, b)。


第二步:

1: (1, 1), (1, 2), (1, 3), (1, 4), (1, 5)

2: (1, 6), (2, 1), (2, 2), (2, 3), (2, 4)

3: (2, 5), (2, 6), (3, 1), (3, 2), (3, 3)

4: (3, 4), (3, 5), (3, 6), (4, 1), (4, 2)

5: (4, 3), (4, 4), (4, 5), (4, 6), (5, 1)

6: (5, 2), (5, 3), (5, 4), (5, 5), (5, 6)

7: (6, 1), (6, 2), (6, 3), (6, 4), (6, 5)

重复第一步: (6, 6)

SofaSofa数据科学社区DS面试题库 DS面经

sasa   2017-09-20 02:45

难受啊,上个月有个电面就因为这个题目没做出来挂掉了,早看到这个就好了 - robin_he   2019-05-07 14:27
8

扔到奇数,记为0

扔到偶数,记为1

连续扔三次,就会得到一个0到7的二进制数。比如010就是3,100就是5。

如果最终得到0,就重新再扔三次。

如此反复,直到得到非0的数。

这个肯定是生成1到7等概率的随机数。

SofaSofa数据科学社区DS面试题库 DS面经

雷猴   2017-09-20 12:08

8

根据sasa的答案,想到一个随机数生成效率的问题。

sasa方法中扔2次骰子也只有35/36的概率可以生成1个随机数。扔一次可得0.486个随机数。

如果扔骰子的时间代价大,需要注意生成随机数的效率,可以扩展下算法。比如扔骰子三次,可以把一个三维空间均匀分为216份,编号为1-216,然后再把这216份编为49组,对应两个1-7的随机数。比如{1,2,3,4}为第一组,对应随机数{1,1};{5,6,7,8}为第二组,对应随机数{1,2};最后剩下20份{197,...,216}表示无效。扔一次骰子可得随机数个数是(216-20)/216*2/3=0.605。

以此类推可以得到接近6/7的生成效率。

——————-

扔k次生成k位6进制数$x$,把这个数换为一个n位7进制数$y$。第n位在[0,6]的分布并不均匀,比如0会多于6,需要去掉。这样可表示n-1位7进制数,变换为n-1个均匀分布$U([0,6])$随机数。

SofaSofa数据科学社区DS面试题库 DS面经

Zealing   2018-05-01 13:45

如果扔四次骰子,生成三个1-7的随机数,会不会效率更高?如果是扔$k+1$次骰子,生成$k$个1~7的随机数,那当$k$非常大的时候,效率是不是就接近100%了? - 稻草人lyd   2018-11-07 15:22
当k无穷大时,扔一次最多只能生成6/7个1-7的随机数,不会接近100%。 - Zealing   2018-11-07 18:20
扔k次生成k位6进制数,把这个数可以换为一个k-1位7进制数吧? - 稻草人lyd   2018-11-09 13:35
3
扔两回骰子,第一次的数字表示范围改为0~5,将第一次的结果乘6加上第二次的,可以得到1~36共36个等概率的数字,舍弃36,只保留1~35这35个数,每5个表示一个结果,例如,1~5表示1,31~35表示7.即可得到等概率产生随机数7的函数SofaSofa数据科学社区DS面试题库 DS面经

南南   2019-05-08 11:58

-4

扔到1-5的数,就保留。

扔到6,就重扔,偶数的话就是6,奇数的话就是7。

SofaSofa数据科学社区DS面试题库 DS面经

ljljlj   2017-09-19 22:31

这个好像不是等概率的 - 信春哥   2017-09-19 23:18
得到6和7的概率只有1/12,不是1/7 - WinJ   2017-09-20 03:16


  相关主题

今天明天都下雨的概率   1回答

一个骰子平均扔多少回才能把六个数字都扔出来至少一次   2回答

对于独立正态变量X, Y ~ N(0,1),X+Y和X-Y是否独立?   2回答

什么是Jensen不等式?有什么直观的解释?   2回答

证明马尔可夫不等式   1回答

超几何概率问题   1回答

柯西分布没有数学期望   1回答

指数分布、几何分布、泊松分的联系是什么?   1回答

蓄水池采样的证明   1回答

为什么p value是服从[0, 1]均匀分布的?   2回答

Fisher Information的统计意义是什么?   1回答

指数家族有哪些常见的概率分布?   2回答



回答问题时需要注意什么?

我们谢绝在回答前讲“生动”的故事。

我们谢绝“这么简单,你自己想”、“书上有的,你认真看”这类的回答;如果你认为对方的提问方式或者内容不妥,你可以直接忽略该问题,不用进行任何作答,甚至可以对该问题投反对票。

我们谢绝答非所问。

我们谢绝自己不会、硬要回答。

我们感激每一个用户在编写答案时的努力与付出!