6.15. Programming Exercises | Introduction to Java Programming-Comprehensive Version (6th Edition)

[Page 204 ( continued )]

Programming Exercises

Section 6.2 Array Basics

6.1	( Analyzing input ) Write a program that reads ten numbers, computes their average, and finds out how many numbers are above the average.
6.2	( Alternative solution to Listing 6.1, TestArray.java ) The solution of Listing 6.1 counts the occurrences of the largest number by comparing each number with the largest. So you have to use an array to store all the numbers. Another way to solve the problem is to maintain two variables , max and count . max stores the current max number, and count stores its occurrences. Initially, assign the first number to max and 1 to count . Compare each subsequent number with max . If the number is greater than max , assign it to max and reset count to 1 . If the number is equal to max , increment count by 1 . Use this approach to rewrite Listing 6.1.
6.3	( Reversing the numbers entered ) Write a program that reads ten integers and displays them in the reverse of the order in which they were read.
6.4	( Analyzing scores ) Write a program that reads an unspecified number of scores and determines how many scores are above or equal to the average and how many scores are below the average. Enter a negative number to signify the end of the input. Assume that the maximum number of scores is 100 .
6.5**	( Printing distinct numbers ) Write a program that reads in ten numbers and displays distinct numbers (i.e., if a number appears multiple times, it is displayed only once). Hint: Read a number and store it to an array if it is new. If the number is already in the array, discard it. After the input, the array contains the distinct numbers.
[Page 205]
6.6*	( Revising Listing 4.11, PrimeNumber.java ) Listing 4.11 determines whether a number n is prime by checking whether 2 , 3 , 4 , 5 , 6 , ..., n/2 is a divisor. If a divisor is found, n is not prime. A more efficient approach to determine whether n is prime is to check whether any of the prime numbers less than or equal to can divide n evenly. If not, n is prime. Rewrite Listing 4.11 to display the first fifty prime numbers using this approach. You need to use an array to store the prime numbers and later use them to check whether they are possible divisors for n .
6.7*	( Counting single digits ) Write a program that generates one hundred random integers between and 9 and displays the count for each number. Hint: Use (int)(Math.random() * 10) to generate a random integer between and 9 . Use an array of ten integers, say counts , to store the counts for the number of 's, 1 's, ..., 9 's.

Sections 6.4 “6.5

6.8	( Averaging an array ) Write two overloaded methods that return the average of an array with the following headers: public static int average( int [] array); public static double average( double [] array); Use { 1 , 2 , 3 , 4 , 5 , 6 } and { 6.0 , 4.4 , 1.9 , 2.9 , 3.4 , 3.5 } to test the methods.
6.9	( Finding the smallest element ) Write a method that finds the smallest element in an array of integers. Use { 1 , 2 , 4 , 5 , 10 , 100 , 2 , “22 } to test the method.
6.10	( Finding the index of the smallest element ) Write a method that returns the index of the smallest element in an array of integers. If there are more than one such elements, return the smallest index. Use { 1 , 2 , 4 , 5 , 10 , 100 , 2 , “22 } to test the method.
6.11*	( Computing deviation ) Exercise 5.21 computes the standard deviation of numbers. This exercise uses a different but equivalent formula to compute the standard deviation of n numbers. To compute deviation with this formula, you have to store the individual numbers using an array, so that they can be used after the mean is obtained. Use {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} to test the method.
6.12*	( Reversing an array ) The reverse method in §6.5 reverses an array by copying it to a new array. Rewrite the method without creating new arrays.
6.13*	( Increasing array size ) Once an array is created, its size is fixed. Occasionally, you need to add more values to an array, but it is full. In such cases, you can create a new, larger array to replace the existing array. Write a method with the following header: public static int [] doubleCapacity( int [] list) The method returns a new array that doubles the size of the parameter list .

Section 6.6 Variable-Length Argument Lists

6.14

( Computing average ) Write a method that returns the average of an unspecified number of numeric arguments.

[Page 206]

Sections 6.7 “6.9

6.15	( Finding the sales amount ) Rewrite Listing 4.7, FindSalesAmount.java, using the binary search approach. Since the sales amount is between 1 and COMMISSION_SOUGHT/0.08 , you can use a binary search to improve Listing 4.7.
6.16	( Timing execution ) Write a program that randomly generates an array of 100000 integers and a key. Estimate the execution time of invoking the linearSearch method in Listing 6.6. Sort the array and estimate the execution time of invoking the binarySearch method in Listing 6.7. You can use the following code template to obtain the execution time: long startTime = System.currentTimeMillis(); perform the task; long endTime = System.currentTimeMillis(); long executionTime = endTime - startTime;
6.17*	( Revising selection sort ) In §6.8, you used selection sort to sort an array. The selection sort method repeatedly finds the largest number in the current array and swaps it with the last number in the array. Rewrite this example by finding the smallest number and swapping it with the first number in the array.
6.18**	( Bubble sort ) Write a sort method that uses the bubble-sort algorithm. The bubble-sort algorithm makes several passes through the array. On each pass, successive neighboring pairs are compared. If a pair is in decreasing order, its values are swapped; otherwise , the values remain unchanged. The technique is called a bubble sort or sinking sort because the smaller values gradually "bubble" their way to the top and the larger values sink to the bottom. The algorithm can be described as follows : boolean changed = true ; do { changed = false ; for ( int j = ; j < list.length - 1 ; j++) if (list[j] > list[j + 1 ]) { swap list[j] with list[j + 1 ]; changed = true ; } } while (changed); Clearly, the list is in increasing order when the loop terminates. It is easy to show that the do loop executes at most list.length “1 times. Use { 6.0 , 4.4 , 1.9 , 2.9 , 3.4 , 2.9 , 3.5 } to test the method.
6.19**	( Sorting students ) Write a program that prompts the user to enter the number of students, and student names and their scores, and prints the student names in decreasing order of their scores.

Section 6.10 Two “Dimensional Arrays

6.20*	( Summing all the numbers in a matrix ) Write a method that sums all the integers in a matrix of integers. Use {{ 1 , 2 , 4 , 5 }, { 6 , 7 , 8 , 9 }, { 10 , 11 , 12 , 13 }, { 14 , 15 , 16 , 17 }} to test the method.
[Page 207]
6.21*	( Summing the major diagonal in a matrix ) Write a method that sums all the integers in the major diagonal in a matrix of integers. Use {{ 1 , 2 , 4 , 5 }, { 6 , 7 , 8 , 9 }, { 10 , 11 , 12 , 13 }, { 14 , 15 , 16 , 17 }} to test the method.
6.22*	( Sorting students on grades ) Rewrite Listing 6.10, GradeExam.java, to display the students in increasing order of the number of correct answers.
6.23*	( Computing the weekly hours for each employee ) Suppose the weekly hours for all employees are stored in a two-dimensional array. Each row records an employee's seven-day work hours with seven columns . For example, the following array stores the work hours for eight employees. Write a program that displays employees and their total hours in decreasing order of the total hours.
6.24	( Adding two matrices ) Write a method to add two matrices. The header of the method is as follows: public static int [][] addMatrix( int [][] a, int [][] b) In order to be added, the two matrices must have the same dimensions and the same or compatible types of elements. As shown below, two matrices are added by adding the two elements of the arrays with the same index:
6.25**	( Multiplying two matrices ) Write a method to multiply two matrices. The header of the method is as follows: public static int [][] multiplyMatrix( int [][] a, int [][] b) [Page 208] To multiply matrix a by matrix b , the number of columns in a must be the same as the number of rows in b , and the two matrices must have elements of the same or compatible types. Let c be the result of the multiplication, and a , b , and c are denoted as follows: where c _ij = a _{i 1} x b _{1 j} x + a _{i 2} x b _{2 j} x + a _{i 3} x b _{3 j} x + a _{i 4} x b _{4 j} x + a _{i 5} x b _{5 j} .
6.26*	( TicTacToe board ) Write a program that randomly fills in s and 1 s into a TicTacToe board, prints the board, and finds the rows, columns, or diagonals with all s or 1 s. Use a two-dimensional array to represent a TicTacToe board. Here is a sample run of the program: 001 001 111 All 0's on row 0 All 1's on row 2 All 1's on column 2
6.27**	( Checker board ) Write a program that randomly fills in s and 1 s into an 8 x 8 checker board, prints the board, and finds the rows, columns, or diagonals with all s or 1 s. Use a two-dimensional array to represent a checker board. Here is a sample run of the program: 10101000 10100001 11100011 10100001 11100111 10000001 10100111 00100001 All 0's on subdiagonal
6.28***	( Playing a TicTacToe game ) In a game of TicTacToe, two players take turns marking an available cell in a 3 x 3 grid with their respective tokens (either X or O). When one player has placed three tokens in a horizontal, vertical, or diagonal row on the grid, the game is over and that player has won. A draw (no winner) occurs when all the cells on the grid have been filled with tokens and neither player has achieved a win. Create a program for playing TicTacToe, as follows: The program prompts the first player to enter an X token, and then prompts the second player to enter an O token. Whenever a token is entered, the program refreshes the board and determines the status of the game (win, draw, or unfinished ). [Page 209] To place a token, display two dialog boxes to prompt the user to enter the row and the column for the token.
6.29***	( Least common multiple ) Write a program that prompts the user to enter two integers and finds their least common multiple (LCM). The LCM of two numbers is the smallest number that is a multiple of both. For example, the LCM for 8 and 12 is 24 , for 15 and 25 it is 75 , and for 120 and 150 it is 600 . There are many ways to find the LCM. In this exercise, you will use the approach described as follows: To find the LCM of two numbers, first create a prime factor table for each number. The first column of the table consists of all the prime factors, and the second column tracks the occurrence of the corresponding prime factor in the number. For example, the prime factors for 120 are 2 , 2 , 2 , 3 , 5 , so the prime factor table for number 120 is shown as follows: The prime factors for 150 are 2 , 3 , 5 , 5 , so the prime factor table for number 150 is shown as follows: The LCM of the two numbers consists of the factors with the most frequent occurrence in the two numbers. So the LCM for 120 and 150 is 2 x 2 x 2 x 3 x 5 x 5 , where 2 appears three times in 120 , 3 one time in 120 , and 5 two times in 150.

Hint

The prime factor table can be represented using a two-dimensional array. Write a method named getPrimeFactors(int number) that returns a two-dimensional array for the prime factor table.

[Page 210]