write a function to returns 0 with probability p?

a function f() returns 0 or 1 with 0.5 probability each.

开发者_StackOverflow中文版

Write a function g() that returns 0 with a probability of p..??

Assume p is given and lies between 0 and 1.

---

If you had access to a (pseudo-) random number generator you could generate a random number between 0 and 1. If that number is below p, return 0, otherwise return 1. You didn't make it clear in your question, but I will assume the only access to a random source you have is to call f() to get one bit at a time.

Consider the binary representation of p, for example: 0.011010010110... Similarly call f() repeatedly generating an unlimited length sequence of random binary digits x: 0.0110110010101...

As soon as you are sure that x is above or below p, you are done. You only need to call f as many times as necessary to be sure of the result.

p=0.011010...
x=0.011011...
         ^
         x>p: Stop and return 1.

I assume this is homework, so I won't give full source code.