一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 810|回复: 16
收起左侧

分享一道G家昂赛题

[复制链接] |试试Instant~ |关注本帖
Griffith♂Guts 发表于 2016-11-20 02:27:00 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 博士 全职@Google - 猎头 - Onsite |Passfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
我感觉自己运气非常好,题目都不难。楼主碰到2位三哥面试官,都非常友善,所以大家别怕。
楼主自己不太看面经,因为很多题看到第二次就懒得做倦怠没激情了。但是刷题对我还是很有帮助的,毕竟转专业敲代码不熟。
. 鍥磋鎴戜滑@1point 3 acres
分享一道比较有意思的题目:. From 1point 3acres bbs
给一个fair coin,对任意正整数n,如何模拟出1/n的概率。follow up:简要证明,然后写这个程序。

由于楼主本身就是做概率方向的所以一会儿就想出来了,但是相信对大部分农友来说此题还是挺另类的:)

评分

1

查看全部评分

本帖被以下淘专辑推荐:

sqrl 发表于 2016-11-20 02:48:02 | 显示全部楼层
二进制? 字数字数
回复 支持 反对

使用道具 举报

kunge12345 发表于 2016-11-20 03:03:24 | 显示全部楼层
是利用conditional probability么?
回复 支持 反对

使用道具 举报

 楼主| Griffith♂Guts 发表于 2016-11-20 03:12:57 | 显示全部楼层
sqrl 发表于 2016-11-20 02:48
二进制? 字数字数

对                              
回复 支持 反对

使用道具 举报

 楼主| Griffith♂Guts 发表于 2016-11-20 03:13:25 | 显示全部楼层
kunge12345 发表于 2016-11-20 03:03
是利用conditional probability么?
. 1point 3acres 璁哄潧
对                        
回复 支持 反对

使用道具 举报

daniel_hl 发表于 2016-11-20 03:29:55 | 显示全部楼层
这样行吗,取一个数k = ceil(log2(n)),扔k次,把这k次的结果看成一个binary number,这个数小于等于n-1的概率是 n/(2^k),反复投掷知道这个数小于等于n-1为止,然后再看这个数是否等于0. 证明就是楼上说的条件概率吧
回复 支持 反对

使用道具 举报

 楼主| Griffith♂Guts 发表于 2016-11-20 03:34:33 | 显示全部楼层
daniel_hl 发表于 2016-11-20 03:29
这样行吗,取一个数k = ceil(log2(n)),扔k次,把这k次的结果看成一个binary number,这个数小于等于n-1的 ...

perfect!
回复 支持 反对

使用道具 举报

daniel_hl 发表于 2016-11-20 03:36:16 | 显示全部楼层

非常感谢分享!
回复 支持 反对

使用道具 举报

zhouyejoe 发表于 2016-11-20 11:46:13 | 显示全部楼层
daniel_hl 发表于 2016-11-20 03:29.鐣欏璁哄潧-涓浜-涓夊垎鍦
这样行吗,取一个数k = ceil(log2(n)),扔k次,把这k次的结果看成一个binary number,这个数小于等于n-1的 ...

可以详细解释一下吗?不是特别理解,概率学的太差了,谢谢。
回复 支持 反对

使用道具 举报

zhouyejoe 发表于 2016-11-20 11:46:21 | 显示全部楼层

可以详细解释一下吗?不是特别理解,概率学的太差了,谢谢。
回复 支持 反对

使用道具 举报

daniel_hl 发表于 2016-11-21 03:14:29 | 显示全部楼层
zhouyejoe 发表于 2016-11-20 11:46
可以详细解释一下吗?不是特别理解,概率学的太差了,谢谢。

如果投掷k次,把每次投掷的结果看作0或1(正或反),那么投k次的结果就可以用一个k位的二进制数表示,这样会得到2^k个数,而且得到每个数的概率是一样的。但是题目要求模拟1/n的概率,所以就要设法以均匀的概率产生n个数,那么产生其中一个数的概率就是1/n。

这个方法就是,选一个k使得2^k >= n。然后这样模拟1/n概率:
    1. 投掷k次,产生一个数m,范围是0~2^k - 1
    2. 如果0 =< m <= n - 1, 停止投掷,跳到3。否则跳回1
    3. m等于[0, n - 1]其中任意一个数的概率就是1/n.
回复 支持 反对

使用道具 举报

zhouyejoe 发表于 2016-11-21 04:04:06 | 显示全部楼层
daniel_hl 发表于 2016-11-21 03:14
如果投掷k次,把每次投掷的结果看作0或1(正或反),那么投k次的结果就可以用一个k位的二进制数表示,这 ...

非常感谢~
回复 支持 反对

使用道具 举报

sunnyroom 发表于 2016-11-22 14:26:13 | 显示全部楼层
daniel_hl 发表于 2016-11-21 03:14
如果投掷k次,把每次投掷的结果看作0或1(正或反),那么投k次的结果就可以用一个k位的二进制数表示,这 ...

我的概率就是渣。。。。
没看懂为什么这么算出来是1/n

落在[0, n - 1] 之间的概率是 n/2^k; 然后,怎么得出的1/n呢
求解释
回复 支持 反对

使用道具 举报

luffy_zc 发表于 2016-11-22 14:54:56 | 显示全部楼层
sunnyroom 发表于 2016-11-22 14:26
我的概率就是渣。。。。
没看懂为什么这么算出来是1/n

我也不太理解,但到利用条件概率是指说满足了落在[0,n-1]的条件之后,每个数的概率一样,所以投掷结果等于0的概率就是1/n了?
回复 支持 反对

使用道具 举报

weii 发表于 2016-11-22 16:12:48 | 显示全部楼层
sunnyroom 发表于 2016-11-22 14:26
我的概率就是渣。。。。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
没看懂为什么这么算出来是1/n

P(A=0 | A < n) = P(A = 0 and A < n)/P(A < n) =P(A = 0)/P(A < n) = (1/2^k)/(n/2^k) = 1/n 我的理解是这样,不一定要是0,任何在0和n-1直接的数都可以
回复 支持 反对

使用道具 举报

finalItw 发表于 2016-11-23 06:02:03 | 显示全部楼层
给楼上各位概率大神跪了!
回复 支持 反对

使用道具 举报

daniel_hl 发表于 2016-11-23 12:03:52 | 显示全部楼层
sunnyroom 发表于 2016-11-22 14:26
我的概率就是渣。。。。
没看懂为什么这么算出来是1/n

是这样的,因为投掷多轮直到结果落在[0, n - 1] 之间为止,所以得到的这个结果是[0, n - 1]中的某个数,在满足了这个条件之后,它是[0, n - 1]中任意一数的概率是1/n。

理论上证明就是15楼给出的。
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-9 06:22

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表