my question was from where did 2 come in RHS in eqn. 2*f(n/2) - 1... coefficient of f(n/2)
On Mar 6, 7:54 am, Gustavo Pacianotto Gouveia <[email protected]> wrote: > 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.
