RandonInt()

Go down

RandonInt()

Post  SwitchCase on Thu Sep 18, 2008 12:58 am

A nested function call is when inside a function, you call the same function.\

We will now define a function RandomInt(N). This function generates a random number between 0 and N-1 (inclusive) with equal probability.
Now RandomInt(Random(Random(..........RandomInt(N).....)))) is nested.
RandomInt(N) means nesting of 1.
And RandomInt(RandomInt(N)) means nesting of 2 and thus so on....

You will be given a Number N, nesting (the no of nestings) and Target.

You have to give the probability of getting a number = Target after nestings starting from number N

SwitchCase

Posts : 5
Join date : 2008-08-13

View user profile

Back to top Go down

Re: RandonInt()

Post  ankurgutpa on Mon Oct 06, 2008 11:44 am

I'm not able to figure out probability but considered following cases:
Let N be number, T be target and n be nestings
if n>=N and T>0 we cannot get T
if N>T (alsothen we cannot get T
if n> N-T ( N > T obviously ) ,we cannot get T
else
we can get T with probability is as follow
0: 1/N +1/2N + ....+ 1/nN
1:1/N +.........+ 1/(n-1)N
.
.
N-1: 1/N
avatar
ankurgutpa

Posts : 44
Join date : 2008-08-10
Age : 31
Location : Tandon 72

View user profile

Back to top Go down

Re: RandonInt()

Post  Ramprasadg on Tue Oct 14, 2008 9:01 pm

my understanding of the problem is simple(probably not right Wink ).

target > N - number_of_nestings OR target < 0
P(target) = 0

0<= target <= N - number_of_nestings
this part needs more maths.... i am weak in it..
its not evenly distributed of course.because at the end,the outer most RandInt can get anything less than N - number_of_nestings as input.
so intuitively it feels like P(1) > P(2) > P(3) .....
somebody please solve this thing!!!


Last edited by Ramprasadg on Tue Oct 14, 2008 9:09 pm; edited 1 time in total
avatar
Ramprasadg

Posts : 12
Join date : 2008-08-13

View user profile

Back to top Go down

Re: RandonInt()

Post  Ramprasadg on Tue Oct 14, 2008 9:06 pm

P(N-1) != 1/N

see to get N-1 as target,every nested RandomINt must give N-1.
so the ans is (1/N-1)^no_of_nestings.
avatar
Ramprasadg

Posts : 12
Join date : 2008-08-13

View user profile

Back to top Go down

Re: RandonInt()

Post  Sponsored content


Sponsored content


Back to top Go down

Back to top


 
Permissions in this forum:
You cannot reply to topics in this forum