c - 我创建过程 Rand(a,b) 的方法的更好解决方案，使用过程 Rand(0,1)

Question

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

我想到了下面的解决方案，时间是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;
}

请为此提出更好的方法。

Answer 1

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

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