我不知道如何解决这个问题。
我讨厌这种面试问题,因为有些答案可以满足它,但如果你使用它们,面试官会很生气。例如,
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组成的随机字符串。
randomBit()
独立地以均匀随机的方式返回0或1,我们想要一个函数random(a, b)
以均匀随机的方式返回范围内的值[a,b]
。实际上,让我们将其范围设为[a, b)
,因为半开放范围更容易处理且等效。事实上,很容易看出我们可以只考虑a == 0
(和b > 0
)的情况,即我们只想在范围内生成一个随机整数[0, b)
。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()
很慢时,例如真正的随机生成器,这只会浪费恒定数量的调用,而不是像第一个解决方案那样线性浪费。
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);
}