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!