Recursion - Data Structures and Problem Solving Using Java - page 333

1 // Dynamic programming algorithm to solve change-making problem.
2 // As a result, the coinsUsed array is filled with the
3 // minimum number of coins needed for change from 0 -> maxChange
4 // and lastCoin contains one of the coins needed to make the change.
5 public static void makeChange( int [ ] coins, int differentCoins,
6 int maxChange, int [ ] coinsUsed, int [ ] lastCoin )
7 {
8 coinsUsed[ 0 ] = 0; lastCoin[ 0 ] = 1;
9
10 for( int cents = 1; cents <= maxChange; cents++ )
11 {
12 int minCoins = cents;
13 int newCoin = 1;
14
15 for( int j = 0; j < differentCoins; j++ )
16 {
17 if( coins[ j ] > cents ) // Cannot use coin j
18 continue;
19 if( coinsUsed[ cents - coins[ j ] ] + 1 < minCoins )
20 {
21 minCoins = coinsUsed[ cents - coins[ j ] ] + 1;
22 newCoin = coins[ j ];
23 }
24 }
25
26 coinsUsed[ cents ] = minCoins;
27 lastCoin[ cents ] = newCoin;
28 }
29 }

figure 7.25
A dynamic programming algorithm for solving the change-making problem by computing
optimal change for all amounts from 0 to maxChange and maintaining information to construct
the actual coin sequence

backtracking

7.7

In this section we set out the last application of recursion. We show how to
write a routine to have the computer select an optimal move in the game Tic-
Tac-Toe. The class Best , shown in Figure 7.26, is used to store the optimal
move that is returned by the move selection algorithm. The skeleton for a Tic-
TacToe class is shown in Figure 7.27. The class has a data object board that rep-
resents the current game position. 6

A backtracking
algorithm uses
recursion to try all
the possibilities.

A host of trivial methods are specified,

6. Tic-Tac-Toe is played on a three-by-three board. Two players alternate placing their sym-
bols on squares. The first to get three squares in a row, column, or a long diagonal wins.