So,when k is other than 2 does that mean we an directly replace 2 in the recurrence with other k value.
And if this is not the case then what will be the equation in that case. On Sun, May 1, 2011 at 3:08 PM, Wasif Hossain <[email protected]>wrote: > Actually You have to give attention to the followings: > 1) If we assume that every k-th person will die, then every number that is > multiple of k will die after 1st trip. > 2) specially when k=2 and n is Even, then "we arrive at a situation similar > to what we began with, except that there are only half as many people and > their numbers have changed". > > *So, we can arrive at a decision that your desired "2" comes from "k" > when k=2.* > > regards, > Wasif Hossain > Student of Computer Science and Engineering > Bangladesh University of Engineering and Technology > Dhaka, Bangladesh > > > On Sun, Mar 6, 2011 at 11:22 AM, Satyajit Bhadange < > [email protected]> wrote: > >> 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. >> >> > -- > 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. > -- Thanks & Regards, Satyajit Bhadange http://satyajit-algorithms.blogspot.com/ -- 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.
