tailieunhanh - Ebook Data structures and problem solving using C++ (2/E): Part 2

Part 2 book “Data structures and problem solving using C++” has contents: Simulation, graphs and paths, stacks and queues, linked lists, trees, binary search trees, hash tables, a priority queue - The binary heap, splay trees, merging priority queues, the disjoint set class, and other contents. | Chapter 14 Simulation An important use of computers is for simulation, in which the computer is used to emulate the operation of a real system and gather statistics. For example, we might want to simulate the operation of a bank with k tellers to determine the minimum value of k that gives reasonable service time. Using a computer for this task has many advantages. First. the information would be gathered without involving real customers. Second, a simulation by computer can be faster than the actual implementation because of the speed of the computer. Third. the simulation could be easily replicated. In many cases, the proper choice of data structures can help us improve the efficiency of the simulation. In this chapter, we show: An important use of computers is simulation, in which the computer is used to emulate the operation of a real system and gather statistics. how to simulate a game modeled on the Joseph~lsproblern, and how to simulate the operation of a computer modem bank. The Josephus Problem The Josephus problem is the following game: N people, numbered 1 to N, are sitting in a circle; starting at person I , a hot potato is passed; after M passes, the person holding the hot potato is eliminated, the circle closes ranks. and the game continues with the person who was sitting after the eliminated person picking up the hot potato; the last remaining person wins. A common assumption is that M is a constant, although a random number generator can be used to change M after each elimination. The Josephus problem arose in the first century 4 . ~ in . a cave on a mountain in Israel where Jewish zealots were being besieged by Roman soldiers. The historian Josephus was among them. To Josephus's consternation. the zealots voted to enter into a suicide pact rather than surrender to the Romans. He suggested the game that now bears his name. The hot potato In the Josephus problem, a hot potato is repeatedly passed; when passing terminates, the player holding