Please find your answers below with your questions.
On Mon, May 2, 2011 at 12:29 AM, Satyajit Bhadange < [email protected]> wrote: > So,when k is other than 2 does that mean we an directly replace 2 in the > recurrence with other k value. > Ans. Yes, you can do that, but the condition should hold: 'n' is a multiple > of 'k' i.e n = mk, for m=0,1,2,... > > > And if this is not the case then what will be the equation in that case. > Ans. if 'n' is NOT multiple of 'k', then you have to extend your equation as needed. > > 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. > -- 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.
