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