DevX Home Today's Headlines   Articles Archive   Tip Bank   Forums

# Thread: Josephus Problem, problem.

1. Registered User
Join Date
Apr 2005
Posts
12

## Josephus Problem, problem.

I'm borrowing this post from another forum, because the guy was having troubles very similar to what i'm having, and i'm doing a very similar project. the assignment is one of the Josephus problem, including, from a command line, have a user enter 2 values, 1 for the amount of people, and the other for the number of people to pass. the Josephus problem is:

N people, numbered 0 to N-1, are sitting in a circle. Starting at person 0, a hot potato is passed. After M people touch the potato, the person holding the potato is eliminated, the circle closes ranks, and the game continues with the person sitting after the eliminated person starting with the potato. The last person remaining wins.

Write a program to accept two command line inputs representing N (the number of people in the circle) and M (the number of people required to touch the hot-potato before a person is eliminated). Initialize a StringBuffer to consist of the characters numbered 0 through N-1 (note: since there are 216 = 65,536 Unicode characters your program will be capable of solving Josephus' Problem up to this value of N).

I've got my code to where I think it should at least work with figuring out the last person left after the entire Josephus problem is carried out, but I keep getting out of bounds compile-time errors whenever I run my code, like the following:

Exception in thread "main" java.lang.StringIndexOutOfBoundsException:String index out of range

Here is my code thus far:

Code:
```import java.lang.StringBuffer;

public class Josephus {

public static void main (String[] args) {

//These two variables store the two values for the people and the passes.
int num = 0;
int pass = 0;

//This variable stores the value of the current index.
int index = 0;

//These two variables store the command line inputs.
String N = args[0];
String M = args[1];

//Output the command line inputs.
System.out.println("There will be " + N + " people.");
System.out.println("A person will be eliminated for every " + M + " touches.");

//Convert the String command line inputs to integers.
Integer tmpN = Integer.valueOf(N);
num = tmpN.intValue();
Integer tmpM = Integer.valueOf(M);
pass = tmpM.intValue();

//Array stores the deleted values.
int[] deleted = new int[num];

//Create a new StringBuffer for the program.
StringBuffer josephus = new StringBuffer(num);

//Create the values needed for the program.
for(int i=0; i<num; i++) {
josephus.append((char)(i+1));
}

//Test garbage.
System.out.println();
System.out.println((int)josephus.charAt(pass-2));

//Loop to solve the Josephus problem.  Note the -1 may need changed.
for(int i=0; i><num-1; i++) {

if((index+pass) > (num)) {

index = (index + pass) % (num);

//Get the value from the StringBuffer, then delete the value.
deleted[i] = (int)josephus.charAt(index);
josephus.delete(index, index+1);

} else {

index += pass;
deleted[i] = (int)josephus.charAt(index);
josephus.delete(index, index+1);

}

}

System.out.println("The final remaining member is " + (int)josephus.charAt(0));
}

}```
If anyone could point out where the problems with this could be occurring, I'd appreciate it. If someone could also provide me with some tips for figuring out problems like this on my own more easily, I would definitely appreciate that as well. I've just played around with the numbers for the past few hours with no luck at ever getting it to run successfully.

2. Registered User
Join Date
Dec 2005
Location
New Jersey
Posts
290
I always like problems like these. I'm going to look at the way you did it in a sec, but I just made my own .
Code:
```import java.util.*;

public class HotPotato {
/** people left in the game */
static ArrayList<Integer> people = new ArrayList<Integer>();

/** how many rounds before elimination */
static int rounds;

/** current index of the people array we're on */
static int currentIndex = 0;

/** how many turns have passed total */
static int turnsPassed = 0;

static public void main(String[] args) {
rounds = args[1];

/** put everyone in the game */
for (int i = 0; i < args[0]; i++) {
}
/** while we don't have a winner pass the potato */
while (people.size() > 1) {
passPotato();
}
/** the winner is the last person remaining */
System.out.println("The winner is person #" + people.get(0));
}

static public void passPotato() {
/** increase the amount of times the potato has been passed */
turnsPassed++;

/**
* if the amount of turns passed is divisible by the amount
* of rounds before elimination, then remove the person at our
* current index
*/
if (turnsPassed % rounds == 0) {
people.remove(currentIndex);
} else {
/** otherwise, pass the potato along */
currentIndex++;
currentIndex %= people.size();
}
}
}```
 crap I didn't see the second paragraph
Last edited by destin; 01-28-2006 at 07:23 PM.

3. Registered User
Join Date
Oct 2005
Posts
107
i'd change this ...

if((index+pass) > (num)) {

to this...

if((index+pass) >= num){

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•

 FAQ Latest Articles Java .NET XML Database Enterprise
 Questions? Contact us. C++ Web Development Wireless Latest Tips Open Source