Mysql, Java, Jsp, Servlet, Tomcat, Ssh, Shared Web Hosting Blog

368 Arrays Chapter 7 RECURSION EXERCISES 7.29 (Selection Sort) A selection sort searches an array looking for the smallest element in the array, then swaps that element with the first element of the array. The process is repeated for the sub- array beginning with the second element. Each pass of the array places one element in its proper location. For an array of n elements, n - 1 passes must be made, and for each subarray, n - 1 comparisons must be made to find the smallest value. When the subarray being processed contains one element, the array is sorted. Write recursive method selectionSortto perform this algorithm. 7.30 (Palindromes) A palindrome is a string that is spelled the same way forward and backward. Some examples of palindromes are radar, able was i ere i saw elba and (if blanks are ignored) a man a plan a canal panama. Write a recursive method testPalindrome that returns boolean value true if the string stored in the array is a palindrome and false otherwise. The method should ignore spaces and punctuation in the string. [Hint: Use String method toCharArray, which takes no arguments, to get a char array containing the characters in the String. Then, pass the array to method testPalindrome.] 7.31 (Linear Search) Modify Figure 7.12 to use recursive method linearSearch to perform a linear search of the array. The method should receive an integer array, the array size and the search key as arguments. If the search key is found, return the array subscript; otherwise, return 1. 7.32 (Binary Search) Modify the program of Figure 7.13 to use a recursive method binary- Search to perform the binary search of the array. The method should receive an integer array and the starting subscript and ending subscript as arguments. If the search key is found, return the array subscript; otherwise, return 1. 7.33 (Eight Queens) Modify the Eight Queens program you created in Exercise 7.24 to solve the problem recursively. 7.34 (Print an array) Write a recursive method printArray that takes an array of int values and the size of the array as arguments and returns nothing. The method should stop processing and return when it receives an array of size 0. 7.35 (Print a string backward) Write a recursive method stringReversethat takes a character array containing a string as an argument, prints the string backward and returns nothing. 7.36 (Find the minimum value in an array) Write a recursive method recursiveMinimumthat takes an integer array and the array size as arguments and returns the smallest element of the array. The method should stop processing and return when it receives an array of one element. 7.37 (Quicksort) In the examples and exercises of this chapter, we discussed the sorting techniques bubble sort, bucket sort and selection sort. We now present the recursive sorting technique called Quicksort. The basic algorithm for a single-subscripted array of values is as follows: a) Partitioning Step: Take the first element of the unsorted array and determine its final location in the sorted array (i.e., all values to the left of the element in the array are less than the element, and all values to the right of the element in the array are greater than the element). We now have one element in its proper location and two unsorted subarrays. b) Recursive Step: Perform step 1 on each unsorted subarray. Each time step 1 is performed on a subarray, another element is placed in its final location of the sorted array and two unsorted subarrays are created. When a subarray consists of one element, it must be sorted therefore, that element is in its final location. The basic algorithm seems simple enough, but how do we determine the final position of the first element of each subarray? As an example, consider the following set of values (the element in bold is the partitioning element it will be placed in its final location in the sorted array): 37 2 6 4 89 8 10 12 68 45 Copyright 1992 2002 by Deitel & Associates, Inc. All Rights Reserved. 7/3/01
Note: In case you are looking for affordable and reliable webhost to host and run your business application check Vision php5 hosting services

Chapter 7 Arrays 367 * * * * * * * * * * * * * * * * * * * * * * Fig. 7.3131 The 22 squares eliminated by placing a queen in the upper left corner. Fig. a) Create a primitive type booleanarray with all elements initialized to true. Array elements with prime subscripts will remain true. All other array elements will eventually be set to false. b) Starting with array subscript 2 (subscript 1 must be prime), determine whether a given element is true. If so, loop through the remainder of the array and set to falseevery element whose subscript is a multiple of the subscript for the element with value true. Then, continue the process with the next element with value true. For array subscript 2, all elements beyond element 2 in the array that have subscripts which are multiples of 2 will be set to false (subscripts 4, 6, 8, 10, etc.); for array subscript 3, all elements beyond element 3 in the array that have subscripts which are multiples of 3 will be set to false(subscripts 6, 9, 12, 15, etc.); and so on. When this process is complete, the array elements that are still trueindicate that the subscript is a prime number. These subscripts can be displayed. Write a program that uses an array of 1000 elements to determine and print the prime numbers between 1 and 999. Ignore element 0 of the array. 7.28 (Bucket Sort) A bucket sort begins with a single-subscripted array of positive integers to be sorted and a double-subscripted array of integers with rows subscripted from 0 to 9 and columns subscripted from 0 to n -1, where n is the number of values in the array to be sorted. Each row of the double-subscripted array is referred to as a bucket. Write an applet containing a method called bucketSortthat takes an integer array as an argument and performs as follows: a) Place each value of the single-subscripted array into a row of the bucket array based on the value s ones digit. For example, 97 is placed in row 7, 3 is placed in row 3 and 100 is placed in row 0. This is called a distribution pass. b) Loop through the bucket array row by row and copy the values back to the original array. This is called a gathering pass. The new order of the preceding values in the single- subscripted array is 100, 3 and 97. c) Repeat this process for each subsequent digit position (tens, hundreds, thousands, etc.). On the second pass, 100 is placed in row 0, 3 is placed in row 0 (because 3 has no tens digit) and 97 is placed in row 9. After the gathering pass, the order of the values in the single-subscripted array is 100, 3 and 97. On the third pass, 100 is placed in row 1, 3 is placed in row 0 and 97 is placed in row 0 (after the 3). After the last gathering pass, the original array is now in sorted order. Note that the double-subscripted array of buckets is ten times the size of the integer array being sorted. This sorting technique provides better performance than a bubble sort, but requires much more memory. The bubble sort requires space for only one additional element of data. This is an example of the space-time trade-off: The bucket sort uses more memory than the bubble sort, but performs better. This version of the bucket sort requires copying all the data back to the original array on each pass. Another possibility is to create a second double-subscripted bucket array and repeatedly swap the data between the two bucket arrays. Copyright 1992 2002 by Deitel & Associates, Inc. All Rights Reserved. 7/3/01
Note: If you are looking for best quality webspace to host and run your tomcat application check Vision shared web hosting services

366 Arrays Chapter 7 7.23 (Knight s Tour: Brute Force Approaches) In 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 increasing 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. a) Use random number generation to enable the knight to walk around the chessboard (in its legitimate L-shaped moves, of course) at random. Your program should run one tour and print the final chessboard. How far did the knight get? b) Most likely, the preceding program produced a relatively short tour. Now modify your program to attempt 1000 tours. Use a single-subscripted array to keep track of the number of tours of each length. When your program finishes attempting the 1000 tours, it should print this information in neat tabular format. What was the best result? c) Most likely, the preceding program gave you some respectable tours, but no full tours. Now pull all the stops out and simply let your program run until it produces a full tour. (Caution: This version of the program could run for hours on a powerful computer.) Once again, keep a table of the number of tours of each length and print this table when the first full tour is found. How many tours did your program attempt before producing a full tour? How much time did it take? d) 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. 7.24 (Eight Queens) Another puzzler for chess buffs is the Eight Queens problem. Simply stated: 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 program. (Hint: It is possible to assign a value to each square of the chessboard indicating 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 in Figure 7.31.) Once these elimination numbers are placed in all 64 squares, an appropriate heuristic might be: Place the next queen in the square with the smallest elimination number. Why is this strategy intuitively appealing? 7.25 (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. a) Solve the Eight Queens exercise, using the random brute force technique developed in Exercise 7.23. b) Use an exhaustive technique (i.e., try all possible combinations of eight queens on the chessboard). c) Why do you suppose the exhaustive brute force approach may not be appropriate for solving the Knight s Tour problem? d) Compare and contrast the random brute force and exhaustive brute force approaches. 7.26 (Knight s Tour: Closed Tour Test) In the Knight s Tour, 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 program you wrote in Exercise 7.22 to test for a closed tour if a full tour has occurred. 7.27 (The Sieve of Eratosthenes) A prime integer is any integer that is evenly divisible only by itself and 1. The Sieve of Eratosthenes is a method of finding prime numbers. It operates as follows: Copyright 1992 2002 by Deitel & Associates, Inc. All Rights Reserved. 7/3/01
Note: In case you are looking for affordable webhost to host and run your servlet application check Vision servlet hosting services

Chapter 7 Arrays 365 Let the variables currentRow and currentColumn indicate the row and column of the knight s current position. To make a move of type moveNumber, where moveNumber is between 0 and 7, your program uses the statements currentRow += vertical[ moveNumber ]; currentColumn += horizontal[ moveNumber ]; 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 already visited that square. Test every potential move to ensure that the knight does not land off the chessboard. Write a program to move the knight around the chessboard. Run the program. How many moves did the knight make? c) After attempting to write and run a Knight s Tour program, you have probably developed some valuable insights. We will use these to develop a heuristic (or strategy) 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 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 they are, then always moving the knight (using the knight s L-shaped moves) to the most inaccessible square. We label a double-subscripted array accessibility with numbers indicating from how many squares each particular square is accessible. On a blank chessboard, each center square is rated as 8, each corner square is rated as 2 and the other squares have accessibility numbers of 3, 4or 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 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 program 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 program. Did you get a full tour? Modify the program to run 64 tours, one starting from each square of the chessboard. How many full tours did you get? d) Write a version of the Knight s Tour program 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 program should move to the square for which the next move would arrive at a square with the lowest accessibility number. Copyright 1992 2002 by Deitel & Associates, Inc. All Rights Reserved. 7/3/01
Note: In case you are looking for affordable and reliable webhost to host and run your j2ee application check Vision best web hosting services

364 Arrays Chapter 7 01234567 0 1 2 3 4 5 6 7 2 1 3 0 K 4 7 5 6 Fig. 7.3030 The eight possible moves of the knight. Fig. b) Now let us develop an applet that will move the knight around a chessboard. The board is represented by an 8-by-8 double-subscripted array board. Each of the squares is initialized to zero. We describe each of the eight possible moves in terms of both their horizontal and vertical components. For example, a move of type 0 as shown in Fig. 7.30 consists of moving two squares horizontally to the right and one square vertically upward. Move 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 single-subscripted arrays, horizontaland vertical, as follows: horizontal[ 0 ] = 2 horizontal[ 1 ] = 1 horizontal[ 2 ] = -1 horizontal[ 3 ] = -2 horizontal[ 4 ] = -2 horizontal[ 5 ] = -1 horizontal[ 6 ] = 1 horizontal[ 7 ] = 2 vertical[ 0 ] = -1 vertical[ 1 ] = -2 vertical[ 2 ] = -2 vertical[ 3 ] = -1 vertical[ 4 ] = 1 vertical[ 5 ] = 2 vertical[ 6 ] = 2 vertical[ 7 ] = 1 Copyright 1992 2002 by Deitel & Associates, Inc. All Rights Reserved. 7/3/01
Note: In case you are looking for affordable webhost to host and run your web application check Vision cheap hosting services

Chapter 7 Arrays 363 Command Meaning 1 Pen up 2 Pen down 3 Turn right 4 Turn left 5,10 Move forward 10 spaces (or a number other than 10) 6 Print the 20-by-20 array 9 End of data (sentinel) Fig. 7.29 Turtle graphics commands. Suppose that the turtle is somewhere near the center of the floor. The following program would draw and print 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 floorto 1s. When the 6 command (print) is given, wherever there is a 1 in the array, display an asterisk or some other character you choose. Wherever there is a zero, display a blank. Write a Java applet to implement the turtle graphics capabilities discussed here. The applet should display the turtle graphics in a JTextArea, using Monospaced font. Write several turtle graphics programs to draw interesting shapes. Add other commands to increase the power of your turtle graphics language. 7.22 (Knight s Tour) One of the more interesting puzzlers for chess buffs is the Knight s Tour problem, originally proposed by the mathematician Euler. The question is this: 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 L-shaped moves (over two in one direction and then over one in a perpendicular direction). Thus, from a square in the middle of an empty chessboard, the knight can make eight different moves (numbered 0 through 7) as shown in Fig. 7.30. a) Draw an 8-by-8 chessboard on a sheet of paper and attempt a Knight s Tour by hand. Put a 1in the first square you move to, a 2in the second square, a 3in the third, etc. 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? Copyright 1992 2002 by Deitel & Associates, Inc. All Rights Reserved. 7/3/01
Note: If you are looking for cheap and reliable webhost to host and run your mysql application check Vision mysql hosting services

362 Arrays Chapter 7 9 public class WhatDoesThisDo2 extends JApplet { 10 11 public void init() 12 { 13 int array[] = { 1, 2, 3, 4,5,6, 7, 8, 9, 10 }; 14 JTextArea outputArea = new JTextArea(); 15 16 someFunction( array, 0, outputArea ); 17 18 Container container = getContentPane(); 19 container.add( outputArea ); 20 } 21 22 public void someFunction( int array2[], int x, JTextArea out ) 23 { 24 if ( x < array2.length ) { 25 someFunction( array2, x + 1, out ); 26 out.append( array2[ x ] + " " ); 27 } 28 } 29 } Fig. 7.28 Determine what this program does. 7.20 Use a double-subscripted 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 different type of product sold. Each slip contains the following: a) The salesperson number b) The product number c) 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 of the slips for last month is available. Write an applet that will read all this information for last month s sales and summarize the total sales by salesperson by product. All totals should be stored in the double-subscripted array sales. After processing all the information for last month, display the results in tabular format with each of the columns representing a particular salesperson and each of the rows 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 printout should include these cross totals to the right of the totaled rows and to the bottom of the totaled columns. Display the results in a JTextArea. 7.21 (Turtle Graphics) The Logo language, which is popular among young computer users, made the concept of turtle graphics famous. Imagine a mechanical turtle that walks around the room under the control of a Java program. 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; 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 as well. 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 program must process are shown in Fig. 7.29. Copyright 1992 2002 by Deitel & Associates, Inc. All Rights Reserved. 7/3/01
Note: If you are looking for high quality webhost to host and run your jsp application check Vision jsp web hosting services

Chapter 7 Arrays 361 28 else 29 return array2[ size -1 ] + 30 whatIsThis( array2, size -1 ); 31 } 32 } Fig. 7.27 Determine what this program does. 7.17 Write a program that runs 1000 games of craps (Fig. 6.9) and answers the following questions: a) How many games are won on the first roll, second roll, , twentieth roll and after the twentieth roll? b) How many games are lost on the first roll, second roll, , twentieth roll and after the twentieth roll? c) 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?] d) What is the average length of a game of craps? e) Do the chances of winning improve with the length of the game? 7.18 (Airline Reservations System) A small airline has just purchased a computer for its new automated reservations system. You have been asked to program the new system. You are to write an applet to assign seats on each flight of the airline s only plane (capacity: 10 seats). Your program should display the following alternatives: Please type 1 for “smoking” Please type 2 for “nonsmoking” If the person types 1, your program should assign a seat in the smoking section (seats 1-5). If the person types 2, your program should assign a seat in the nonsmoking section (seats 6-10). Your program should then print a boarding pass indicating the person s seat number and whether it is in the smoking or nonsmoking section of the plane. Use a single-subscripted 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 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 program should, of course, never assign a seat that has already been assigned. When the smoking section is full, your program should ask the person if it is acceptable to be placed in the nonsmoking section (and vice versa). If yes, make the appropriate seat assignment. If no, print the message “Nextflightleavesin3hours.” 7.19 What does the program of Fig. 7.28 do? 1 // Exercise 7.19: WhatDoesThisDo2.java 2 3 // Java core packages 4 import java.awt.*; 5 6 // Java extension packages 7 import javax.swing.*; 8 Fig. 7.28 Determine what this program does. Copyright 1992 2002 by Deitel & Associates, Inc. All Rights Reserved. 7/3/01
Note: If you are looking for high quality webhost to host and run your jsp application check Vision christian web host services

360 Arrays Chapter 7 123456 1 2 3 4 5 6 2 3 4 5 6 7 3 4 5 6 7 8 4 5 6 7 8 9 5 6 7 8 9 10 6 7 8 910 11 7 8 9 10 11 12 Fig. 7.2626 The 36 possible outcomes of rolling two dice. Fig. roll the dice 36,000 times. Use a single-subscripted array to tally the numbers of times each possible sum appears. Display the results in a JTextAreain tabular format. Also, determine whether the totals are reasonable (i.e., there are six ways to roll a 7, so approximately one sixth of all the rolls should be 7). The applet should use the GUI techniques introduced in Chapter 6. Provide a JButtonto allow the user of the applet to roll the dice another 36,000 times. The applet should reset the elements of the single-subscripted array to 0 before rolling the dice again. 7.16 What does the program of Fig. 7.27 do? 1 // Exercise 7.16: WhatDoesThisDo.java 2 3 // Java core packages 4 import java.awt.*; 5 6 // Java extension packages 7 import javax.swing.*; 8 9 public class WhatDoesThisDo extends JApplet { 10 int result; 11 12 public void init() 13 { 14 int array[] = { 1, 2, 3, 4,5,6, 7, 8, 9, 10 }; 15 16 result = whatIsThis( array, array.length ); 17 18 Container container = getContentPane(); 19 JTextArea output = new JTextArea(); 20 output.setText( “Result is: ” + result ); 21 container.add( output ); 22 } 23 24 public int whatIsThis( int array2[], int size ) 25 { 26 if ( size == 1 ) 27 return array2[ 0 ]; Fig. 7.27 Determine what this program does. Copyright 1992 2002 by Deitel & Associates, Inc. All Rights Reserved. 7/3/01
Note: If you are looking for cheap and reliable webhost to host and run your mysql application check Vision mysql hosting services

Chapter 7 Arrays 359 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 applet (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): a) $200-$299 b) $300-$399 c) $400-$499 d) $500-$599 e) $600-$699 f) $700-$799 g) $800-$899 h) $900-$999 i) $1000 and over The applet should use the GUI techniques introduced in Chapter 6. Display the results in a JText- Area. Use JTextArea method setText to update the results after each value input by the user. 7.11 The bubble sort presented in Fig. 7.11 is inefficient for large arrays. Make the following simple modifications to improve the performance of the bubble sort: a) After the first pass, the largest number is guaranteed to be in the highest-numbered element of the array; after the second pass, the two highest numbers are in place ; and so on. Instead of making nine comparisons on every pass, modify the bubble sort to make eight comparisons on the second pass, seven on the third pass and so on. b) The data in the array may already be in the proper order or near-proper order, so why make nine passes if fewer will suffice? Modify the sort to check at the end of each pass if any swaps have been made. If none have been made, the data must already be in the proper order, so the program should terminate. If swaps have been made, at least one more pass is needed. 7.12 Write statements that perform the following single-subscripted array operations: a) Set the 10 elements of integer array counts to zeros. b) Add 1 to each of the 15 elements of integer array bonus. c) Print the five values of integer array bestScores in column format. 7.13 Use a single-subscripted array to solve the following problem: Write an applet that inputs 20 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 20 numbers are different. Use the smallest possible array to solve this problem. The applet should use the GUI techniques introduced in Chapter 6. Display the results in a JTextArea. Use JTextAreamethod setTextto update the results after each value input by the user. 7.14 Label the elements of 3-by-5 double-subscripted 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; 7.15 Write an applet to simulate the rolling of two dice. The program should use Math.random to roll the first die and should use Math.random again to roll the second die. The sum of the two values should then be calculated. [Note: 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.26 shows the 36 possible combinations of the two dice. Your program should Copyright 1992 2002 by Deitel & Associates, Inc. All Rights Reserved. 7/3/01
Note: If you are looking for best quality webspace to host and run your tomcat application check Vision personal web hosting services