Fig. 7.17
The 36 possible outcomes of rolling two dice.
Included below are short-answer and programming exercises. Answers are provided for those exercises whose exercise number is a hyperlink. Because college faculty use these exercises in their exams, we have provided answers to roughly half of the exercises included here.
7.6 Fill in the blanks in each of the following:
7.7 State whether each of the following is true or false. If false, explain why.
7.8 Write Java statements to accomplish each of the following:
7.9 Consider a 2-by-3 integer array t.
7.10 Use a single-subscripted 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 a program (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):
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.
7.12 Write statements that perform the following single-subscripted array operations:
7.13 Use a single-subscripted array to solve the following problem. Read in 20 numbers, each of which is between 10 and 100, inclusive. As each number is read, print 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.
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:
7.15 Write a program 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: Since each die can show an integer value from 1 to 6, 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.17 shows the 36 possible combinations of the two dice. Your program should roll the dice 36,000 times. Use a single-subscripted array to tally the numbers of times each possible sum appears. Print the results in a tabular format. Also, determine if 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).]
Fig. 7.17
The 36 possible outcomes of rolling two dice.
7.16 What does the following program do?
7.17 Write a program that runs 1000 games of craps and answers the following questions:
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 a program to assign seats on each flight of the airline’s only plane (capacity: 10 seats).
Your program should display the following menu of 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 to represent the seating chart of the plane. Initialize all the elements of the array to 0 to indicate that all seats are empty. As each seat is assigned, set the corresponding elements of the array to 1 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 "Next flight leaves in 3 hours."
7.19 What does the following program do?
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:
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 of the slips for last month is available. Write a program 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.
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 which 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 as follows:
| 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) |
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 floor to 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 program 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.
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.18.
Fig. 7.18
The eight possible moves of the knight.
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
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?
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 may 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, 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 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?
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.
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, 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 Fig. 7.19.) 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?
Fig. 7.19
The 22 squares eliminated by placing a queen in the upper left corner.
| * * * * * * * * * * * * * * * * * * * * * * |
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.
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:
When this process is complete, the array elements that are still set to one indicate that the subscript is a prime number. These subscripts can then be printed. 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 a method bucketSort that takes an integer array as an argument and performs as follows:
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.
Recursion Exercises
7.29 (Selection Sort) A selection sort searches an array looking for the smallest element in the array. Then, the smallest element is swapped with the first element of the array. The process is repeated for the subarray beginning with the second element of the array. Each pass of the array results in one element being placed 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 selectionSort to 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 1 if the string stored in the array is a palindrome and 0 otherwise. The method should ignore spaces and punctuation in the string.
7.31 (Linear Search) Modify Fig. 7.12 to use recursive method linearSearch to perform a linear search of the array. The method should receive an integer array and the size of the array as arguments. If the search key is found, return the array subscript; otherwise, return —1.
7.32 (Binary Search) Modify the program of Fig. 7.13 to use a recursive method binarySearch 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 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 zero.
7.35 (Print a string backward) Write a recursive method stringReverse that 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 recursiveMinimum that 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 of 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:
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
12 2 6 4 89 8 10 37 68 45
Element 12 is in italic to indicate that it was just swapped with 37.
Once the partition has been applied on the above array, there are two unsorted subarrays. The subarray with values less than 37 contains 12, 2, 6, 4, 10 and 8. The subarray with values greater than 37 contains 89, 68 and 45. The sort continues with both subarrays being partitioned in the same manner as the original array.
Based on the preceding discussion, write recursive method quickSort to sort a single-subscripted integer array. The method should receive as arguments an integer array, a starting subscript and an ending subscript. Method partition should be called by quickSort to perform the partitioning step.
7.38 (Maze Traversal) The following grid of #s and dots (.) is a double-subscripted array representation of a maze.
# # # # # # # # # # # #
# . . . # . . . . . . #
. . # . # . # # # # . #
# # # . # . . . . # . #
# . . . . # # # . # . .
# # # # . # . # . # . #
# . . # . # . # . # . #
# # . # . # . # . # . #
# . . . . . . . . # . #
# # # # # # . # # # . #
# . . . . . . # . . . #
# # # # # # # # # # # #
In the preceding double-subscripted array, the #s represent the walls of the maze and the dots represent squares in the possible paths through the maze. Moves can only be made to a location in the array that contains a dot.
There is a simple algorithm for walking through a maze that guarantees finding the exit (assuming there is an exit). If there is not an exit, you will arrive at the starting location again. Place your right hand on the wall to your right and begin walking forward. Never remove your hand from the wall. If the maze turns to the right, you follow the wall to the right. As long as you do not remove your hand from the wall, eventually you will arrive at the exit of the maze. There may be a shorter path than the one you have taken, but you are guaranteed to get out of the maze if you follow the algorithm.
Write recursive method mazeTraverse to walk through the maze. The method should receive as arguments a 12-by-12 character array representing the maze and the starting location of the maze. As mazeTraverse attempts to locate the exit from the maze, it should place the character X in each square in the path. The method should display the maze after each move so the user can watch as the maze is solved.
7.39 (Generating Mazes Randomly) Write a method mazeGenerator that takes as an argument a double-subscripted 12-by-12 character array and randomly produces a maze. The method should also provide the starting and ending locations of the maze. Try your method mazeTraverse from Exercise 7.38 using several randomly generated mazes.
7.40 (Mazes of Any Size) Generalize methods mazeTraverse and mazeGenerator of Exercises 7.38 and 7.39 to process mazes of any width and height.
7.41 (Simulation: The Tortoise and the Hare) In this problem you will recreate one of the truly great moments in history, namely 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.
There is a clock that ticks once per second. With each tick of the clock, your program should adjust the position of the animals according to the following rules:
| Animal | Move type | Percentage of the time | Actual move |
| Tortoise | Fast plod | 50% | 3 squares to the right |
| Slip | 20% | 6 squares to the left | |
| Slow plod | 30% | 1 square to the right | |
| Hare | Sleep | 20% | No move at all |
| Big hop | 20% | 9 squares to the right | |
| Big slip | 10% | 12 squares to the left | |
| Small hop | 30% | 1 square to the right | |
| Small slip | 20% | 2 squares to the left |
Use variables to keep track of the positions of the animals (i.e., position numbers are 1—70). Start each animal at position 1 (i.e., the "starting gate"). If an animal slips left before square 1, move the animal back to square 1.
Generate the percentages in the preceding table by producing a random integer, i, in the range 1 i 10. For the tortoise, perform a "fast plod" when 1 i 5, a "slip" when 6 i 7 or a "slow plod" when 8 i 10. Use a similar technique to move the hare.
Begin the race by printing
BANG !!!!!
AND THEY'RE OFF !!!!!
Then, for each tick of the clock (i.e., each repetition of a loop), print 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 program should print OUCH!!! beginning at that position. All print positions other than the T, the H or the OUCH!!! (in case of a tie) should be blank.
After each line is printed, test if either animal has reached or passed square 70. If so, print the winner and terminate the simulation. If the tortoise wins, print TORTOISE WINS!!! YAY!!! If the hare wins, print Hare wins. Yuch. If both animals win on the same tick of the clock, you may want to favor the turtle (the "underdog") or you may want to print 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 program, 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.
Special Section: Building Your Own Computer
In the next several problems, we take a temporary diversion away from the world of high-level language programming. We "peel open" a computer and look at its internal structure. We introduce machine-language programming and write several machine-language programs. To make this an especially valuable experience, we then build a computer (through the technique of software-based simulation) on which you can execute your machine-language programs!
7.42 (Machine-Language Programming) Let us create a computer we will call the Simpletron. As its name implies, it is a simple machine, but as we will soon see, a powerful one as well. The Simpletron runs programs written in the only language it directly understands, that is, Simpletron Machine Language or SML for short.
The Simpletron contains an accumulator–a "special register" in which information is put before the Simpletron uses that information in calculations or examines it in various ways. All information in the Simpletron is handled in terms of words. A word is a signed four-digit decimal number such as +3364, -1293, +0007, -0001, etc. The Simpletron is equipped with a 100-word memory and these words are referenced by their location numbers 00, 01, …, 99.
Before running an SML program, we must load or place the program into memory. The first instruction (or statement) of every SML program is always placed in location 00. The simulator will start executing at this location.
Each instruction written in SML occupies one word of the Simpletron’s memory (and hence instructions are signed four-digit decimal numbers). We shall assume that the sign of an SML instruction is always plus, but the sign of a data word may be either plus or minus. Each location in the Simpletron’s memory may contain either an instruction, a data value used by a program or an unused (and hence undefined) area of memory. The first two digits of each SML instruction are the operation code specifying the operation to be performed. SML operation codes are summarized in Fig. 7.20.
Fig. 7.20
Simpletron Machine Language (SML) operation codes.
| Operation code | Meaning |
| Input/output operations: | |
| final int READ = 10; | Read a word from the keyboard into a specific location in memory. |
| final int WRITE = 11; | Write a word from a specific location in memory to the screen. |
| Load/store operations: | |
| final int LOAD = 20; | Load a word from a specific location in memory into the accumulator. |
| final int STORE = 21; | Store a word from the accumulator into a specific location in memory. |
| Arithmetic operations: | |
| final int ADD = 30; | Add a word from a specific location in memory to the word in the accumulator (leave result in the accumulator). |
| final int SUBTRACT = 31; | Subtract a word from a specific location in memory from the word in the accumulator (leave result in the accumulator). |
| final int DIVIDE = 32; | Divide a word from a specific location in memory into the word in the accumulator (leave result in the accumulator). |
| final int MULTIPLY = 33; | Multiply a word from a specific location in memory by the word in the accumulator (leave result in the accumulator). |
| Transfer of control operations: | |
| final int BRANCH = 40; | Branch to a specific location in memory. |
| final int BRANCHNEG = 41; | Branch to a specific location in memory if the accumulator is negative. |
| final int BRANCHZERO = 42; | Branch to a specific location in memory if the accumulator is zero. |
| final int HALT = 43; | Halt–the program has completed its task. |
The last two digits of an SML instruction are the operand–the address of the memory location containing the word to which the operation applies. Let’s consider several simple SML programs.
The first SML program (Example 1) reads two numbers from the keyboard and computes and prints their sum. The instruction +1007 reads the first number from the keyboard and places it into location 07 (which has been initialized to zero). Then instruction +1008 reads the next number into location 08. The load instruction, +2007, puts the first number into the accumulator and the add instruction, +3008, adds the second number to the number in the accumulator. All SML arithmetic instructions leave their results in the accumulator. The store instruction, +2109, places the result back into memory location 09 from which the write instruction, +1109, takes the number and prints it (as a signed four-digit decimal number). The halt instruction, +4300, terminates execution.
| Example 1 Location | Number | Instruction |
| 00 | +1007 | (Read A) |
| 01 | +1008 | (Read B) |
| 02 | +2007 | (Load A) |
| 03 | +3008 | (Add B) |
| 04 | +2109 | (Store C) |
| 05 | +1109 | (Write C) |
| 06 | +4300 | (Halt) |
| 07 | +0000 | (Variable A) |
| 08 | +0000 | (Variable B) |
| 09 | +0000 | (Result C) |
The next SML program reads two numbers from the keyboard and determines and prints the larger value. Note the use of the instruction +4107 as a conditional transfer of control, much the same as Java’s if statement.
| Example 2 Location | Number | Instruction |
| 00 | +1009 | (Read A) |
| 01 | +1010 | (Read B) |
| 02 | +2009 | (Load A) |
| 03 | +3110 | (Subtract B) |
| 04 | +4107 | (Branch negative to 07) |
| 05 | +1109 | (Write A) |
| 06 | +4300 | (Halt) |
| 07 | +1110 | (Write B) |
| 08 | +4300 | (Halt) |
| 09 | +0000 | (Variable A) |
| 10 | +0000 | (Variable B) |
Now write SML programs to accomplish each of the following tasks.
7.43 (A Computer Simulator) It may at first seem outrageous, but in this problem you are going to build your own computer. No, you will not be soldering components together. Rather, you will use the powerful technique of software-based simulation to create an object-oriented software model of the Simpletron. You will not be disappointed. Your Simpletron simulator will turn the computer you are using into a Simpletron, and you will actually be able to run, test and debug the SML programs you wrote in Exercise 7.42. Your Simpletron will be an event-driven applet–you will click a button to execute each SML instruction and you will be able to see the instruction "in action."
When you run your Simpletron simulator, it should begin by displaying:
*** Welcome to Simpletron! ***
*** Please enter your program one instruction ***
*** (or data word) at a time into the input ***
*** text field. I will display the location ***
*** number and a question mark (?). You then ***
*** type the word for that location. Press the ***
*** Done button to stop entering your program. ***
The program should display an input JTextField in which the user will type each instruction one at a time and a Done button for the user to click when the complete SML program has been entered. Simulate the memory of the Simpletron with a single-subscripted array memory that has 100 elements. Now assume that the simulator is running and let us examine the dialog as we enter the program of Example 2 of Exercise 7.42:
00 ? +1009
01 ? +1010
02 ? +2009
03 ? +3110
04 ? +4107
05 ? +1109
06 ? +4300
07 ? +1110
08 ? +4300
09 ? +0000
10 ? +0000
Your program should use a JTextField to display the memory location followed by a question mark. Each of the values to the right of a question mark is typed by the user into the input JTextField. When the Done button is clicked, the program should display:
*** Program loading completed ***
*** Program execution begins ***
The SML program has now been placed (or loaded) in array memory. The Simpletron should provide an "Execute next instruction" button the user can click to execute each instruction in your SML program. Execution begins with the instruction in location 00 and, like Java, continues sequentially, unless directed to some other part of the program by a transfer of control.
Use the variable accumulator to represent the accumulator register. Use the variable instructionCounter to keep track of the location in memory that contains the instruction being performed. Use the variable operationCode to indicate the operation currently being performed (i.e., the left two digits of the instruction word). Use the variable operand to indicate the memory location on which the current instruction operates. Thus, operand is the rightmost two digits of the instruction currently being performed. Do not execute instructions directly from memory. Rather, transfer the next instruction to be performed from memory to a variable called instructionRegister. Then "pick off" the left two digits and place them in operationCode and "pick off" the right two digits and place them in operand. Each of the preceding registers should have a corresponding JTextField in which its current value can be displayed at all times. When Simpletron begins execution, the special registers are all initialized to 0.
Now let us "walk through" execution of the first SML instruction, +1009 in memory location 00. This is called an instruction execution cycle.
The instructionCounter tells us the location of the next instruction to be performed. We fetch the contents of that location from memory by using the Java statement
instructionRegister = memory[ instructionCounter ];
The operation code and the operand are extracted from the instruction register by the statements
operationCode = instructionRegister / 100;
operand = instructionRegister % 100;
Now the Simpletron must determine that the operation code is actually a read (versus a write, a load, etc.). A switch differentiates among the twelve operations of SML.
In the switch structure, the behavior of various SML instructions is simulated as follows (we leave the others to the reader):
| read: | Display an input dialog with the prompt "Enter an integer." Read the value entered, convert it to an integer and store it in location memory[ operand ]. |
| load: | accumulator = memory[ operand ]; |
| add: | accumulator += memory[ operand ]; |
| branch: | We will discuss the branch instructions shortly. |
| halt: | This instruction prints the message *** Simpletron execution terminated *** |
When the SML program completes execution, the name and contents of each register as well as the complete contents of memory should be displayed. Such a printout is often called a computer dump (and, no, a computer dump is not a place where old computers go). To help you program your dump method, a sample dump format is shown in Fig. 7.23. Note that a dump after executing a Simpletron program would show the actual values of instructions and data values at the moment execution terminated. The sample dump assumes the output will be sent to the display screen with a series of System.out.print and System.out.println method calls. However, we encourage you to experiment with a version that can be displayed on the applet using a JTextArea or an array of JTextField objects.
Let us proceed with the execution of our program’s first instruction, namely the +1009 in location 00. As we have indicated, the switch statement simulates this by prompting the user to enter a value into the input dialog, reading the value, converting the value to an integer and storing it in memory location memory[ operand ]. Because your Simpletron is event driven, it waits for the user to type a value into the input JTextField and press the Enter key. The value is then read into location 09.
Fig. 7.21
A sample dump.
| REGISTERS:
accumulator +0000 instructionCounter 00 instructionRegister +0000 operationCode 00 operand 00 MEMORY: |
At this point, simulation of the first instruction is completed. All that remains is to prepare the Simpletron to execute the next instruction. Since the instruction just performed was not a transfer of control, we need merely increment the instruction counter register as follows:
++instructionCounter;
This completes the simulated execution of the first instruction. When the user clicks the Execute next instruction button, the entire process (i.e., the instruction execution cycle) begins again with the fetch of the next instruction to be executed.
Now let us consider how the branching instructions–the transfers of control–are simulated. All we need to do is adjust the value in the instruction counter appropriately. Therefore, the unconditional branch instruction (40) is simulated within the switch as
instructionCounter = operand;
The conditional "branch if accumulator is zero" instruction is simulated as
if ( accumulator == 0 )
instructionCounter = operand;
At this point you should implement your Simpletron simulator and run each of the SML programs you wrote in Exercise 7.42. You may embellish SML with additional features and provide for these in your simulator.
Your simulator should check for various types of errors. During the program loading phase, for example, each number the user types into the Simpletron’s memory must be in the range -9999 to +9999. Your simulator should test that each number entered is in this range, and, if not, keep prompting the user to reenter the number until the user enters a correct number.
During the execution phase, your simulator should check for various serious errors, such as attempts to divide by zero, attempts to execute invalid operation codes, accumulator overflows (i.e., arithmetic operations resulting in values larger than +9999 or smaller than -9999) and the like. Such serious errors are called fatal errors. When a fatal error is detected, your simulator should print an error message such as:
*** Attempt to divide by zero ***
*** Simpletron execution abnormally terminated ***
and should print a full computer dump in the format we have discussed previously. This will help the user locate the error in the program.
7.44 (Modifications to the Simpletron Simulator) In Exercise 7.43, you wrote a software simulation of a computer that executes programs written in Simpletron Machine Language (SML). In this exercise, we propose several modifications and enhancements to the Simpletron Simulator. In Exercises 22.26 and 22.27, we propose building a compiler that converts programs written in a high-level programming language (a variation of Basic) to Simpletron Machine Language. Some of the following modifications and enhancements may be required to execute the programs produced by the compiler.
7.45 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.
Included below are answers to approximately half the of the exercises in the Cyber Classroom. We are not able to include answers to every exercise because college faculty use these exercises in their classroom exams.
7.6 Fill in the blanks in each of the following:
7.9 Consider a 2-by-3 integer array t.
// Exercise 7.10 Solution
// Sales.java
// Program calculates the amount of pay
// for a salesperson
import javax.swing.*;
import java.awt.*;
import java.awt.event.*;
public class Sales extends JApplet
implements ActionListener {
JTextField input;
JLabel prompt;
int total[];
public void init()
{
total = new int[ 9 ];
for ( int i = 0; i < total.length; i++ )
total[ i ] = 0;
input = new JTextField( 5 );
input.addActionListener( this );
prompt = new JLabel( "Enter sales amount:" );
Container c = getContentPane();
c.setLayout( new FlowLayout() );
c.add( prompt );
c.add( input );
}
public void paint( Graphics g )
{
super.paint( g );
int x = 105, y = 70;
g.drawString( "Range", 5, 50 );
g.drawString( "Number", 105, 50 );
g.drawString( "$200-$299", 5, 70 );
g.drawString( "$300-$399", 5, 80 );
g.drawString( "$400-$499", 5, 90 );
g.drawString( "$500-$599", 5, 100 );
g.drawString( "$600-$699", 5, 110 );
g.drawString( "$700-$799", 5, 120 );
g.drawString( "$800-$899", 5, 130 );
g.drawString( "$900-$999", 5, 140 );
g.drawString( "$1000 and over", 5, 150 );
for ( int i = 0; i < total.length; i++, y += 10 )
g.drawString( String.valueOf( total[ i ] ), x, y );
}
public void actionPerformed( ActionEvent e )
{
double dollars = Double.parseDouble( input.getText() );
double salary = dollars * 0.09 + 200;
int x = ( int ) ( salary / 100 );
if ( salary < 0 )
return;
else if ( x > 9 )
x = 10;
++total[ x - 2 ];
input.setText( "" );
repaint();
}
}
// Exercise 7.15 Solution
// Roll36.java
// Program simulates rolling two
// six-sided die 36,000 times
// NOTE: this program could take a
// few seconds before displaying the data
import javax.swing.*;
import java.awt.*;
public class Roll36 extends JApplet {
int total[];
public void init()
{
total = new int[ 13 ];
for ( int i = 0; i < total.length; i++ )
total[ i ] = 0;
roll2Dice();
}
public void roll2Dice()
{
int face1, face2;
for ( int x = 1; x <= 36000; x++ ) {
face1 = ( int ) ( 1 + Math.random() * 6 );
face2 = ( int ) ( 1 + Math.random() * 6 );
total[ face1 + face2 ]++;
}
}
public void paint( Graphics g )
{
super.paint( g );
int y = 60;
g.drawString( "Sum", 5, 60 );
g.drawString( "Frequency", 85, 60 );
// ignore subscripts 0 and 1
for ( int k = 2; k < total.length; k++ ) {
g.drawString( String.valueOf( k ), 5, y += 10 );
g.drawString( String.valueOf( total[ k ] ), 85, y );
double percent = ( double ) total[ k ] / 360.0;
g.drawString( "%" + ( int ) percent, 150, y );
}
}
}
// Exercise 7.16 Solution
// WhatDoesThisDo.java
// What does this program do?
import java.awt.*;
import javax.swing.*;
public class WhatDoesThisDo extends JApplet {
int result;
public void start()
{
int a[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
result = whatIsThis( a, a.length );
Container c = getContentPane();
JTextArea output = new JTextArea();
output.setText( "Result is: " + result );
c.add( output );
}
public int whatIsThis( int b[], int size )
{
if ( size == 1 )
return b[ 0 ];
else
return b[ size - 1 ] + whatIsThis( b, size - 1 );
}
}
// Exercise 7.18 Solution
// Plane.java
// Airline Reservation System program
import javax.swing.*;
import java.awt.*;
import java.awt.event.*;
public class Plane extends JApplet
implements ActionListener {
JTextField input;
JLabel prompt1, prompt2;
JButton yesButton, noButton;
int section, seats[], smoking;
int nonsmoking, people;
public void init()
{
input = new JTextField( 4 );
input.addActionListener( this );
prompt1 = new JLabel( "Please type 1 for smoking" );
prompt2 = new JLabel( "Please type 2 for nonsmoking" );
yesButton = new JButton( "Yes" );
noButton = new JButton( "No" );
yesButton.addActionListener( this );
noButton.addActionListener( this );
// The enabled method has not been introduced up
// to this point in the book. It is used here to
// disable the buttons by "graying" them.
yesButton.setEnabled( false );
noButton.setEnabled( false );
seats = new int[ 11 ];
smoking = 6;
nonsmoking = 1;
Container c = getContentPane();
c.setLayout( new FlowLayout() );
c.add( prompt1 );
c.add( prompt2 );
c.add( input );
c.add( yesButton );
c.add( noButton );
}
public void actionPerformed( ActionEvent e )
{
if ( e.getSource() == input && people <= 10 ) {
section = Integer.parseInt( input.getText() );
String s = "";
if ( section == 1 ) {
if ( smoking <= 10 && seats[ smoking ] == 0 ) {
s = "Smoking. Seat #" + smoking;
seats[ smoking++ ] = 1;
people++;
}
else if ( smoking > 10 && nonsmoking <= 5 ) {
// enable buttons
yesButton.setEnabled( true );
noButton.setEnabled( true );
s = "Smoking is full. Non-smoking?";
}
else
s = "Next flight leaves in 3 hours.";
}
else if ( section == 2 ) {
if ( seats[ nonsmoking ] == 0 && nonsmoking <= 5 ) {
s = "Nonsmoking. Seat #" + nonsmoking;
seats[ nonsmoking++ ] = 1;
people++;
}
else if ( nonsmoking > 5 && smoking <= 10 ) {
// enable buttons
yesButton.setEnabled( true );
noButton.setEnabled( true );
s = "Nonsmoking is full. Smoking?";
}
else
s = "Next flight leaves in 3 hours.";
}
else
s = "Invalid input.";
showStatus( s );
}
else if ( e.getSource() == yesButton ) {
if ( section == 1 ) {
showStatus( "Your seat assignment is " + nonsmoking );
seats[ nonsmoking++ ] = 1;
}
else { // section is 2
showStatus( "Your seat assignment is " + smoking );
seats[ smoking++ ] = 1;
}
++people;
noButton.setEnabled( false );
yesButton.setEnabled( false );
}
else if ( e.getSource() == noButton ) {
showStatus( "Next flight leaves in 3 hours." );
noButton.setEnabled( false );
yesButton.setEnabled( false );
}
}
}
// Exercise 7.19 Solution
// WhatDoesThisDo2.java
// What does this program do?
import javax.swing.*;
import java.awt.*;
public class WhatDoesThisDo2 extends JApplet {
int yPosition;
int a[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
public void paint( Graphics g )
{
super.paint( g );
yPosition = 25;
someMethod( a, 0, g );
}
public void someMethod( int b[], int x, Graphics g )
{
if ( x < b.length ) {
someMethod( b, x + 1, g );
g.drawString( String.valueOf( b[ x ] ),
25, yPosition );
yPosition += 15;
}
}
}
// Exercise 7.20 Solution
// Sales.java
// Program totals sales for salespeople
// and products.
import javax.swing.*;
import java.awt.*;
import java.awt.event.*;
public class Sales extends JApplet
implements ActionListener {
JLabel prompt1, prompt2, prompt3;
JTextField input1, input2, input3;
double sales[][], totalPerson[], totalProducts[];
int person, product;
public void init()
{
sales = new double[ 4 ][ 5 ];
totalPerson = new double[ 4 ];
totalProducts = new double[ 5 ];
prompt1 = new JLabel( "Enter sales person number: " );
prompt2 = new JLabel( "Enter product number: " );
prompt3 = new JLabel( "Enter sales amount: " );
input1 = new JTextField( 5 );
input2 = new JTextField( 5 );
input3 = new JTextField( 5 );
input3.addActionListener( this );
Container c = getContentPane();
c.setLayout( new FlowLayout() );
c.add( prompt1 );
c.add( input1 );
c.add( prompt2 );
c.add( input2 );
c.add( prompt3 );
c.add( input3 );
}
public void actionPerformed( ActionEvent e )
{
showStatus( "" );
double d = Double.parseDouble( input3.getText() );
person = Integer.parseInt( input1.getText() );
product = Integer.parseInt( input2.getText() );
if ( person >= 1 && person < 5 &&
product >= 1 && product < 6 ) {
sales[ person - 1 ][ product - 1 ] += d;
}
else
showStatus( "Invalid input!" );
repaint();
}
public void paint( Graphics g )
{
super.paint( g );
int x = 100, y = 120;
double total = 0.0;
for ( int j = 0; j < totalProducts.length; j++ )
totalProducts[ j ] = 0;
g.drawString( "Product", 5, 110 );
g.drawString( "1", x += 30, 110 );
g.drawString( "2", x += 30, 110 );
g.drawString( "3", x += 30, 110 );
g.drawString( "4", x += 30, 110 );
g.drawString( "5", x += 30, 110 );
g.drawString( "Total", x += 30, 110 );
for ( int r = 0; r < sales.length; r++ ) {
g.drawString( "Sales person " + ( r + 1 ), 5, y );
total = 0.0;
x = 100;
for ( int c = 0; c < sales[ r ].length; c++ ) {
total += sales[ r ][ c ];
g.drawString( String.valueOf( sales[ r ][ c ] ), x += 30, y );
totalProducts[ c ] += sales[ r ][ c ];
}
g.drawString( String.valueOf( total ), x += 30, y );
y += 10;
}
g.drawString( "Total", 5, y );
x = 100;
for ( int k = 0; k < totalProducts.length; k++ )
g.drawString( String.valueOf( totalProducts[ k ] ), x += 30, y );
}
}
// Exercise 7.27 Solution
// Sieve.java
// Sieve of Eratosthenes
import javax.swing.*;
import java.awt.*;
public class Sieve {
public static void main( String args[] )
{
int count = 0;
String result = "";
JTextArea output = new JTextArea( 10, 15 );
JScrollPane scroller = new JScrollPane( output );
int a[] = new int[ 1000 ];
for ( int z = 0; z < a.length; z++ )
a[ z ] = 1;
for ( int i = 1; i < a.length; i++ )
if ( a[ i ] == 1 && i != 1 )
for ( int j = i; j < a.length; j++ )
if ( j % i == 0 && j != i )
a[ j ] = 0;
// range 2 - 197
for ( int k = 2; k < a.length; k++ )
if ( a[ k ] == 1 ) {
result += k + " is prime." + "\n";
++count;
}
result += "\n" + count + " primes found.";
output.setText( result );
JOptionPane.showMessageDialog(
null, scroller, "Sieve",
JOptionPane.INFORMATION_MESSAGE );
System.exit( 0 );
}
}
// Exercise 7.30 Solution
// Palindrome.java
// Program tests for a palindrome
import javax.swing.*;
import java.awt.event.*;
import java.awt.*;
public class Palindrome extends JApplet
implements ActionListener {
String string;
char copy[];
JLabel label;
JTextField input;
public void init()
{
label = new JLabel( "Enter a string:" );
input = new JTextField( 20 );
input.addActionListener( this );
Container c = getContentPane();
c.setLayout( new FlowLayout() );
c.add( label );
c.add( input);
}
public void actionPerformed( ActionEvent e )
{
string = input.getText();
int count = makeCopy();
if ( testPalindrome( copy, 0, count - 1 ) == 1 )
showStatus( "Palindrome" );
else
showStatus( "Not a palindrome" );
}
public int makeCopy()
{
copy = new char[ string.length() + 1 ];
int counter = 0;
for ( int i = 0; i < string.length(); i++ ) {
// method charAt returns a character at
// the specified subscript of a String
char c = string.charAt( i );
switch ( c ) {
// skip these punctuation characters
case ' ': case '.': case ';': case ':':
case ',': case '?': case '!': case '-':
break;
default:
copy[ counter++ ] = c;
}
}
copy[ counter ] = '\0'; // as a precaution
return counter;
}
public int testPalindrome( char b[], int left, int right )
{
if ( left == right || left > right )
return 1;
else if ( b[ left ] != b[ right ] )
return 0;
else
return testPalindrome( b, left + 1, right - 1 );
}
}
// Exercise 7.31 Solution
// LinearSearch.java
// Recursively linear search of an array
import javax.swing.*;
import java.awt.*;
import java.awt.event.*;
public class LinearSearch extends JApplet
implements ActionListener {
int a[], element;
String searchKey;
JLabel enterLabel, resultLabel;
JTextField enter, result;
public void init()
{
enterLabel = new JLabel( "Enter integer search key" );
enter = new JTextField( 10 );
enter.addActionListener( this );
resultLabel = new JLabel( "Result" );
result = new JTextField( 25 );
result.setEditable( false );
Container c = getContentPane();
c.setLayout( new FlowLayout() );
c.add( enterLabel );
c.add( enter );
c.add( resultLabel );
c.add( result );
a = new int[ 100 ];
for ( int i = 0; i < a.length; i++ ) // create data
a[ i ] = 2 * i;
}
public int linearSearch( int b[], int key, int low, int high )
{
if ( b[ low ] == key )
return low;
else if ( low == high )
return -1;
else
return linearSearch( b, key, low + 1, high );
}
public void actionPerformed( ActionEvent event )
{
searchKey = event.getActionCommand().toString();
element = linearSearch( a, Integer.parseInt( searchKey ),
0, a.length - 1 );
if ( element != -1 )
result.setText( "Found value in element " + element );
else
result.setText( "Value not found" );
}
}
// Exercise 7.34 Solution
// Print.java
// Program prints a string
import javax.swing.*;
import java.awt.*;
public class Print extends JApplet {
int x = 0;
Graphics g2;
public void paint( Graphics g )
{
int a[] = { 8, 22, 88, 34, 84, 21, 94 };
x = 0;
g2 = g;
printArray( a, 0, a.length - 1 );
}
public void printArray( int b[], int low, int high )
{
g2.drawString( String.valueOf( b[ low ] ), x += 30, 20 );
if ( low == high )
return;
else
printArray( b, low + 1, high );
}
}
// Exercise 7.36 Solution
// Minimum.java
// Program finds the minimum value in an array.
import javax.swing.*;
import java.awt.*;
public class Minimum extends JApplet {
final int MAX = 100;
int smallest;
public void init()
{
smallest = MAX;
}
public void paint( Graphics g )
{
int a[] = { 22, 88, 8, 94, 78, 84, 96, 73, 34 };
int x = 0;
for ( int i = 0; i < a.length; i++ )
g.drawString( String.valueOf( a[ i ] ), x += 20, 40 );
showStatus( String.valueOf( recursiveMinimum( a,
0, a.length - 1 ) ) );
}
public int recursiveMinimum( int b[], int low, int high )
{
if ( b[ low ] < smallest )
smallest = b[ low ];
if ( low == high )
return smallest;
else
return recursiveMinimum( b, low + 1, high );
}
}
// Exercise 7.38 Solution
// Maze.java
// Program traverses a maze
import javax.swing.*;
import java.awt.*;
public class Maze extends JApplet {
final int RIGHT = 1, LEFT = 3, UP = 2, DOWN = 0;
final int X_START = 2, Y_START = 0;
int flag;
char m[][] =
{ { '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#' },
{ '#', '.', '.', '.', '#', '.', '.', '.', '.', '.', '.', '#' },
{ '.', '.', '#', '.', '#', '.', '#', '#', '#', '#', '.', '#' },
{ '#', '#', '#', '.', '#', '.', '.', '.', '.', '#', '.', '#' },
{ '#', '.', '.', '.', '.', '#', '#', '#', '.', '#', '.', '.' },
{ '#', '#', '#', '#', '.', '#', '.', '#', '.', '#', '.', '#' },
{ '#', '.', '.', '#', '.', '#', '.', '#', '.', '#', '.', '#' },
{ '#', '#', '.', '#', '.', '#', '.', '#', '.', '#', '.', '#' },
{ '#', '.', '.', '.', '.', '.', '.', '.', '.', '#', '.', '#' },
{ '#', '#', '#', '#', '#', '#', '.', '#', '#', '#', '.', '#' },
{ '#', '.', '.', '.', '.', '.', '.', '#', '.', '.', '.', '#' },
{ '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#' } };
public void init()
{
mazeTraversal( m, X_START, Y_START, RIGHT );
}
public void mazeTraversal( char m2[][], int x, int y, int direction )
{
m2[ x ][ y ] = 'x';
repaint();
if ( xyAreEdge( x, y ) && x != X_START && y != Y_START ) {
JOptionPane.showMessageDialog(
null, "Maze sucessfully exited!" , "Maze Solver",
JOptionPane.INFORMATION_MESSAGE );
return;
}
else if ( x == X_START && y == Y_START && flag == 1 ) {
JOptionPane.showMessageDialog(
null, "Returned to Starting Location!" , "Maze Solver",
JOptionPane.INFORMATION_MESSAGE );
return;
}
else {
flag = 1;
for ( int move = direction, count = 0; count < 4;
++count, ++move, move %= 4 )
switch ( move ) {
case DOWN:
if ( validMove( x + 1, y ) ) { // move down
mazeTraversal( m2, x + 1, y, LEFT );
return;
}
break;
case RIGHT:
if ( validMove( x, y + 1 ) ) { // move right
mazeTraversal( m2, x, y + 1, DOWN );
return;
}
break;
case UP:
if ( validMove( x - 1, y ) ) { // move up
mazeTraversal( m2, x - 1, y, RIGHT );
return;
}
break;
case LEFT:
if ( validMove( x, y - 1 ) ) { // move left
mazeTraversal( m2, x, y - 1, UP );
return;
}
}
}
}
public boolean validMove( int r, int c )
{
return ( r >= 0 && r <= 11 && c >= 0 &&
c <= 11 && m[ r ][ c ] != '#' );
}
public boolean xyAreEdge( int x1, int y1 )
{
if ( ( x1 == 0 || x1 == 11 ) && ( y1 >= 0 && y1 <= 11 ) )
return true;
else if ( ( y1 == 0 || y1 == 11 ) &&
( x1 >= 0 && x1 <= 11 ) )
return true;
else
return false;
}
public void paint( Graphics g )
{
int x = 5, y = 30;
for ( int r = 0; r < m.length; r++ ) {
for ( int c = 0; c < m[ r ].length; c++ )
g.drawString( String.valueOf( m[ r ][ c ] ), x += 20, y );
y += 10;
x = 5;
}
}
}