15.33 |
Implement the game of Nine Men's Morris (Figure 15-41). |

15.34 |
Implement the game of Aggression (Figure 15-42). Generate the board randomly, so that a city has a 50% chance of being connected to each of the cities next to it horizontally, vertically, or diagonally. |

Nine Men's Morris |
---|

Players: 2 |

Object: To either reduce the opponent to two pieces or to leave the opponent with no legal move. |

Board: See below. The pieces (merels) are placed on the dots (points) and moved along the lines to adjacent points. Each player gets nine merels in her color. The board is initially empty. |

Play: Players take turns. On a turn, a player places a merel on an unoccupied point. If a player has no merels left to place, she instead moves one of her merels to an adjacent point. |

Capture: If a player's move causes three of her merels to be in a horizontal or vertical line through adjacent points, she has formed a mill. She gets to remove any one of the opponent's merels from the board. If possible, she must choose a merel which is not currently part of a mill. The removed merel is discarded; the opponent does not get it back. |

Game End: The game ends when one player either has only two merels or has no legal move. This player loses. |

Aggression |
---|

Players: 2, black and white. |

Object: To control the most cities at the end of the game. |

Board: There are 20 cities and some roads on the board. Two cities are adjacent if they are connected by a single road segment. The board may be different in each game. A typical board is shown below. |

Setup: The board is initially empty. Each player starts with 100 troops. In turns, each player places one or more troops in any unoccupied city to claim it. This continues until all cities have been claimed or both players have deployed all of their troops. An example is shown below. |

Play: Taking turns, each player chooses a city to attack. The attack is successful if the number of troops in the city is less than the number of opposing troops in adjacent cities. After a successful attack, the defending troops are removed and the city becomes neutral. The attacking troops are unaffected. An unsuccessful attack has no effect. |

As an example, in the game above, black could successfully attack the upper white 20 (with 45 adjacent troops), but not the lower white 20 (with only 15 adjacent troops). |

Game End: The game ends when either one player has no troops left or there are no successful attacks left to make. The player controlling the most cities wins. |

Part I: Object-Oriented Programming

Encapsulation

Polymorphism

Inheritance

- Inheritance
- Extending a Class
- The Object Class
- Packages and Access Levels
- Summary
- Vocabulary
- Problems
- Projects

Part II: Linear Structures

Stacks and Queues

- Stacks and Queues
- The Stack Interface
- The Call Stack
- Exceptions
- The Queue Interface
- Summary
- Vocabulary
- Problems
- Projects

Array-Based Structures

- Array-Based Structures
- Shrinking and Stretching Arrays
- Implementing Stacks and Queues
- The List Interface
- Iterators
- The Java Collections Framework: A First Look
- Summary
- Vocabulary
- Problems
- Projects

Linked Structures

- Linked Structures
- List Nodes
- Stacks and Queues
- The LinkedList Class
- The Java Collections Framework Revisited
- Summary
- Vocabulary
- Problems
- Projects

Part III: Algorithms

Analysis of Algorithms

- Analysis of Algorithms
- Timing
- Asymptotic Notation
- Counting Steps
- Best, Worst, and Average Case
- Amortized Analysis
- Summary
- Vocabulary
- Problems
- Projects

Searching and Sorting

- Searching and Sorting
- Linear Search
- Binary Search
- Insertion Sort
- The Comparable Interface
- Sorting Linked Lists
- Summary
- Vocabulary
- Problems
- Projects

Recursion

- Recursion
- Thinking Recursively
- Analyzing Recursive Algorithms
- Merge Sort
- Quicksort
- Avoiding Recursion
- Summary
- Vocabulary
- Problems
- Projects

Part IV: Trees and Sets

Trees

Sets

- Sets
- The Set Interface
- Ordered Lists
- Binary Search Trees
- Hash Tables
- The Java Collections Framework Again
- Summary
- Vocabulary
- Problems
- Projects

Part V: Advanced Topics

Advanced Linear Structures

- Advanced Linear Structures
- Bit Vectors
- Sparse Arrays
- Contiguous Representation of Multidimensional Arrays
- Advanced Searching and Sorting
- Summary
- Vocabulary
- Problems
- Projects

Strings

Advanced Trees

- Advanced Trees
- Heaps
- Disjoint Set Clusters
- Digital Search Trees
- Red-Black Trees
- Summary
- Vocabulary
- Problems
- Projects

Graphs

- Graphs
- Terminology
- Representation
- Graph Traversal
- Topological Sorting
- Shortest Paths
- Minimum Spanning Trees
- Summary
- Vocabulary
- Problems
- Projects

Memory Management

Out to the Disk

- Out to the Disk
- Interacting with Files
- Compression
- External Sorting
- B-Trees
- Summary
- Vocabulary
- Problems
- Projects

Part VI: Appendices

A. Review of Java

- A. Review of Java
- A.1. The First Program
- A.2. Variables and Types
- A.3. Loops
- A.4. Interacting with the User
- A.5. Branching
- A.6. Methods and Breaking Out
- A.7. Constants
- A.8. Operators
- A.9. Debugging
- A.10. Coding Conventions

B. Unified Modeling Language

C. Summation Formulae

- C. Summation Formulae
- C.1. Sum Notation
- C.2. Sum of Constants
- C.3. Sum of First n Integers
- C.4. Sums of Halves and Doubles
- C.5. Upper Limit on Sum of a Function
- C.6. Constant Factors

D. Further Reading

Index

Data Structures and Algorithms in Java

ISBN: 0131469142

EAN: 2147483647

EAN: 2147483647

Year: 2004

Pages: 216

Pages: 216

Authors: Peter Drake

Flylib.com © 2008-2020.

If you may any questions please contact us: flylib@qtcs.net

If you may any questions please contact us: flylib@qtcs.net