Thread: The Josephus Problem

  1. #1
    Registered User
    Join Date
    Oct 2002
    Posts
    155

    The Josephus Problem

    I am having a bit of trouble. The Josephus problem is where you have a circle of people, body_count people big (like, if body_count were 5, that means the circle is made up of 5 people). And another term, excuse_counter, is set to a number. Using this number we go around the circle elinimating people until one is left.

    For instance, let's say the circle is made of 9 people, and we choose our excuse_counter to be 5:

    5, 1, 7, 4, 3, 6, 9, 2, 8

    We reloop around this circle nailing off the person we come to when we count to excuse_counter. Using the remaining people we count again, etc, until we are left with one man left.

    However I am having a bit of trouble with the coding portion. It finds the first person alright, but from here it's all downhill:

    Code:
    person* pick_person(person *group, int excuse_counter, int body_count){
    	person *temp = new person;
    	temp -> position = 12345;
    	temp -> next = group;
    	
    	person *previous = temp;
    	person *current;
    	
    	for (int i = 1; i < body_count; i++){
    		
    		for (int x = 1; x <= excuse_counter; x++){
    
    			if (temp -> next -> next == NULL)
    				temp -> next = previous -> next;
    			
    			
    			else
    				temp = temp -> next;
    					
    		}
    		
    		cout << "\nPerson " << temp -> position << " is leaving...";
    		
    		current = temp;
    		
    			
    		while (previous -> next != current){
    			previous = previous -> next;
    		}
    			
    		previous -> next = current -> next;
    		delete current;
    				   	   	   	   
    	}	 
    
    return group;
    } //end person *pick_person


    The struct:



    Code:
    struct person{
    	int position;
    	person *next;
    };

    I know this is very close to working but it needs a push in the right direction. I am using a linklist

  2. #2
    CS Author and Instructor
    Join Date
    Sep 2002
    Posts
    511
    I would use a queue. I had to do this problem in college.

    Also, would it be better to use a random number to choose which person who would be killed??
    Mr. C: Author and Instructor

  3. #3
    Registered User
    Join Date
    Oct 2002
    Posts
    155
    No the user decides the values

  4. #4
    Registered User
    Join Date
    Oct 2002
    Posts
    155
    That and the problem states that we must use a linklist

  5. #5
    Skunkmeister Stoned_Coder's Avatar
    Join Date
    Aug 2001
    Posts
    2,572
    well my approach to this would be a circular list. This can be rotated and nodes removed. I would think that a circular list will model a circle of people better
    Free the weed!! Class B to class C is not good enough!!
    And the FAQ is here :- http://faq.cprogramming.com/cgi-bin/smartfaq.cgi

  6. #6
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    Try to find the trick to solving this problem fast without a
    list.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. A question related to strcmp
    By meili100 in forum C++ Programming
    Replies: 6
    Last Post: 07-07-2007, 02:51 PM
  2. WS_POPUP, continuation of old problem
    By blurrymadness in forum Windows Programming
    Replies: 1
    Last Post: 04-20-2007, 06:54 PM
  3. Please , i need help with this Josephus Problem
    By Haytham in forum C Programming
    Replies: 17
    Last Post: 04-07-2007, 07:28 PM
  4. Laptop Problem
    By Boomba in forum Tech Board
    Replies: 1
    Last Post: 03-07-2006, 06:24 PM
  5. beginner problem
    By The_Nymph in forum C Programming
    Replies: 4
    Last Post: 03-05-2002, 05:46 PM