给定一个公平硬币的函数，为有偏差的硬币编写一个函数？

Question

我在进行一些审查时遇到了这个报道的面试问题（以下引用是我发现的有关该问题的所有信息）：

给定一个公平硬币的函数， 为有偏差的硬币编写一个函数 返回正面 1/n 次（n 是 参数）

乍一看我写道：

int biased_coin(n) { //0=Tails, 1=Heads
  int sum = 0;

  if(n==1)
    return 1;

  for(int i=0;i<n;i++) {
    sum += unbiased(); //unbiased returns 0 50% of the time and 1 50% of the time
  }

  if(sum == 1)
    return 1;

  return 0;
}

但这显然行不通。例如，对于 n=4，它确实有效：因为 4 次抛掷得到单个正面的概率是 4/(2^4)=1/4。但对于 n=3，3/(2^3)!=1/3。

假设您不能使用随机数生成器，那么实现此类操作的正确方法是什么？

Answer 1

由于 N 的大多数值不是 2 的幂，因此严格来说不可能保证任意次数的硬币抛掷的概率为 1/N。相反，您必须满足于接近您所需精度的 1/N 的结果。但是，嘿，这对你来说无论如何都是抛硬币。

为自己绘制一棵决策树，其根部有 2 个分支（标记为 H 和 T），然后每个节点有 2 个分支（也标记为 H 和 T），直到达到足够的叶节点来满足您的准确性要求。用您想要的值标记叶子的右侧（为您）部分，例如，如果 N=3，则为 1,2,3。然后，每个叶子定义一条从根开始的路由，例如 HHHTTHH（或其他）。这些定义了导致“3”的投掷顺序。

我将把编码留给你。

Answer 2

假设：

int fairCoinToss();

正面返回 1，反面返回 2，写入：

int biasedCoinToss(int n);

其中正面 (1) 将出现 1/n 的时间，这应该有效：

int biasedCoinToss(int n) {
  if (n == 1) {
    return 1; // 1/1 = 1 = always heads
  } else if (n == 2) {
    return fairCoinToss(); // 1/2 = 50% = fair coint oss
  }
  int r = random_number(n);
  return r == 0 ? 1 : 0;
}

其中 random_number(n) 生成一个公平的随机整数 i，使得<代码> 0 <= i < n。因此，random_number(3) 为 0、1 或 2。假设均匀分布，则 1/3 的时间将出现值 0。

当然，我们不能使用本机随机数生成器，但无论如何我们可以创建一个。 fairCoinToss() 随机生成 1 或 0。可以组合多次抛硬币来生成更大的数字。例如：

fairCoinToss() << 1 | fairCoinToss()

将生成：

00 = 0
01 = 1
10 = 2
11 = 3

根据定义，它是 0 到 3 之间的随机数 (n = 4)。

如果 n 是 2 的幂就可以，但也不一定。然而，这很容易满足。假设 n = 5。我们最多可以生成一个从 0 到 7 的随机数。如果您“重新滚动”5、6 或 7，直到获得 0 到 4 范围内的数字，那么您就（非确定性地）构造了一个0到4之间均匀分布的随机数，满足要求。

代码看起来像这样：

int random_number(int n) {
  int ret;
  do {
    int limit = 2;
    ret = fairCoinToss();
    while (limit < n) {
      ret <<= 1;
      ret |= fairCoinToss();
      limit <<= 1;
    }
  } while (ret >= n);
  return ret;
}

Answer 3

这个怎么样：
1.找出n的二进制表示
2. 翻转公平硬币logn次。每一次翻转对应一个位。
3. 如果翻转的结果大于n的值，则重新滚动。
4. 如果结果为0，则返回正面。
5. 否则，返回尾部。