Simulation - Data Structures and Problem Solving Using Java - page 523

common errors

The most common error in simulation is using a poor model. A simulation
is only as good as the accuracy of its random input.

1.

on the internet

Both examples in this chapter are available online.

Josephus.java Contains both implementations of josephus and a

main to test them.

CallSim.java Contains the code for the call bank simulation.

exercises

IN SHORT
13.1

If M = 0, who wins the Josephus game?

Show the operation of the Josephus algorithm in Figure 13.3 for the
case of seven people with three passes. Include the computation of
rank and a picture that contains the remaining elements after each
iteration.

13.2

Are there any values of M for which player 1 wins a 30-person Jose-
phus game?

13.3

Show the state of the priority queue after each of the first 10 lines of
the simulation depicted in Figure 13.4.

13.4

IN THEORY
13.5

Let N = 2 k for any integer k . Prove that if M is 1, then player 1 always
wins the Josephus game.

Let J ( N ) be the winner of an N -player Josephus game with M = 1.
Show that
a.

13.6

If N is even, then J ( N ) = 2 J ( N / 2) - 1.

b. If N is odd and J ( ⎡ N /2 ⎤ ) ≠ 1, then J ( N ) = 2 J ( ⎡ N /2 ⎤ ) - 3.

c. If N is odd and J ( ⎡ N /2 ⎤ ) = 1, then J ( N ) = N .

Use the results in Exercise 13.6 to write an algorithm that returns the
winner of an N -player Josephus game with M = 1. What is the run-
ning time of your algorithm?

13.7