随机数生成问题

Question

随机数生成问题

javarandom

3

这个问题是在我的面试中被问到的。 random(0,1) 是一个随机生成整数0和1的函数。使用这个函数，你如何设计一个函数，以两个整数a和b作为输入，并生成包括a和b在内的随机整数。

我不知道如何解决这个问题。

- user973931

1

把提供的函数看作是生成随机位的工具。你会如何使用它来生成一个 n 位的随机数？ - Chris Nash

除了出现非零概率的a和b之外，随机整数的分布是否有任何特定限制？ - Neil

我没有问面试官这个问题，但他的意思是在a和b之间选择任何一个数字的概率应该是相等的。 - user973931

4个回答

0

我讨厌这种面试问题，因为有些答案可以满足它，但如果你使用它们，面试官会很生气。例如，

Call random, 
if you obtain 0, output a
if you obtain 1, output b

更为复杂的答案，也许是面试官想要的。

init(a,b){
  c = Max(a,b)
  d = log2(c) //so we know how much bits we need to cover both a and b
}

Random(){
 int r = 0;
 for(int i = 0; i< d; i++)
    r = (r<<1)| Random01();
 return r;
 }

通过连续调用子函数，您可以生成由0和1组成的随机字符串。

- UmNyobe

0

所以我们有randomBit()独立地以均匀随机的方式返回0或1，我们想要一个函数random(a, b)以均匀随机的方式返回范围内的值[a,b]。实际上，让我们将其范围设为[a, b)，因为半开放范围更容易处理且等效。事实上，很容易看出我们可以只考虑a == 0（和b > 0）的情况，即我们只想在范围内生成一个随机整数[0, b)。

让我们从其他地方建议的简单答案开始。（请原谅我使用c++语法，Java中的概念是相同的）

int random2n(int n) {
   int ret = n ? randomBit() + (random2n(n - 1) << 1) : 0;
}
int random(int b) {
    int n = ceil(log2(b)), v;
    while ((v = random2n(n)) >= b);
    return v;
}

也就是说，如果给定randomBit()，在范围[0, 2^n)内生成一个值很容易。因此，为了得到[0, b)范围内的值，我们重复生成[0, 2^ceil(log2(b))]范围内的值，直到得到正确范围内的值。很容易证明，这样随机选择的范围是[0, b)。

如前所述，对于这种方法，最坏情况下期望调用randomBit()的次数为(1 + 1/2 + 1/4 + ...) ceil(log2(b)) = 2 ceil(log2(b))。其中大部分调用都是浪费的，我们只需要log2(n)位熵，因此应尽可能接近该值。即使是聪明的实现也会尽早计算高位并在退出所需范围时立即退出，但在最坏情况下，期望调用randomBit()的次数仍然相同。

我们可以很容易地设计出一种更有效的方法（以调用randomBit()为单位）。假设我们想要在范围[0，b)内生成一个数字。通过一次调用randomBit()，我们应该能够将目标范围大致减半。实际上，如果b是偶数，我们可以这样做。如果b是奇数，我们将有一个（非常）小的机会需要“重新投掷”。考虑以下函数：

int random(int b) {
    if (b < 2) return 0;
    int mid = (b + 1) / 2, ret = b;
    while (ret == b) {
         ret = (randomBit() ? mid : 0) + random(mid);
    }
    return ret;
}

这个函数基本上使用每个随机位来选择所需范围的两半，然后在该半部分递归生成一个值。虽然函数相当简单，但对其进行分析要复杂一些。通过归纳法可以证明，这会在范围 [0, b) 中均匀随机生成一个值。此外，可以证明，在最坏情况下，这需要 ceil(log2(b)) + 2 次调用 randomBit()。当 randomBit() 很慢时，例如真正的随机生成器，这只会浪费恒定数量的调用，而不是像第一个解决方案那样线性浪费。

- Chris Hopman

0

function randomBetween(int a, int b){
int x = b-a;//assuming a is smaller than b
float rand = random();
return a+Math.ceil(rand*x);
}

- Raks

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- CommonMan · Accepted Answer

我们可以通过位运算轻松地实现这一点（例如，a=4 b=10）。

计算差值b-a（例如给定6）
现在计算ceil(log(b-a+1)(Base 2))，即表示a和b之间所有数字所需的位数。
现在为每个位调用random(0,1)。（例如，范围将在000-111之间）
重复步骤3，直到该数字（称为num）介于000到110之间（包括110），即我们只需要7个级别，因为b-a+1为7。因此，存在7种可能的状态a、a+1、a+2、... a+6，其中b等于a+6。
返回num+a。