Wrap-Up

Fill in the blanks in each of the following statements:

1. One-dimensional array p contains four elements. The names of those elements are __________, __________, __________ and __________.
2. Naming an array, stating its type and specifying the number of dimensions in the array is called __________ the array.
3. In a two-dimensional array, the first index identifies the __________ of an element and the second index identifies the __________ of an element.
4. An m-by-n array contains __________ rows, __________ columns and __________ elements.
5. The name of the element in row 3 and column 5 of array d is __________.

Determine whether each of the following is true or false. If false, explain why.

1. To refer to a particular location or element within an array, we specify the name of the array and the value of the particular element.
2. An array declaration reserves space for the array.
3. To indicate that 100 locations should be reserved for integer array p, the programmer writes the declaration

   p[ 100 ];

4. An application that initializes the elements of a 15-element array to zero must contain at least one for statement.
5. An application that totals the elements of a two-dimensional array must contain nested for statements.

Write Java statements to accomplish each of the following tasks:

1. Display the value of the seventh element of character array f.
2. Initialize each of the five elements of one-dimensional integer array g to 8.
3. Total the 100 elements of floating-point array c.
4. Copy 11-element array a into the first portion of array b, which contains 34 elements.
5. Determine and display the smallest and largest values contained in 99-element floating-point array w.

Consider a two-by-three integer array t.

1. Write a statement that declares and creates t.
2. How many rows does t have?
3. How many columns does t have?
4. How many elements does t have?
5. Write the names of all the elements in the second row of t.
6. Write the names of all the elements in the third column of t.
7. Write a single statement that sets the element of t in row 1 and column 2 to zero.
8. Write a series of statements that initializes each element of t to zero. Do not use a repetition statement.
9. Write a nested for statement that initializes each element of t to zero.
10. Write a nested for statement that inputs the values for the elements of t from the user.
11. Write a series of statements that determines and displays the smallest value in t.
12. Write a statement that displays the elements of the first row of t.
13. Write a statement that totals the elements of the third column of t.
14. Write a series of statements that displays the contents of t in tabular format. List the column indices as headings across the top, and list the row indices at the left of each row.

(Sales Commissions) Use a one-dimensional array to solve the following problem: A company pays its salespeople on a commission basis. The salespeople receive $200 per week plus 9% of their gross sales for that week. For example, a salesperson who grosses $5000 in sales in a week receives $200 plus 9% of $5000, or a total of $650. Write an application (using an array of counters) that determines how many of the salespeople earned salaries in each of the following ranges (assume that each salesperson's salary is truncated to an integer amount):

1. $200299
2. $300399
3. $400499
4. $500599
5. $600699
6. $700799
7. $800899
8. $900999
9. $1000 and over

Summarize the results in tabular format.

Write statements that perform the following one-dimensional-array operations:

1. Set the 10 elements of integer array counts to zero.
2. Add one to each of the 15 elements of integer array bonus.
3. Display the five values of integer array bestScores in column format.

(Duplicate Elimination) Use a one-dimensional array to solve the following problem: Write an application that inputs five numbers, each of which is between 10 and 100, inclusive. As each number is read, display it only if it is not a duplicate of a number already read. Provide for the "worst case," in which all five numbers are different. Use the smallest possible array to solve this problem. Display the complete set of unique values input after the user inputs each new value.

Label the elements of three-by-five two-dimensional array sales to indicate the order in which they are set to zero by the following program segment:

for ( int row = 0; row < sales.length; row++ ) { for ( int col = 0; col < sales[ row ].length; col++ ) { sales[ row ][ col ] = 0; } }

Write an application that calculates the product of a series of integers that are passed to method product using a variable-length argument list. Test your method with several calls, each with a different number of arguments.

Rewrite Fig. 7.2 so that the size of the array is specified by the first command-line argument. If no command-line argument is supplied, use 10 as the default size of the array.

Write an application that uses an enhanced for statement to sum the double values passed by the command-line arguments. [Hint: Use the static method parseDouble of class Double to convert a String to a double value.]

(Dice Rolling) Write an application to simulate the rolling of two dice. The application should use an object of class Random once to roll the first die and again to roll the second die. The sum of the two values should then be calculated. Each die can show an integer value from 1 to 6, so the sum of the values will vary from 2 to 12, with 7 being the most frequent sum and 2 and 12 being the least frequent sums. Figure 7.30 shows the 36 possible combinations of the two dice. Your application should roll the dice 36,000 times. Use a one-dimensional array to tally the number of times each possible sum appears. Display the results in tabular format. Determine whether the totals are reasonable (e.g., there are six ways to roll a 7, so approximately one-sixth of the rolls should be 7).

Figure 7.30. The 36 possible sums of two dice.

(Game of Craps) Write an application that runs 1000 games of craps (Fig. 6.9) and answers the following questions:

1. How many games are won on the first roll, second roll, ..., twentieth roll and after the twentieth roll?
2. How many games are lost on the first roll, second roll, ..., twentieth roll and after the twentieth roll?
3. What are the chances of winning at craps? [Note: You should discover that craps is one of the fairest casino games. What do you suppose this means?]
4. What is the average length of a game of craps?
5. Do the chances of winning improve with the length of the game?

(Airline Reservations System) A small airline has just purchased a computer for its new automated reservations system. You have been asked to develop the new system. You are to write an application to assign seats on each flight of the airline's only plane (capacity: 10 seats).

Your application should display the following alternatives: Please type 1 for First Class and Please type 2 for Economy. If the user types 1, your application should assign a seat in the first-class section (seats 15). If the user types 2, your application should assign a seat in the economy section (seats 610). Your application should then display a boarding pass indicating the person's seat number and whether it is in the first-class or economy section of the plane.

Use a one-dimensional array of primitive type boolean to represent the seating chart of the plane. Initialize all the elements of the array to false to indicate that all the seats are empty. As each seat is assigned, set the corresponding elements of the array to true to indicate that the seat is no longer available.

Your application should never assign a seat that has already been assigned. When the economy section is full, your application should ask the person if it is acceptable to be placed in the first-class section (and vice versa). If yes, make the appropriate seat assignment. If no, display the message "Next flight leaves in 3 hours."

(Total Sales) Use a two-dimensional array to solve the following problem: A company has four salespeople (1 to 4) who sell five different products (1 to 5). Once a day, each salesperson passes in a slip for each type of product sold. Each slip contains the following:

1. The salesperson number
2. The product number
3. The total dollar value of that product sold that day

Thus, each salesperson passes in between 0 and 5 sales slips per day. Assume that the information from all the slips for last month is available. Write an application that will read all this information for last month's sales and summarize the total sales by salesperson and by product. All totals should be stored in the two-dimensional array sales. After processing all the information for last month, display the results in tabular format, with each column representing a particular salesperson and each row representing a particular product. Cross-total each row to get the total sales of each product for last month. Cross-total each column to get the total sales by salesperson for last month. Your tabular output should include these cross-totals to the right of the totaled rows and to the bottom of the totaled columns.

(Turtle Graphics) The Logo language made the concept of turtle graphics famous. Imagine a mechanical turtle that walks around the room under the control of a Java application. The turtle holds a pen in one of two positions, up or down. While the pen is down, the turtle traces out shapes as it moves, and while the pen is up, the turtle moves about freely without writing anything. In this problem, you will simulate the operation of the turtle and create a computerized sketchpad.

Use a 20-by-20 array floor that is initialized to zeros. Read commands from an array that contains them. Keep track of the current position of the turtle at all times and whether the pen is currently up or down. Assume that the turtle always starts at position (0, 0) of the floor with its pen up. The set of turtle commands your application must process are shown in Fig. 7.31.

Suppose that the turtle is somewhere near the center of the floor. The following "program" would draw and display a 12-by-12 square, leaving the pen in the up position:

2 5,12 3 5,12 3 5,12 3 5,12 1 6 9  

As the turtle moves with the pen down, set the appropriate elements of array floor to 1s. When the 6 command (display the array) is given, wherever there is a 1 in the array, display an asterisk or any character you choose. Wherever there is a 0, display a blank.

Write an application to implement the turtle graphics capabilities discussed here. Write several turtle graphics programs to draw interesting shapes. Add other commands to increase the power of your turtle graphics language.

(Knight's Tour) One of the more interesting puzzlers for chess buffs is the Knight's Tour problem, originally proposed by the mathematician Euler. Can the chess piece called the knight move around an empty chessboard and touch each of the 64 squares once and only once? We study this intriguing problem in depth here.

The knight makes only L-shaped moves (two spaces in one direction and one space in a perpendicular direction). Thus, as shown in Fig. 7.32, from a square near the middle of an empty chessboard, the knight (labeled K) can make eight different moves (numbered 0 through 7).

Figure 7.32. The eight possible moves of the knight.

1. Draw an eight-by-eight chessboard on a sheet of paper, and attempt a Knight's Tour by hand. Put a 1 in the starting square, a 2 in the second square, a 3 in the third, and so on. Before starting the tour, estimate how far you think you will get, remembering that a full tour consists of 64 moves. How far did you get? Was this close to your estimate?
2. Now let us develop an application that will move the knight around a chessboard. The board is represented by an eight-by-eight two-dimensional array board. Each square is initialized to zero. We describe each of the eight possible moves in terms of their horizontal and vertical components. For example, a move of type 0, as shown in Fig. 7.32, consists of moving two squares horizontally to the right and one square vertically upward. A move of type 2 consists of moving one square horizontally to the left and two squares vertically upward. Horizontal moves to the left and vertical moves upward are indicated with negative numbers. The eight moves may be described by two one-dimensional arrays, horizontal and vertical, as follows:

   horizontal[ 0 ] = 2 vertical[ 0 ] = -1 horizontal[ 1 ] = 1 vertical[ 1 ] = -2 horizontal[ 2 ] = -1 vertical[ 2 ] = -2 horizontal[ 3 ] = -2 vertical[ 3 ] = -1 horizontal[ 4 ] = -2 vertical[ 4 ] = 1 horizontal[ 5 ] = -1 vertical[ 5 ] = 2 horizontal[ 6 ] = 1 vertical[ 6 ] = 2 horizontal[ 7 ] = 2 vertical[ 7 ] = 1

   Let the variables currentRow and currentColumn indicate the row and column, respectively, of the knight's current position. To make a move of type moveNumber, where moveNumber is between 0 and 7, your application should use the statements

   currentRow += vertical[ moveNumber ]; currentColumn += horizontal[ moveNumber ];

   Write an application to move the knight around the chessboard. Keep a counter that varies from 1 to 64. Record the latest count in each square the knight moves to. Test each potential move to see if the knight has already visited that square. Test every potential move to ensure that the knight does not land off the chessboard. Run the application. How many moves did the knight make?

3. After attempting to write and run a Knight's Tour application, you have probably developed some valuable insights. We will use these insights to develop a heuristic (or "rule of thumb") for moving the knight. Heuristics do not guarantee success, but a carefully developed heuristic greatly improves the chance of success. You may have observed that the outer squares are more troublesome than the squares nearer the center of the board. In fact, the most troublesome or inaccessible squares are the four corners.

   Intuition may suggest that you should attempt to move the knight to the most troublesome squares first and leave open those that are easiest to get to, so that when the board gets congested near the end of the tour, there will be a greater chance of success.

   We could develop an "accessibility heuristic" by classifying each of the squares according to how accessible it is and always moving the knight (using the knight's L-shaped moves) to the most inaccessible square. We label a two-dimensional array accessibility with numbers indicating from how many squares each particular square is accessible. On a blank chessboard, each of the 16 squares nearest the center is rated as 8, each corner square is rated as 2, and the other squares have accessibility numbers of 3, 4 or 6 as follows:

     2 3 4 4 4 4 3 2 3 4 6 6 6 6 4 3 4 6 8 8 8 8 6 4 4 6 8 8 8 8 6 4 4 6 8 8 8 8 6 4 4 6 8 8 8 8 6 4 3 4 6 6 6 6 4 3 2 3 4 4 4 4 3 2

   Write a new version of the Knight's Tour, using the accessibility heuristic. The knight should always move to the square with the lowest accessibility number. In case of a tie, the knight may move to any of the tied squares. Therefore, the tour may begin in any of the four corners. [Note: As the knight moves around the chessboard, your application should reduce the accessibility numbers as more squares become occupied. In this way, at any given time during the tour, each available square's accessibility number will remain equal to precisely the number of squares from which that square may be reached.] Run this version of your application. Did you get a full tour? Modify the application to run 64 tours, one starting from each square of the chessboard. How many full tours did you get?

4. Write a version of the Knight's Tour application that, when encountering a tie between two or more squares, decides what square to choose by looking ahead to those squares reachable from the "tied" squares. Your application should move to the tied square for which the next move would arrive at a square with the lowest accessibility number.

(Knight's Tour: Brute-Force Approaches) In part (c) of Exercise 7.22, we developed a solution to the Knight's Tour problem. The approach used, called the "accessibility heuristic," generates many solutions and executes efficiently.

As computers continue to increase in power, we will be able to solve more problems with sheer computer power and relatively unsophisticated algorithms. Let us call this approach "brute-force" problem solving.

1. Use random-number generation to enable the knight to walk around the chessboard (in its legitimate L-shaped moves) at random. Your application should run one tour and display the final chessboard. How far did the knight get?
2. Most likely, the application in part (a) produced a relatively short tour. Now modify your application to attempt 1000 tours. Use a one-dimensional array to keep track of the number of tours of each length. When your application finishes attempting the 1000 tours, it should display this information in neat tabular format. What was the best result?
3. Most likely, the application in part (b) gave you some "respectable" tours, but no full tours. Now let your application run until it produces a full tour. (Caution: This version of the application could run for hours on a powerful computer.) Once again, keep a table of the number of tours of each length, and display this table when the first full tour is found. How many tours did your application attempt before producing a full tour? How much time did it take?
4. Compare the brute-force version of the Knight's Tour with the accessibility-heuristic version. Which required a more careful study of the problem? Which algorithm was more difficult to develop? Which required more computer power? Could we be certain (in advance) of obtaining a full tour with the accessibility-heuristic approach? Could we be certain (in advance) of obtaining a full tour with the brute-force approach? Argue the pros and cons of brute-force problem solving in general.

(Eight Queens) Another puzzler for chess buffs is the Eight Queens problem, which asks the following: Is it possible to place eight queens on an empty chessboard so that no queen is "attacking" any other (i.e., no two queens are in the same row, in the same column or along the same diagonal)? Use the thinking developed in Exercise 7.22 to formulate a heuristic for solving the Eight Queens problem. Run your application. (Hint: It is possible to assign a value to each square of the chessboard to indicate how many squares of an empty chessboard are "eliminated" if a queen is placed in that square. Each of the corners would be assigned the value 22, as demonstrated by Fig. 7.33. Once these "elimination numbers" are placed in all 64 squares, an appropriate heuristic might be as follows: Place the next queen in the square with the smallest elimination number. Why is this strategy intuitively appealing?

Figure 7.33. The 22 squares eliminated by placing a queen in the upper left corner.

(Eight Queens: Brute-Force Approaches) In this exercise, you will develop several brute-force approaches to solving the Eight Queens problem introduced in Exercise 7.24.

1. Use the random brute-force technique developed in Exercise 7.23 to solve the Eight Queens problem.
2. Use an exhaustive technique (i.e., try all possible combinations of eight queens on the chessboard) to solve the Eight Queens problem.
3. Why might the exhaustive brute-force approach not be appropriate for solving the Knight's Tour problem?
4. Compare and contrast the random brute-force and exhaustive brute-force approaches.

(Knight's Tour: Closed-Tour Test) In the Knight's Tour (Exercise 7.22), a full tour occurs when the knight makes 64 moves, touching each square of the chessboard once and only once. A closed tour occurs when the 64th move is one move away from the square in which the knight started the tour. Modify the application you wrote in Exercise 7.22 to test for a closed tour if a full tour has occurred.

(Sieve of Eratosthenes) A prime number is any integer greater than one that is evenly divisible only by itself and 1. The Sieve of Eratosthenes is a method of finding prime numbers. It operates as follows:

1. Create a primitive type boolean array with all elements initialized to true. Array elements with prime indices will remain TRue. All other array elements will eventually be set to false.
2. Starting with array index 2, determine whether a given element is TRue. If so, loop through the remainder of the array and set to false every element whose index is a multiple of the index for the element with value TRue. Then continue the process with the next element with value true. For array index 2, all elements beyond element 2 in the array that have indices which are multiples of 2 (indices 4, 6, 8, 10, etc.) will be set to false; for array index 3, all elements beyond element 3 in the array that have indices which are multiples of 3 (indices 6, 9, 12, 15, etc.) will be set to false; and so on.

When this process completes, the array elements that are still TRue indicate that the index is a prime number. These indices can be displayed. Write an application that uses an array of 1000 elements to determine and display the prime numbers between 2 and 999. Ignore array elements 0 and 1.

(Simulation: The Tortoise and the Hare) In this problem, you will re-create the classic race of the tortoise and the hare. You will use random-number generation to develop a simulation of this memorable event.

Our contenders begin the race at square 1 of 70 squares. Each square represents a possible position along the race course. The finish line is at square 70. The first contender to reach or pass square 70 is rewarded with a pail of fresh carrots and lettuce. The course weaves its way up the side of a slippery mountain, so occasionally the contenders lose ground.

A clock ticks once per second. With each tick of the clock, your application should adjust the position of the animals according to the rules in Fig. 7.34. Use variables to keep track of the positions of the animals (i.e., position numbers are 170). Start each animal at position 1 (the "starting gate"). If an animal slips left before square 1, move it back to square 1.

Generate the percentages in Fig. 7.34 by producing a random integer i in the range 1 10. For the tortoise, perform a "fast plod" when 1 images/U2264.jpg border=0> 5, a "slip" when 6 images/U2264.jpg border=0> 7 or a "slow plod" when 8 images/U2264.jpg border=0> images/U2264.jpg border=0> 10. Use a similar technique to move the hare.

Begin the race by displaying

BANG !!!!! AND THEY'RE OFF !!!!!  

Then, for each tick of the clock (i.e., each repetition of a loop), display a 70-position line showing the letter T in the position of the tortoise and the letter H in the position of the hare. Occasionally, the contenders will land on the same square. In this case, the tortoise bites the hare, and your application should display OUCH!!! beginning at that position. All output positions other than the T, the H or the OUCH!!! (in case of a tie) should be blank.

After each line is displayed, test for whether either animal has reached or passed square 70. If so, display the winner and terminate the simulation. If the tortoise wins, display TORTOISE WINS!!! YAY!!! If the hare wins, display Hare wins. Yuch. If both animals win on the same tick of the clock, you may want to favor the tortoise (the "underdog"), or you may want to display It's a tie. If neither animal wins, perform the loop again to simulate the next tick of the clock. When you are ready to run your application, assemble a group of fans to watch the race. You'll be amazed at how involved your audience gets!

Later in the book, we introduce a number of Java capabilities, such as graphics, images, animation, sound and multithreading. As you study those features, you might enjoy enhancing your tortoise-and-hare contest simulation.

(Fibonacci Series) The Fibonacci series

0, 1, 1, 2, 3, 5, 8, 13, 21, ...

begins with the terms 0 and 1 and has the property that each succeeding term is the sum of the two preceding terms.

1. Write a method fibonacci( n ) that calculates the nth Fibonacci number. Incorporate this method into an application that enables the user to enter the value of n.
2. Determine the largest Fibonacci number that can be displayed on your system.
3. Modify the application you wrote in part (a) to use double instead of int to calculate and return Fibonacci numbers, and use this modified application to repeat part (b).

Exercise 7.30Exercise 7.33 are reasonably challenging. Once you have done these problems, you ought to be able to implement most popular card games easily.

(Card Shuffling and Dealing) Modify the application of Fig. 7.11 to deal a five-card poker hand. Then modify class DeckOfCards of Fig. 7.10 to include methods that determine whether a hand contains

1. a pair
2. two pairs
3. three of a kind (e.g., three jacks)
4. four of a kind (e.g., four aces)
5. a flush (i.e., all five cards of the same suit)
6. a straight (i.e., five cards of consecutive face values)
7. a full house (i.e., two cards of one face value and three cards of another face value)

[Hint: Add methods getFace and getSuit to class Card of Fig. 7.9.]

(Card Shuffling and Dealing) Use the methods developed in Exercise 7.30 to write an application that deals two five-card poker hands, evaluates each hand and determines which is the better hand.

(Card Shuffling and Dealing) Modify the application developed in Exercise 7.31 so that it can simulate the dealer. The dealer's five-card hand is dealt "face down," so the player cannot see it. The application should then evaluate the dealer's hand, and, based on the quality of the hand, the dealer should draw one, two or three more cards to replace the corresponding number of unneeded cards in the original hand. The application should then reevaluate the dealer's hand. [Caution: This is a difficult problem!]

(Card Shuffling and Dealing) Modify the application developed in Exercise 7.32 so that it can handle the dealer's hand automatically, but the player is allowed to decide which cards of the player's hand to replace. The application should then evaluate both hands and determine who wins. Now use this new application to play 20 games against the computer. Who wins more games, you or the computer? Have a friend play 20 games against the computer. Who wins more games? Based on the results of these games, refine your poker-playing application. (This, too, is a difficult problem.) Play 20 more games. Does your modified application play a better game?