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 的大作中提到】
: 面试的一道问题
: 给定一种概率发生器，出1的概率是p,出0的概率是1-p
: 如果我们需要一个概率都是1/2的概率发生器，该怎么做？
: 如果是1/n的，怎么做？
: 1/2的做出来了
: 1/n的做着做着就乱了
: 求问
| U*******L
发帖数: 94 | 3 似乎只能用这种概率发生器来做，你这个还要判断加过滤。。。
貌似不大行？
【在 h*********3 的大作中提到】
: 用给定的发生器，连续发生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 的大作中提到】
: 面试的一道问题
: 给定一种概率发生器，出1的概率是p,出0的概率是1-p
: 如果我们需要一个概率都是1/2的概率发生器，该怎么做？
: 如果是1/n的，怎么做？
: 1/2的做出来了
: 1/n的做着做着就乱了
: 求问
| U*******L
发帖数: 94 | 5 这个和2楼的想法一样
但是会比2楼的快一些
我刚才证明了一下，貌似如果不用过滤或者条件判断的话是没办法从一个小数算出另一
个无理数的，纯用布尔逻辑的话。所以估计只能用这种办法了
多谢
【在 b**********r 的大作中提到】
: 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 的大作中提到】
: 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 的大作中提到】
: 面试的一道问题
: 给定一种概率发生器，出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 的大作中提到】
: for 1/2,
: p(1-p) = (1-p)p
|
|
