In this case, k = J(n)
The recurrence is :
int f(int n){
if(n == 1) return 1;
if(n&1) return 2*f(n/2) +1; // case its odd
return 2*f(n/2) -1; // case it's even
}
--
but the statement J(2n) = 2J(n) is incorrect, since, J(2n) = 2J(n)-1
sorry if it wasn't the question.. what was your real doubt?
---
grato,
Gustavo Pacianotto Gouveia
Escola Politécnica da Universidade de São Paulo
<[email protected]> [email protected]
[email protected]
[email protected]
2011/3/5 Satyajit Bhadange <[email protected]>
> hi,
>
> I am studying Josephus problem
> the recurrence relation for same is
>
> J(1) = 1;
> J(2n) = 2J(n) - 1, for n >= 1
> j(2n + 1) = 2J(n) + 1, for n >= 1
>
> how J(2n) = 2J(n)
>
> on R.H.S side how 2 which is called k is derived..
>
> its is given in book that (concrete mathematics)
>
> J(2n) = newnumber(J(n)),
> where
> newnumber( k) =
> 2k-1.
>
>
> what is k..?
>
> --
> You received this message because you are subscribed to the Google Groups
> "google-codejam" group.
> To post to this group, send email to [email protected].
> To unsubscribe from this group, send email to
> [email protected].
> For more options, visit this group at
> http://groups.google.com/group/google-code?hl=en.
>
>
--
You received this message because you are subscribed to the Google Groups
"google-codejam" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/google-code?hl=en.
