Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
add comment

1 Answer

up vote 1 down vote accepted

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.