All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Random Number Generator (Posted on 2004-06-08)
A particular random number generator returns positive integer n with probability 1/(2^n). (ie '1' with probability 1/2, '2' with probability 1/4, '3' with probability 1/8, etc.)

Using this random number generator, write an algorithm which chooses a random integer from 1 to 37 with equal probability.

 See The Solution Submitted by Brian Smith Rating: 2.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 My algorithm | Comment 11 of 26 |

This is my answer to the problem written in UBASIC

Lines 11-15, 199-205, 1005 are statistics lines.
Lines 1000-1050 simulate the random number generator given in the problem.
1,000,000 numbers 1-37 used 4,378,259 random number calls.

10   randomize
11   dim STAT(38)
12   R_count=0
15   for TEST=1 to 1000000
20   R=fnRND
30   if R=2 then 20
40   if (R@4)=1 then V=1:goto 100
50   if (R@4)=0 then V=33:goto 130
60   if (R@4)=2 then V=37:goto 150
70   goto 20
100   R=fnRND
101   if R=1 then V=V+16:goto 110
102   if R=2 then V=V+8:goto 120
103   if R=3 then V=V+4:goto 130
104   if R=4 then V=V+2:goto 140
105   if R=5 then V=V+1
106   goto 150
110   R=fnRND
111   if R=1 then V=V+8:goto 120
112   if R=2 then V=V+4:goto 130
113   if R=3 then V=V+2:goto 140
114   if R=4 then V=V+1
115   goto 150
120   R=fnRND
121   if R=1 then V=V+4:goto 130
122   if R=2 then V=V+2:goto 140
123   if R=3 then V=V+1
124   goto 150
130   R=fnRND
131   if R=1 then V=V+2:goto 140
132   if R=2 then V=V+1
133   goto 150
140   R=fnRND
141   if R=1 then V=V+1
150   ' print V;
199   STAT(V)+=1
200   next TEST
201   print
202   for STATS=1 to 37
203   print STATS;STAT(STATS),
204   next STATS
205   print:print "Random Calls";R_count
999   end
1000   fnRND
1005   R_count=R_count+1
1010   X=1
1020   if rnd>0.5 then 1050
1030   X=X+1
1040   goto 1020
1050   return(X)

 Posted by Brian Smith on 2004-06-14 18:59:16

 Search: Search body:
Forums (0)