You are provided with a function f() which returns either 0 or 1 with probability 1/2. Using this to construct a function f1() which returns 0 with probability 1/3 and 1 with probability 2/3.
int f1(){
while( true ){
if( f()==1 ) return 1;
if( f()==1 ) return 0;
}
}
int f1()
{
while( true)
{
int x = f();
int y = f();
if(x==1) return 1;
if(y==1) return 0;
}
}
int f1()
{
int x = 2;
while(x ==2)
{
x=f() + f();
}
return x;
}
4 comments:
It would be great if you could show the correctness of the algo.
I am not able to do that......
Or at least explain it.....
Or may be some link or reference material.
May be you have the policy of just writing the code :-)
Manoj
the last one is easy to define...
what it does is...
in the while loop it will generate x
so x can take values 0,1,2 with prob.
x | probability
===============
0 | 1/4
1 | 1/2
2 | 1/4
since x = f()+f()...
now we want o/p as only 0 or 1...
so when ever i get 2 i loop around..
so 2 case we are not taking...
so it will now become
x = 0 when both f()returns 0
x = 1 when one of them returns 1.
(0,0) --- x = 0
(1,0) (0,1) --- x = 1
So function f1 returns x=0 with 1/3 rd probability. and x = 1 with 2/3...
First two i dont know...i got it from one of my friends..
ok....
then let me try the first one
actually there is no difference between the first and the second....
int f1(){
....while( true )
....{
........if( f()==1 ) return 1;
........if( f()==1 ) return 0;
....}
}
The code only returns 0 and 1
The probabilities are
P(1) = P( f() == 1 ) = 1/2
P(0) = P( f() == 0 and next f() == 1)= 1/2*1/2 = 1/4
but what if both f() = 1
Then we dont output anything and in the next loop of while again
P(0)=1/4
and P(1) = 1/2
Given this as the all which can occour....the total probability is
P(total) = 1/2+1/4 = 3/4
ooopssss but the sum of all the probability should be = 1
(it look good then )
So multiply all the probabilities by 4/3
So P(1) = 1/2*4/3 = 2/3
and P(0) = 1/2*4/3 = 1/3
I dont know if the fact of multiplying the probabilities is absolutely right or not..... but it seems logical here
All the solutions seem correct.
Deduce from truth table:
for 1st two solns...
f() can give either 1 or 0
The possible combinations are:
1st f()...2nd f()....- result
0..........0........- repeat loop
0..........1........- return 0
1..........0........- return 1
1..........1........- return 1
try doing the same with 3rd soln...too.
Post a Comment