求问 G家一道跟概率相关的题

G 家onsite 遇到一个题

从m 个人里面选一个（0-m-1），没有 Random.nextInt() 函数，只有一个硬币（coinFace(), return 1 or 0)，如何选出唯一的candidate，实现代码，返回这个人的idx。要求每个人被选中的概率是1/m。

我的想法是如果m 是2 的次方数， 每次选上一次一半的人， 选多了或选少了，重选；直到最后只剩2个人选一个。
没有想到solid 的证明方法。。  
如果m 不是2 的次方数， 没想到怎么解决。。。

不知道大家有什么好的方法吗？ 谢谢。

抛n次，保证2的n次方大于m，抛的次序看成二进制数，如果在1-m之间返回这个数，否则重新抛n次。

把m想成是二进制 每一位都可以flip

def shit(m):
   f=ceiling(log(m,2))-1
   s=0
   for i = (0:f)
       s = s +  2^i * coinFace()
   if s <= m:
       return s
   else:
       return shit(m)
#assume m >= 1
#assume coinFace() is not a pseudo stuff

楼上的大家的思路应该是正确的
可以这样想 每次我们最后选定的那个数 其实是给定了个condition 就是在当前范围里 我们才会选
比如 0->4
这5个数，bit组合有8种，但有3种是需要被drop掉的，prob = (1/8)/(5/8) = 1/5
不知道我这样理解对不对~

在最坏情况下浪费的情况还是较大的。连续三次都要扔掉的概率是0.5^3仍然有12.5%

也可以考虑伪随机的构造：假设33是要求的数
先用硬币抛若干次得到一个seed，一个m，一个c。
第一次 f(1) = (seed * m + c) % 33
第二次 f(2) = (f(1) * m + c) % 33
...