[Home | Assignments | Links | Grades | CIS 313]
CIS 323 - Assignment 1
The Josephus problem
Due Thursday, January 21, 2010
You must write your code in C++ for this assignment.
The Josephus problem is classic, although it is also a little grim. The history of the problem is in its wikipedia entry, but our formulation of the problem differs subtly from most of the ones found on the net.
There are n soldiers trapped in a cave and hopelessly surrounded. They agree to kill each other to save themselves from what they are sure is a far more gruesome fate of capture. They agree to kill each other using the following method: The first soldier a will kill soldier b directly in front of a. Then, the next living soldier c will kill the next living soldier d in front of them. And so on until there is only one peron left. At some point, then, a might have to kill c.
Your task is to simulate this process, provide an ordered listing of who kills whom, and then print out who survives after this bizarre suicide is complete. You should do this directly, by putting the soldiers in a circularly linked list and then progressively removing every other soldier.
The input you will be given will be formatted as an integer on its own line (representing the number of soldiers) and then every name on its own line, in order. The output should be n-1 lines, where each line says "x kills y", and then one last line saying "z lives!".
Here is an example:
- Input:
-
7 Bashful Doc Dopey Grumpy Happy Sleepy Sneezy - Output:
-
Bashful kills Doc Dopey kills Grumpy Happy kills Sleepy Sneezy kills Bashful Dopey kills Happy Sneezy kills Dopey Sneezy lives!
You should conform exactly to the input and output specification, as I will be using massive test cases and checking your output against the correct output with the diff command. So let me say it again: conform exactly to the input and output specification!
In order to verify O(n) timing, a much larger test case may be found in words. If you find your algorithm taking more than a minute, there's probably a problem. Also, in that example, bauxite lives.