Description
To simulate a simple survivor game with a queue.
Exercise
File Lab4.java contains an almost-complete application with a simple Queue. You need to add most of the body of the method survivor, which currently only prints some information.
The survivor method should simulate (using a queue) the survivor game. In this game, N people (numbered 0 to N− 1) stand in circle, then every kth person is counted out (leaves the circle), until only one person is left. At each elimination, you should print out the eliminated person’s number.
For example, if there are 7 people (N = 7) and k = 2, then you should print out 1 3 5 0 4 2 6 because
| the circle changes as follows: | ||
| 0 | 0 | 0 |
6Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â 1Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â 6Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â 1Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â 6
- 2 5Â Â Â Â Â Â Â Â Â Â Â Â Â 2Â Â Â Â Â Â Â Â Â Â Â Â Â 5Â Â Â Â Â Â Â Â Â Â Â Â Â Â 2
4Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â 3Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â 4Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â 3Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â 4Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â 3
Start                                 First elimination: 1                 Second elimination: 3
0Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â 0
- 6 6
| 4
Third elimination: 5 |
4
Fourth elimination: 0 |
4
Fifth elimination: 4 |
|
| 6 | 6 |
5 Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â 2Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â 2Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â 2
2
Third elimination: 2Â Â Â Â Â Â Â Â Â Â Â Â Last element remaining: 6
The code that you add to the survivor method must simulate the game using a queue to represent the circle of people. To do the eliminating, you must use the standard queue methods (enter, leave, front, and isEmpty) provided in the Queue class. You may not change the Queue class or the main method in any way.
Hint: You can keep eliminating until no people are left in the circle. Sample output:
7 people numbered 0 to 6 stand in a circle.
Every second person is eliminated repeatedly until only one person is left.
The people are eliminated in the following order:
1 3 5 0 4 2 6 <=== last person left
11 people numbered 0 to 10 stand in a circle.
Every third person is eliminated repeatedly until only one person is left. The people are eliminated in the following order:
2 5 8 0 4 9 3 10 7 1 6 <=== last person left
17 people numbered 0 to 16 stand in a circle.
Every 5-th person is eliminated repeatedly until only one person is left.
The people are eliminated in the following order:
4 9 14 2 8 15 5 12 3 13 7 1 0 6 11 16 10 <=== last person left
Program ends normally.
