In this problem, you will learn how to use a computer to solve a thorny historical problem. You will also apply your recently-gained knowledge of abstract data types, C++ classes, and linked lists.
The historian Flavius Josephus relates how, in the Romano-Jewish conflict of 67 C.E., the Romans took the town of Jotapata which he was commanding. Escaping, Jospehus found himself trapped in a cave with 40 companions. The Romans discovered his whereabouts and invited him to surrender, but his companions refused to allow him to do so. He therefore suggested that they kill each other, one by one, the order to be decided by lot. Tradition has it that the means for effecting the lot was to stand in a circle, and, beginning at some point, count round, every third person being killed in turn. The sole survivor of this process was Josephus, who then surrendered to the Romans. Which begs the question: had Josephus previously practiced quietly with 41 stones in a dark corner, or had he calculated mathematically that he should adopt the 31st position in order to survive?
Having read an account of this gruesome event you become obsessed with the fear that you will find yourself in a similar situation at some time in the future. In order to prepare yourself for such an eventuality you decide to write a program to run on your smartphone which will determine the position in which you should stand in order to ensure that you will be the sole survivor.
In particular, your program should be able to handle the following processes. n > 0 people are initially arranged in a circle, facing inwards, and numbered consecutively from 1 to n clockwise. Starting with person number 1, counting starts in a clockwise direction, until we get to person number k (k >= 0), who is promptly killed. We then proceed to count a further k people in a clockwise direction, starting with the person immediately to the left of the victim. That kth person is killed next, and so on, until only one person remains.
For example, when n = 5, and k = 0, the players are eliminated in order, and player 5 wins. If n = 5 and k = 1, the order of elimination is 2, 4, 1, 5, and player 3 wins. Note that players are not renumbered after each death: everyone keeps their initial number until the end (or their end).
Write a program to solve the Josephus problem for general values of n > 0 and k >= 0. Your program must read multiple problems from cin and write the winners for each to cout. Each problem will be on its own input line containing values for n and k (in that order). For each input problem, your program should output a single line containing only the number of the survivor (so youll know in which position to stand). Input will be terminated by a line containing values of 0 for both n and k. Your program may assume that both n and k can be held by int variables.
While it may be the case that this problem can be solved in a simpler manner, you should solve this using a singly linked list. Your program should create one node for each person in the scenario (i.e., n nodes, not counting any dummy nodes) and delete a node each time it determines a person to kill. The traversal algorithm you use should be a member of your list class; it should take in the value of k and use that value to delete nodes until only one survivor is present. Initialization of your list should be accomplished by some method other than the traversal algorithm or the constructor either an external function that uses list primitives or an initialization method in your list class.
When you submit your program, remember that each class you use should have its own .h and .cpp files. This means that a working program with only one class will have at least three files, as youll also need one for main(). Please go over the syllabus carefully to make sure that you obey all design, documentation, and coding standards.