Corman练习：随机（a，b）

Question

我不明白这个练习的答案，特别是为什么他们这样做

n = [log(b - a +1 )] ?!! 

我认为n = ceil(log2(b))

---

这是练习：

描述RANDOM（a，b）的实现，它只调用RANDOM（0,1）。

和答案：

1: n = [lg(b − a + 1)] 
2: Initialize an array A of length n
3: while true do
4:    for i = 1 to n do
5:       A[i] = RANDOM(0, 1)
6:    end for
7:    if A holds the binary representation of one of the numbers in a through
b     then
8:          return number represented by A
9:    end if
10: end while

链接页面：http://sites.math.rutgers.edu/~ajl213/CLRS/CLRS.html

Answer 1

它支持十进制方法。当你想要一个从(0,1)到(a,b)的数字时，你需要乘以(b-a)中的数字然后再加上a。这意味着如果我们在x中有一个数字(a,b)，我们将有(b-a)*x + a将0映射到a和1到b。

由于加a是所有数字的线性移位，因此这里忽略了这种转变。因此，最大的值是b-a，而密切的[a,b]之间的值的数量是b-a+1。