0

我一直在阅读 CLRS 并遇到了编写一个过程 Rand(a,b) 的问题，该过程使用 Rand(0,1) 以 50% 的概率生成 0 或 1 的过程 Rand(0,1) 随机均匀地在 a 到 b 之间生成一个随机数.

我想到了以下解决方案，时间为 O(b)：

int Rand_a_b(int a,int b)
{
    int i,k=0;
    for(i=0;i<b-a;i++)
    {
         k+=Rand(0,1);
    }
    return a+k;
}

请为此提出更好的方法。

4

3 回答 3

4

如果范围内不同数字的数量不是 2 的幂，则必须小心，因为任何总是需要 N 个数字的过程只能看到 2^N 个不同的可能性，并且不可能分布 2^N 个不同的如果该范围不具有两种不同可能性的幂，则该范围内的可能性是均匀的。

在 a..b 之间生成数字时的一种方法是使用 k 个随机数作为 k 位数字中的单个位，以生成 a..a+2^k-1 范围内的数字，其中选择 k 使得 a +2^k-1 >= b。如果事实证明您生成的随机数超出范围，请从头开始。这通过采用可变数量的随机位来避免上述问题，具体取决于您是否以及多久生成超出范围的内容并且必须重新开始。

于 2014-02-16T12:36:02.103 回答
1

这是一个算法：计算 a 和 b 之间的差异：k = abs(a-b)并开始进行二进制搜索，如下所示：

保留一个数字n = 0。翻转你的硬币 - Rand(0,1)，如果结果是 1 添加k/2到您的nelse 中，则不添加任何内容。而不是再次翻转它k/4并重复直到k/i为0。

于 2014-02-16T12:25:23.610 回答
1

这里应该在 log(n) 中。（我没有检查边界，它没有经过测试！） 你不能让它更快 - 如果你一次只发出一个比特，你至少需要 log(ba) 轮次间隔。

function Rand_a_b(int a, int b) {
   if (a == b) return a;
   int middle = (b-a)/2;
   if (Rand(0,1)) {
      return Rand_a_b(middle + 1, b);
   } else {
      return Rand_a_b(a, middle);
   }
}
于 2014-02-16T12:26:01.550 回答