1
$\begingroup$

So I was trying to write a little java program that would solve [Josephus' Problem][1]. The one where you have a certain amount of people in a circle and then a count where every 3rd, 4th or what have you is eliminated, until there is only one remaining. I was writting a program that will take user input for the number of soldiers as well as the count between each kill.

Heres a link to the problem in more detail:

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

Using this logic.

Assuming that the start position is index 1. He is safe as he is the only one in the game:

f(1,k) = 1

In general you solve the nth case by reducing the problem by 1 and solving, adding k afterwards:

f(n,k) = f(n-1,k)+ k mod n+1
= f(n-2,k) + 2k mod n
= f(1,k) + (n-1)k mod n
= 1 + (n-1)k mod n

Should be: return 1 + (((n-1) * k) % n);

I came up with this.

import java.util.Scanner;  public class JosephusProblem {     public static void main(String[] args)     {         Scanner input = new Scanner(System.in);          int safespace;         System.out.println("Please enter the number of soliders");         int soldiers = input.nextInt();         System.out.println("Please enter the how many soldiers are skipped before the next death");         int count = input.nextInt();         //safespace = 1 + (((soldiers-1) * count) % soldiers);         safespace = 1 + (((count-1) * soldiers) %count);         System.out.println("The safe place to stand would be " + safespace);     }     //end main } //end class 

At first I thought it was just a stupid mistake of me getting the variables mixed up (as you can see) but neither is returning what I was looking for. Math is not my strong suit and this has been bugging me for a little longer than I like. Can anyone tell me where I went wrong? Thank you in advance for any adive you can give!

1 Answers 1

1

First when you look at the algorithm $ \begin{align*} f(n,k) &= \left(f(n-1,k)+ k \right) ({\text mod} n) + 1\\ &= \left(f(n-2,k) + 2k \right) ({\text mod} n) +1\\ &= \left(f(1,k) + (n-1)k \right) ({\text mod} n) \\ &= 1 + (n-1)k ({\text mod} n) \\ \end{align*} $ is not correct They are not always mod $n$ When you find $f(n-1, k)$ it goes like this

$f(n-1, k) = \left(f(n-2, k)+ k\right) ({\text mod}\hspace{3pt} (n-1))$

So you cannot reach to a single expression. You have to rather write a recursive function or a function using tail-recursion.

Someone wrote a program using Java Collection classes.

Check http://users.cis.fiu.edu/~weiss/dsj2/code/Josephus.java