I don't understand the answer of this exercise , especially why they take
n = [log(b - a +1 )] ?!!
I think n = ceil(log2(b))
here is the exercices :
Describe an implementation of RANDOM(a, b) that only makes calls to RANDOM (0, 1) .
and the answer :
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
link of page : http://sites.math.rutgers.edu/~ajl213/CLRS/CLRS.html
Thanks.
Aucun commentaire:
Enregistrer un commentaire