1

假设我有一个返回随机位的函数，是否可以编写一个在一定范围内统一生成随机数并始终终止的函数？

我知道如何做到这一点，以便它应该（并且可能会）终止。我只是想知道是否有可能编写一个保证终止（并且它不必特别有效。它会有什么复杂性？

这是不总是终止版本的代码

int random(int n)
{
  while(true)
  {
    int r = 0;
    for (int i = 0; i < ceil(log(n)); i++)
    {
      r = r<<1;
      r = r|getRandomBit();
    }

    if(r<n)
    {
      return r;
    }
  }
}
4

2 回答 2

2

我认为这会起作用：

假设您要生成范围内的数字[a,b]

使用二进制基数生成r范围内的分数。[0,1}这意味着使用您的随机函数生成许多表格0.x1x2x3....，其中每个表格x都是 0 或 1。

[0,b-a]一旦你有了它，你可以通过计算轻松地生成范围内的数字ceil(r*(b-a))，然后简单地添加a以获取范围内的数字[a,b]

于 2012-11-30T18:54:54.890 回答
1

如果范围的大小不是 2 的幂，则您无法获得完全均匀的分布，除非通过相当于拒绝抽样的方式。但是，您可以通过从大范围中采样一次，然后将较小的范围划分为该范围来尽可能接近均匀。

例如，虽然您无法在 1 到 10 之间进行均匀采样，但您可以通过选择 10 个随机位轻松地在 1 到 1024 之间进行采样，并找出某种方法将其公平地划分为 10 个大小大致相同的间隔。

选择额外的位具有将您在选择中必须看到的最大误差（来自真正的均匀性）减半的效果......因此，当您选择更多位时，误差会呈指数下降。

于 2012-11-30T21:13:03.677 回答