Josephsus Problem

Tthe Josephus problem (or Josephus permutation) is a theoretical problem related to a certain counting-out game.

There are people standing in a circle waiting to be executed. After the first person is executed, certain number of people are skipped and one person is executed. Then again, people are skipped and a person is executed. The elimination proceeds around the circle (which is becoming smaller and smaller as the executed people are removed), until only the last person remains, who is given freedom.

The task is to choose the place in the initial circle so that you are the last one remaining and so survive.

The easiest way to solve this problem in the general case is to use dynamic programming. This approach gives us the recurrence:

This can be seen from the following arguments:

• When starting from position k(mod n) instead of 0, the number of the last remaining person also shifts by k positions
• After the first round of the n person problem one eliminates the person on position kmod n and is left with an n − 1 person problem. The person (k + 1)mod n (in the n person case) is the first of the nextk counts and thus has the label 1 in the n − 1 problem. We must therefore shift the outcome of then − 1 problem by (k + 1 − 1) positions to get the answer for the case with n persons.

This approach has running time O(n), but for small k and large n there is another approach. The second approach also uses dynamic programming but has running time O(klogn). It is based on considering killing k-th, 2k-th, ..., -th people as one step, then changing the numbering.

Refer : http://en.wikipedia.org/wiki/Josephus_problem

Ex : If n people are standing in a circle ,they start shooting the person standing next to their neighbour.If they start firing in this way , determine who will be alive after this sequence ??


f(n,k) = (f(n-1,k) + k)%n with f(1,k) = 0

public class JosephusProblem {
 public static void main(String[] args) {
  System.out.println(f(6, 1));
 }

 public static int f(int n, int k) {
  if (n == 1)
   return 0;
  else {
   return (f(n - 1, k) + k) % n;
  }
 }

}

Refer : http://ihaventyetdecided.blogspot.com/2010/10/josephus-problem.html