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

Home > Algorithms
Random Number Generator (Posted on 2004-06-08) Difficulty: 3 of 5
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
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (2)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information