Josephus Problem, problem.


DevX Home    Today's Headlines   Articles Archive   Tip Bank   Forums   

Results 1 to 3 of 3

Thread: Josephus Problem, problem.

Hybrid View

  1. #1
    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. #2
    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++) {
                people.add(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();
            }
        }
    }
    [edit] crap I didn't see the second paragraph
    Last edited by destin; 01-28-2006 at 07:23 PM.

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

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

    to this...

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

Similar Threads

  1. Problem with Search
    By Irina in forum ASP.NET
    Replies: 0
    Last Post: 11-29-2002, 11:47 PM
  2. Replies: 0
    Last Post: 12-13-2001, 01:06 PM
  3. a problem with font and language
    By Roseta in forum VB Classic
    Replies: 0
    Last Post: 11-14-2001, 04:24 AM
  4. Arabic problem view
    By Ayman in forum VB Classic
    Replies: 0
    Last Post: 04-03-2000, 02:08 AM
  5. Problem with CryptoAPI and JCE
    By Jason Bock in forum VB Classic
    Replies: 0
    Last Post: 03-21-2000, 07:48 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
HTML5 Development Center
 
 
FAQ
Latest Articles
Java
.NET
XML
Database
Enterprise
Questions? Contact us.
C++
Web Development
Wireless
Latest Tips
Open Source


   Development Centers

   -- Android Development Center
   -- Cloud Development Project Center
   -- HTML5 Development Center
   -- Windows Mobile Development Center