Josephus problem

This is a discussion on Josephus problem within the C++ Programming forums, part of the General Programming Boards category; Has anybody over here ever tried the Josephus problem? In Massada, in ancient Greece, it was decided that there were ...

  1. #1
    I'm Back
    Join Date
    Dec 2001
    Posts
    556

    Josephus problem

    Has anybody over here ever tried the Josephus problem?

    In Massada, in ancient Greece, it was decided that there were too many prisoners and many should be executed. One prisoner was given a sword and all 1000 prisoners were instructed to stand in a circle. The one with the sword was instructed to kill the man on his left and then pass the sword to the next man on the left, who would then do the same. The circle would continue to get smaller as this continued, and the last man left would be set free. Josephus, one of the prisoners, placed himself at the correct position in the line-up to be the one remaining man at the end of this elimination. At what position did he place himself on the circle? Also, if the last two will be set free, where should Josephus direct his friend to stand?

    I got the answer 977. Is it correct??

    Post your codes too [if you want]

  2. #2
    geek SilentStrike's Avatar
    Join Date
    Aug 2001
    Location
    NJ
    Posts
    1,141
    I got it correct (at least, I did if you did) on the second compilation attempt, and the first valid compilation.

    Code:
    #include <list>
    #include <iostream>
    
    int main() {
    	std::list<int> people_nums;
    	int peopleCount=1000, finalNumberLiving=2;
    
    	for (int i = 0; i < peopleCount; ++i) {
    		people_nums.push_back(i);
    	}
    
    	typedef std::list<int>::iterator it;
    	it curPersonIt = people_nums.begin();
    
    	while (peopleCount > finalNumberLiving) {
    		it end = people_nums.end();
    		/* went passed end of list, wrap around */
    		if (curPersonIt == end) curPersonIt = people_nums.begin();
    
    		/* at last valid person in list, kill dude in front and wrap around */
    		if (curPersonIt == --end) curPersonIt = people_nums.erase(people_nums.begin());
    		/* somewhere not near end of list, kill the next guy, and pass sword to the next next guy */
    		else curPersonIt = people_nums.erase(++curPersonIt);
    
    		peopleCount--;
    	}
    
    	std::cout << "And the survivors are (person starting with the sword labelled with 0, next is 1, etc)\t";
    
    	for (it curSurvivor = people_nums.begin(); curSurvivor != people_nums.end(); ++curSurvivor) {
    	 		std::cout << *curSurvivor << ' ';
    	}
    
    	return 0;
    }
    Prove you can code in C++ or C# at TopCoder, referrer rrenaud
    Read my livejournal

  3. #3
    I'm Back
    Join Date
    Dec 2001
    Posts
    556

    Thumbs up

    Hey cool thanks for confirming it.

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, 03:51 PM
  2. WS_POPUP, continuation of old problem
    By blurrymadness in forum Windows Programming
    Replies: 1
    Last Post: 04-20-2007, 07:54 PM
  3. Please , i need help with this Josephus Problem
    By Haytham in forum C Programming
    Replies: 17
    Last Post: 04-07-2007, 08:28 PM
  4. Laptop Problem
    By Boomba in forum Tech Board
    Replies: 1
    Last Post: 03-07-2006, 06:24 PM
  5. The Josephus Problem
    By Nakeerb in forum C++ Programming
    Replies: 5
    Last Post: 11-21-2002, 08:43 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21