Jump to content


Welcome to BrainDen.com - Brain Teasers Forum

Welcome to BrainDen.com - Brain Teasers Forum. Like most online communities you must register to post in our community, but don't worry this is a simple free process. To be a part of BrainDen Forums you may create a new account or sign in if you already have an account.
As a member you could start new topics, reply to others, subscribe to topics/forums to get automatic updates, get your own profile and make new friends.

Of course, you can also enjoy our collection of amazing optical illusions and cool math games.

If you like our site, you may support us by simply clicking Google "+1" or Facebook "Like" buttons at the top.
If you have a website, we would appreciate a little link to BrainDen.

Thanks and enjoy the Den :-)
Guest Message by DevFuse
 

Photo
- - - - -

Random Number API - Part 1...


Best Answer witzar, 06 August 2013 - 02:47 PM

Spoiler for

Go to the full post


  • Please log in to reply
11 replies to this topic

#1 Anza Power

Anza Power

    Junior Member

  • Members
  • PipPip
  • 80 posts

Posted 05 August 2013 - 11:08 PM

You are a programmer, you want to make a function rand(n) that takes an integer n>1 and returns a random integer in the range {1...n} with uniform probability.

 

At you disposal is a binary random number generator which generates 0's and 1's with equal probability (a fair coin) you can use it as many times as you want.

 

Can you do this and guarantee your program won't run forever?


  • 0

#2 James33

James33

    Junior Member

  • Members
  • PipPip
  • 38 posts

Posted 06 August 2013 - 12:59 AM

By not run forever, do you mean that we must be able to fix a time at which the algorithm will certainly have terminated by? If you mean that it just has to end at some point then

 

Spoiler for


  • 0

#3 phil1882

phil1882

    Senior Member

  • Members
  • PipPipPipPip
  • 550 posts

Posted 06 August 2013 - 05:01 AM

Spoiler for how about this

  • 0

#4 gavinksong

gavinksong

    Advanced Member

  • Members
  • PipPipPip
  • 222 posts

Posted 06 August 2013 - 09:30 AM

By not run forever, do you mean that we must be able to fix a time at which the algorithm will certainly have terminated by? If you mean that it just has to end at some point then

 

Spoiler for

 

Spoiler for small correction


Edited by gavinksong, 06 August 2013 - 09:32 AM.

  • 0

#5 witzar

witzar

    Advanced Member

  • Members
  • PipPipPip
  • 233 posts

Posted 06 August 2013 - 02:47 PM   Best Answer

Spoiler for


  • 0

#6 James33

James33

    Junior Member

  • Members
  • PipPip
  • 38 posts

Posted 06 August 2013 - 02:53 PM

Spoiler for

 

I don't think that the logic there quite works. Certain results could be ignored (conditional on what has been generated) to make everything divisible by 3.


  • 0

#7 witzar

witzar

    Advanced Member

  • Members
  • PipPipPip
  • 233 posts

Posted 06 August 2013 - 03:38 PM

Spoiler for second attempt


  • 0

#8 BobbyGo

BobbyGo

    Advanced Member

  • Members
  • PipPipPip
  • 131 posts
  • Gender:Male

Posted 06 August 2013 - 05:11 PM

By not run forever, do you mean that we must be able to fix a time at which the algorithm will certainly have terminated by? If you mean that it just has to end at some point then

 

Spoiler for

 

 

Spoiler for

  • 0

#9 James33

James33

    Junior Member

  • Members
  • PipPip
  • 38 posts

Posted 06 August 2013 - 06:23 PM

 

By not run forever, do you mean that we must be able to fix a time at which the algorithm will certainly have terminated by? If you mean that it just has to end at some point then

 

Spoiler for

 

 

Spoiler for

 

True, I was just giving an outline of what I would do because I don't think it is what the OP as it has no upper bound on time taken.


  • 0

#10 Anza Power

Anza Power

    Junior Member

  • Members
  • PipPip
  • 80 posts

Posted 06 August 2013 - 06:50 PM

 

Spoiler for

 

I don't think that the logic there quite works. Certain results could be ignored (conditional on what has been generated) to make everything divisible by 3.

 

Actually it is correct.

 

Let's assume the upper bound is 8 calls, but if your algorithm sees 10001 then it returns 3, then we say that all 2^3 = 8 sequences of the form 10001xxx result in 3.

 

Congratulations to witzar...


  • 0




0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users