在旧的面试技巧上寻找新想法

Question

原来的问题是：

描述一种算法来输出掷骰子(从1到6的随机数)，给定一个输出抛硬币的函数(从1到2的随机数)。每种可能的结果都应该具有同等的可能性。

这个问题最受欢迎的答案是：

将硬币翻转三次，并将这三个硬币翻转作为三位数的位。如果数字在1到6的范围内，则输出数字。否则，请重复。

我的问题是：

大多数关于Stack Overflow的讨论都是以上述方式进行的。我还在互联网上搜索过，发现有许多其他类型的答案，但他们并没有明确地挖掘出来。有没有人能分享一下关于这个问题的一两个不同的想法？

Answer 1

如果你只是想要其他的选择，不一定是好的，那么这个怎么样：

1. 为每个可能的输出值抛硬币。
2. 如果有一个或多个头部，则丢弃所有可能得到尾部的值。
3. 如果只剩下一个值，则停止。否则转到1.

我怀疑它将会有比你所描述的方法更高的投掷硬币的预期数量，并且实际上没有任何优势。

一般来说，我假设这就是为什么没有太多关于使用随机数的其他可能方法的原因。他们就是没那么好。

Answer 2

对“抛3次，丢弃If110或111”算法有一个小的改进。丢弃110或111是浪费的，因为你正在浪费你可以重复使用的一个非常好的熵。在弹出其中一个值之后，您只需抛出两次，并从映射{110->tails，111->head}中获得第三个抛出的值。110和111的概率是相等的，因此您不会以这种方式引入任何偏差。

在伪代码中：

bit0 = toss()
while True:
   bit1 = toss()
   bit2 = toss()
   if bit1,bit2,bit3 give i such that 0<=i<=5 then 
      return i+1
   else
      bit0 = bit3 // the reuse happens here

这里的预计抛出次数是1+2* expected_number_of_loop_executions = 1+2*8/6 = 11/3

Answer 3

1. 翻转5枚硬币。如果它们都是正面或反面，你的答案是1。如果只有一个正面或一条尾部，则继续下一步。如果有多个头和多个尾巴，请重复此步骤(包括重新翻转硬币)。
2. 翻转4枚硬币。如果它们都是正面或反面，你的答案是2。如果只有一个正面或一条尾部，则继续下一步。如果有两个正面和两个反面，重复这一步(包括重新翻转硬币)。
3. 翻转3个硬币。如果它们都是正面或反面，你的答案是3。否则，继续下一步
4. 翻转2硬币。如果它们都是正面，你的答案是4。如果它们都是反面，重复这一步(包括重新翻盖硬币)。否则，继续下一步。
5. 掷硬币1。如果是正面，你的答案是5。如果是反面，你的答案是6。