Thread: Circular arrays

    #1
  1. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2007
    Posts
    64
    Rep Power
    14

    Circular arrays


    There are 10 children who are playing a game of drop out. There is a sentence of 7 words. Starting at the first child, the child who called the 7th word drops out. The process continues in a circular array until the last child is left.

    My program gives 1 for the answer, but when I work it manually I get nine. need some help!!

    Code:
    import java.io.*; 
    import java.util.*; 
    
     class Ex8n024{ 	public static void main(String[] args){ 		int n = 10; //children 		int m = 7;// length of sentence 		int i=0; 		int []a = new int[n +1]; 		 		//init array elements to 1 		 		for(int j =1; j <a.length; j++) 		{ 			a[j] = 1; 		} 		 		for(i =1; i <= n; i++){ 			int count = 0; 			 			while (count < m){ 				i = i % n + 1	; 				if(a[i] == 1)count++; 				 			} 			a[i] =0;	 		} 		 		 		 		for (i = 1; i <n; i++){ 			 			if(a[i]==1) 				break; 			 		} 		 	System.out.printf("The last child is  %d", i); 		 	}//main }//end class

    Comments on this post

    • spyder0101 agrees : Formatting needs help, but otherwise this is a great example of how to ask a question.
  2. #2
  3. Santosh Vaza
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jun 2010
    Location
    JHome
    Posts
    356
    Rep Power
    17
    There might be some problem in your program logic, try to solve it and post what errors you get or where have you stuck..
    Originally Posted by chetahXX
    My program gives 1 for the answer, but when I work it manually I get nine. need some help!!
    It doesnt gives sufficient information about your problem..

    Also pls format your code properly.

    Comments on this post

    • hglasgow agrees
    • Yawmark disagrees : [0] There is sufficient information in that post to resolve the problem.
    no one can become perfect by merely ceasing the act
  4. #3
  5. Feelin' Groovy
    Devshed Supreme Being (6500+ posts)

    Join Date
    Aug 2001
    Location
    Chicago, IL
    Posts
    10,131
    Rep Power
    5058
    It doesnt gives sufficient information about your problem..
    I completely disagree. There is a description of the expected result and the actual result. There is an SSCCE (unformatted, but an SSCCE nevertheless). Would that everyone who came here with a question did as good a job providing such detailed information!

    ~

    Comments on this post

    • mvantuyl agrees : Amen to that!
    Yawmark
    class Sig{public static void main(String...args){\u0066or(int
    \u0020$:"v\"ʲ\"vΤ\"".to\u0043h\u0061rArray()
    )System./*goto/*$/%\u0126//^\u002A\u002Fout.print((char)(($>>
    +(~'"'&'#'))+('<'>>('\\'/'.')/\u002Array.const(~1)\*\u002F)));}}
  6. #4
  7. Contributing User
    Devshed Intermediate (1500 - 1999 posts)

    Join Date
    Feb 2007
    Posts
    1,939
    Rep Power
    3122
    Print out the values in your array throughout your code. You will see that your program will stop before all the children are eliminated.

    Comments on this post

    • Yawmark agrees
  8. #5
  9. Feelin' Groovy
    Devshed Supreme Being (6500+ posts)

    Join Date
    Aug 2001
    Location
    Chicago, IL
    Posts
    10,131
    Rep Power
    5058
    @chetahXX: I have formatted your code, added comments, and some explanatory code to point you in the right direction. See if you can see the multiple problems in your for loop:
    Java Code:
    import java.io.*;
    import java.util.*;
     
    class Ex8n024{
        public static void main(String[] args) {
            /*
             * Give your variables meaningful names, so you don't
             * need to clutter the code with comments.
             *
             * For example, the next line should something like:
             *
             *     int totalChildren = 10;
             */
            int n = 10; // children
     
            /*
             * Same thing applies here. For example:
             *
             *     int sentenceLength = 7;
             */
            int m = 7;// length of sentence
     
            /*
             * Variables should be declared and initialized in the smallest
             * scope possible. This variable is declared too far away from
             * where it is first used.
             */
            int i = 0;
     
            /*
             * Why one more element than necessary? Arrays are zero-indexed.
             * Don't use unconventional techniques; they only complicate
             * your code and any subsequent troubleshooting.
             *
             * Also, variable names are important as mentioned. Example:
             *
             *    int[] children = new int[totalChildren];
             */
            int[] a = new int[n + 1];
     
            /*
             * The next block of code does not do what the comment says.
             * Not all array elements are initialized to 1.
             */
            //init array elements to 1
            for (int j = 1; j <a.length; j++) {
                a[j] = 1;
            }
     
            /*
             * Here's proof. Compile and run with "java -ea Ex8n024".
             */
            assert a[0] != 1;
     
            /*
             * This algorithm does not behave as one would expect to solve
             * the problem. Look at the the output generated from the added
             * lines.
             */
            System.out.printf("The following process will stop when the child index is > %d%n%n", n);
            for(i = 1; i <= n; i++) {
                System.out.printf("The current child index is: %d%n", i);
                int count = 0;
                while (count < m) {
                    i = i % n + 1;
                    if (a[i] == 1) count++;
                }
                System.out.printf("The child dropping out is number: %d%n", i); // <-- Observe
                a[i] = 0;
                System.out.println(Arrays.toString(a)); // <-- Observe
                System.out.printf("The next child index is: %d%n%n", i + 1);
            }
     
            /*
             * Again, use standard array indexing to avoid fencepost errors.
             */
            for (i = 1; i < n; i++) {
                if(a[i] == 1) break;
            }
     
            System.out.printf("%n%nThe last child is  %d", i);
     
        /*
         * Comments such as those below are superfluous. Don't clutter up your
         * code this way.
         */
        }//main
    }//end class

    You can also find a *lot* more information about this sort of problem by using your favorite search engine and the terms "Josephus Problem."

    ~
    Yawmark
    class Sig{public static void main(String...args){\u0066or(int
    \u0020$:"v\"ʲ\"vΤ\"".to\u0043h\u0061rArray()
    )System./*goto/*$/%\u0126//^\u002A\u002Fout.print((char)(($>>
    +(~'"'&'#'))+('<'>>('\\'/'.')/\u002Array.const(~1)\*\u002F)));}}
  10. #6
  11. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2007
    Posts
    64
    Rep Power
    14
    I modified my approach after some reading. I now decide to reduce the array my one after each child is eliminated, but the answer still does not come out right. Here is my new code.
    Code:
    import java.io.*;
    import java.util.Scanner;
    
    public class Ex8no24 {
    
        public static void main(String[] args) {
            //Initiates the variables N and M for later use.
    	int N = 10;
    	int M = 7;
    
    	//Initiates index variable to use in later "for" loop.
    	int index = 0;
    
           int []c = new int [N];
            //System.out.println(deleted.length); Double-checks spaces available in
            //array to be (N - 1) spaces.
            
    	       
            //Creates each knight from N as a separate value.
    	for(int i = 0; i < N; i++) {
    		c[i] = i + 1;
                    System.out.println("Knight No. " + c[i] + " created.");
    		}
    
            //Starts loops that solves Josephus problem.
            for(int i = 0; i < N - 1; i++) {
                if((index + M) > (c.length) - 1) {
                    index = (index + (M - 1)) % c.length;
                    
                    stem.out.println("Knight No. >" + index + "< is dead");
                    removeElt(c,index);
    
                } 
                else{
                   index = (index + (M - 1));
                   System.out.println("Knight No. >" + index + "< is dead");
                   removeElt(c,index);
                }
            }
           
    
            int x = c[0];
    
            System.out.println("Therefore, Knight No. " + x +
                    " is the lone survivor.");
            
        }//mian
    
    
    	public static void removeElt( int [] arr, int remIndex )
    {
       for ( int i = remIndex ; i < arr.length - 1 ; i++ )
       {
          arr[ i ] = arr[ i + 1 ] ; 
       }
    }
    
    }//end class
  12. #7
  13. Feelin' Groovy
    Devshed Supreme Being (6500+ posts)

    Join Date
    Aug 2001
    Location
    Chicago, IL
    Posts
    10,131
    Rep Power
    5058
    I now decide to reduce the array my one after each child is eliminated
    That's not necessary, or even desirable.

    ~
    Yawmark
    class Sig{public static void main(String...args){\u0066or(int
    \u0020$:"v\"ʲ\"vΤ\"".to\u0043h\u0061rArray()
    )System./*goto/*$/%\u0126//^\u002A\u002Fout.print((char)(($>>
    +(~'"'&'#'))+('<'>>('\\'/'.')/\u002Array.const(~1)\*\u002F)));}}

IMN logo majestic logo threadwatch logo seochat tools logo