U*******L 发帖数: 94 | 1 面试的一道问题
给定一种概率发生器,出1的概率是p,出0的概率是1-p
如果我们需要一个概率都是1/2的概率发生器,该怎么做?
如果是1/n的,怎么做?
1/2的做出来了
1/n的做着做着就乱了
求问 | h*********3 发帖数: 111 | 2 用给定的发生器,连续发生n次,
如果是 100...00, 输出0
如果是 010...00, 001...00, ... , 000...10,000...01, 输出1
其他情况则简单抛弃,不输出结果。
这样 0 的概率是1/n
【在 U*******L 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 面试的一道问题 : 给定一种概率发生器,出1的概率是p,出0的概率是1-p : 如果我们需要一个概率都是1/2的概率发生器,该怎么做? : 如果是1/n的,怎么做? : 1/2的做出来了 : 1/n的做着做着就乱了 : 求问
| U*******L 发帖数: 94 | 3 似乎只能用这种概率发生器来做,你这个还要判断加过滤。。。
貌似不大行?
【在 h*********3 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 用给定的发生器,连续发生n次, : 如果是 100...00, 输出0 : 如果是 010...00, 001...00, ... , 000...10,000...01, 输出1 : 其他情况则简单抛弃,不输出结果。 : 这样 0 的概率是1/n
| b**********r 发帖数: 91 | 4 let G2 be the 1/2 generator from the first question, that is, G2 generates
0 and 1 with the equal probability
then let n is between 2^k <= n < 2^(k+1), the new generator will produce
value from {0 to n-1} with equal probability with the following process:
(1) use G2 to generate k 0 and 1 sequence and use it as binary
representation to calculate the decimal value, denote as v,
(2) if v >= n goto (1), otherwise return v, then v is equally distributed
in {0, 1, ..., n-1}
【在 U*******L 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 面试的一道问题 : 给定一种概率发生器,出1的概率是p,出0的概率是1-p : 如果我们需要一个概率都是1/2的概率发生器,该怎么做? : 如果是1/n的,怎么做? : 1/2的做出来了 : 1/n的做着做着就乱了 : 求问
| U*******L 发帖数: 94 | 5 这个和2楼的想法一样
但是会比2楼的快一些
我刚才证明了一下,貌似如果不用过滤或者条件判断的话是没办法从一个小数算出另一
个无理数的,纯用布尔逻辑的话。所以估计只能用这种办法了
多谢
【在 b**********r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : let G2 be the 1/2 generator from the first question, that is, G2 generates : 0 and 1 with the equal probability : then let n is between 2^k <= n < 2^(k+1), the new generator will produce : value from {0 to n-1} with equal probability with the following process: : (1) use G2 to generate k 0 and 1 sequence and use it as binary : representation to calculate the decimal value, denote as v, : (2) if v >= n goto (1), otherwise return v, then v is equally distributed : in {0, 1, ..., n-1}
| d*******l 发帖数: 338 | 6 不错的想法,以前就听人说过不限制次数的话,能生成1/2就能生成1/x,哪怕x是无理
数,大概想法就是确定每个二进制位
【在 b**********r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : let G2 be the 1/2 generator from the first question, that is, G2 generates : 0 and 1 with the equal probability : then let n is between 2^k <= n < 2^(k+1), the new generator will produce : value from {0 to n-1} with equal probability with the following process: : (1) use G2 to generate k 0 and 1 sequence and use it as binary : representation to calculate the decimal value, denote as v, : (2) if v >= n goto (1), otherwise return v, then v is equally distributed : in {0, 1, ..., n-1}
| l******c 发帖数: 2555 | 7 for 1/2,
p(1-p) = (1-p)p
【在 U*******L 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 面试的一道问题 : 给定一种概率发生器,出1的概率是p,出0的概率是1-p : 如果我们需要一个概率都是1/2的概率发生器,该怎么做? : 如果是1/n的,怎么做? : 1/2的做出来了 : 1/n的做着做着就乱了 : 求问
| z****c 发帖数: 602 | 8 嗯,可以用杨辉三角的系数来提高效率。当n第一次在杨辉三角形出现的地方n*p^x*(1-
p)^y,对于所有的x个0,y个1的permutation输出对应的1~n。另外利用三角形的对称性y
个0,x个1的permutation也可输出。剩下的情况抛弃。 | Z**********4 发帖数: 528 | | Z**********4 发帖数: 528 | 10 把两个概率发生器的输出异或 得出的结果作为输出
【在 l******c 的大作中提到】![](/moin_static193/solenoid/img/up.png) : for 1/2, : p(1-p) = (1-p)p
|
|