2008级计算机专业数据结构课堂教学笔记 内部资料,仅供课堂教学使用 5.2.4 Calculating Factorials Recursive; Nonrecursive; Example: P 177 Fibonacci Numbers Definition: Recursive function: Nonrecursive function P. 178-179 5.3 Backtracking: Postponing the Work Eight Queens Puzzle P183 Four Queens Solution P 184 Program Outline Recursive function: P 184 Main program Methods in the queens Class P 187 The Backtracking Function P The first Data Structure P 188 Sample Results P 191 void Queens insert(int col) P. 189 Queens Queens(int size) P.189 bool Queens : unguarded( int col) const P. 191 Components of a Chessboard P 190 Revised data structures p193 Sample results P.194 Class Declaration P. 193 Constructor P.193 Insertion P.193 Recursion tree P 195 5.4 Tree-Structured Programs: Look-Ahead in Games P.198 5. 4.1 Game Trees P 198 5.4.3 Algorithm Development P201 Use two classes called Move and Board. A Move object represents a single game move. A Board object represents a single game position The class Move requires only constructor methods The class board requires methods to initialize the board, to detect whether the game is over, to play a move that is passed as a parameter, to evaluate a position, and to supply a list of all current legal moves The method legal moves uses a stack to return the current move options The method better uses two integer parameters and returns a nonzero result if the(current) mover would prefer a game value given by the first rather than the second parameter The method worst case returns a constant value that the mover would like less than the value of any possible game position class board: P202 5.4.4 Look-Ahead algorithm P203 5.4.5 Tic-Tac-Toe P204 o The tic-tac-toe grid is a 3x3 array of integers, with0 to denote an empty square and the values I and 2 to denote squares occupied by the first and second players, respectively A Move object stores the coordinates of a square on the gri The board class contains private data members to record the current game state in a 3 x 3 array and to record how many moves have been played The game is finished either after nine moves have been played or when one or the other player has actually won The legal moves available for a player are just the squares with a value of o e Evaluate a Board position as O if neither player has yet won; however, if one or other player has won, we shall evaluate the position according to the rule that quick wins are considered very good, and quick losses are considered very bad a program that sets the depth of look-ahead to a value of 9 or more will play a perfect game, since it will al ways be able to look ahead to a situation where its evaluation of the position is exact. A program with shallower depth can make mistakes, because it might finish its look-ahead with a collection of positions2008 级 计算机专业 数据结构 课堂教学笔记 内部资料，仅供课堂教学使用 5.2.4Calculating Factorials Recursive; Nonrecursive; Example: P. 177 Fibonacci Numbers Definition; Recursive function; Nonrecursive function: P. 178-179 [5.3] Backtracking: Postponing the Work Eight Queens Puzzle P. 183 Four Queens Solution P. 184 Program Outline Recursive function: P. 184 Main program: P. 186 Methods in the Queens Class P. 187 The Backtracking Function P. 188 The First Data Structure P. 188 Sample Results P. 191 void Queens :: insert(int col) P. 189 Queens :: Queens(int size) P. 189 bool Queens :: unguarded(int col) const P. 191 Components of a Chessboard P. 190 Revised Data Structures P. 193 Sample Results P. 194 Class Declaration P. 193 Constructor P. 193 Insertion P. 193 Recursion Tree P . 195 [5.4] Tree-Structured Programs: Look-Ahead in Games P. 198 5.4.1 Game Trees P. 198 5.4.3 Algorithm Development P. 201 Use two classes called Move and Board. A Move object represents a single game move. A Board object represents a single game position. The class Move requires only constructor methods. The class Board requires methods to initialize the Board, to detect whether the game is over, to play a move that is passed as a parameter, to evaluate a position, and to supply a list of all current legal moves. The method legal_moves uses a stack to return the current move options. The method better uses two integer parameters and returns a nonzero result if the (current) mover would prefer a game value given by the first rather than the second parameter. The method worst_case returns a constant value that the mover would like less than the value of any possible game position. class Board: P. 202 5.4.4 Look-Ahead Algorithm P. 203 5.4.5 Tic-Tac-Toe P. 204 ⚫ The tic-tac-toe grid is a 3×3 array of integers, with 0 to denote an empty square and the values 1 and 2 to denote squares occupied by the first and second players, respectively. ⚫ A Move object stores the coordinates of a square on the grid. ⚫ The Board class contains private data members to record the current game state in a 3 × 3 array and to record how many moves have been played. ⚫ The game is finished either after nine moves have been played or when one or the other player has actually won. ⚫ The legal moves available for a player are just the squares with a value of 0. ⚫ Evaluate a Board position as 0 if neither player has yet won; however, if one or other player has won, we shall evaluate the position according to the rule that quick wins are considered very good, and quick losses are considered very bad. ⚫ A program that sets the depth of look-ahead to a value of 9 or more will play a perfect game, since it will always be able to look ahead to a situation where its evaluation of the position is exact. A program with shallower depth can make mistakes, because it might finish its look-ahead with a collection of positions