1

I am trying to understand josephus problem recursive algorithms.It has been explained in details here . But I am not clear about certain details . here those are :

The 1-indexed position of the survivor in the ring of four people is given by josephus(n - 1, 2). We can therefore walk forward josephus(n - 1, 2) - 1 positions, wrapping around the ring if necessary, to get to our final position. In other words, the survivor is given by position.

doubts : how are we reaching to equation josephus(n-1,2)-1 by which we need to walk forward.

Now this also has been explained in the comment section but i am not able to understand how this information is helping us to reach the final recursive method.

Here is the final recursive method :

public int josephus(int n, int k)
{
 if (n == 1) return 1;
 return (josephus(n - 1, k) + k-1) % n + 1;
}

I understand that this question may be marked as duplicate but still if someone can explain me the intuition. I tried Wikipedia but no luck so far.

optional
  • 3,260
  • 5
  • 26
  • 47

1 Answers1

0

At first I struggled with this as well, but then I realized the fact that we use the previous recursion josephus(n-1,2) only to identify where in the current circle of people did the previous surviver was if we started counting just after we kill the k'th person.

The position of the last survivor in the circle of n people is related to the position of the last survivor in the circle of n-1 people, as we need to adjust the position of the last survivor in the smaller circle to match the larger circle.

So we add k-1 % n + 1 just to adjust the position.

Daniel
  • 13
  • 5