Table of Contents#### Download Safari Books Online apps: Apple iOS | Android | BlackBerry

### Exercises

Entire Site

Free Trial

Safari Books Online is a digital library providing on-demand subscription access to thousands of learning resources.

6.6 | Fill in the blanks in each of the following:
C stores lists of values in __________. The elements of an array are related by the fact that they __________. When referring to an array element, the position number contained within parentheses is called a(n) __________. The names of the five elements of array `p`are __________, __________, __________, and __________.The contents of a particular element of an array is called the __________ of that element. Naming an array, stating its type and specifying the number of elements in the array is called __________ the array. The process of placing the elements of an array into either ascending or descending order is called __________. In a double-subscripted array, the first subscript (by convention) identifies the __________ of an element and the second subscript (by convention) identifies the __________ of an element. An m-by-n array contains __________ rows, __________ columns and __________ elements. The name of the element in row 3 and column 5 of array `d`is __________.
| ||||||||||||||||

6.7 | State which of the following are true and which are false. If false, explain why.
To refer to a particular location or element within an array, we specify the name of the array and the value of the particular element. An array definition reserves space for the array. To indicate that 100 locations should be reserved for integer array `p`, write90 `p[ 100 ];` A C program that initializes the elements of a 15-element array to zero must contain one `for`statement.A C program that totals the elements of a double-subscripted array must contain nested `for`statements.The mean, median and mode of the following set of values are 5, 6 and 7, respectively: 1, 2, 5, 6, 7, 7, 7.
| ||||||||||||||||

6.8 | Write statements to accomplish each of the following:
Display the value of the seventh element of character array `f`.Input a value into element 4 of single-subscripted floating-point array `b`.Initialize each of the five elements of single-subscripted integer array `g`to`8`.Total the elements of floating-point array `c`of 100 elements.Copy array `a`into the first portion of array`b`. Assume`double a[ 11 ], b[ 34 ];`Determine and print the smallest and largest values contained in 99-element floating-point array `w`.
| ||||||||||||||||

6.9 | Consider a 2-by-5 integer array t.
Write a definition for `t`.How many rows does `t`have?How many columns does `t`have?How many elements does `t`have?Write the names of all the elements in the second row of `t`.Write the names of all the elements in the third column of `t`.Write a single statement that sets the element of `t`in row 1 and column 2 to zero.Write a series of statements that initialize each element of `t`to zero. Do not use a repetition structure.Write a nested `for`statement that initializes each element of`t`to zero.Write a statement that inputs the values for the elements of `t`from the terminal.Write a series of statements that determine and print the smallest value in array `t`.Write a statement that totals the elements of the fourth column of `t`.
| ||||||||||||||||

6.10 | Use a single-subscripted array to solve the following problem. A company pays its sales-people 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 $3000 in sales in a week receives $200 plus 9% of $3000, or a total of $470. Write a C 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):
$200–299 $300–399 $400–499 $500–599 $600–699 $700–799 $800–899 $900–999 $1000 and over
| ||||||||||||||||

6.11 | The bubble sort presented in Fig. 6.15 is inefficient for large arrays. Make the following simple modifications to improve the performance of the bubble sort.
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. 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 whether any swaps have been made. If none has been made, then the data must already be in the proper order, so the program should terminate. If swaps have been made, then at least one more pass is needed.
| ||||||||||||||||

6.12 | Write single statements that perform each of the following single-subscripted array operations:
Initialize the 10 elements of integer array `counts`to zeros.Add 1 to each of the 15 elements of integer array `bonus`.Read the 12 values of floating-point array `monthlyTemperatures`from the keyboard.Print the five values of integer array `bestScores`in column format.
| ||||||||||||||||

6.13 | Find the error(s) in each of the following statements:
Assume: char `str[`5`];`90 scanf( "%s", str ); /* User types hello */ Assume: int `a[`3`];`90 printf( "$d %d %d\n", a[ 1 ], a[ 2 ], a[ 3 ] ); 90 double f[ 3 ] = { 1.1, 10.01, 100.001, 1000.0001 }; Assume: double `d[`2`][`10`];`90 d[ 1, 9 ] = 2.345;
| ||||||||||||||||

6.14 | Modify the program of Fig. 6.16 so function mode is capable of handling a tie for the mode value. Also modify function median so the two middle elements are averaged in an array with an even number of elements.
| ||||||||||||||||

6.15 | 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. | ||||||||||||||||

6.16 | 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:
90 for ( row = 0; row <= 2; row++ ) for ( column = 0; column <= 4; column++ ) sales[ row ][ column ] = 0; | ||||||||||||||||

6.17 | What does the following program do?
| ||||||||||||||||

6.18 | What does the following program do?
| ||||||||||||||||

6.19 | Write a program that simulates the rolling of two dice. The program should use rand to roll the first die, and should use rand 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, then the sum of the two values will vary from 2 to 12, with 7 being the most frequent sum and 2 and 12 the least frequent sums.] Figure 6.23 shows the 36 possible combinations of the two dice. Your program should roll the two 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. 6.23. Dice rolling outcomes.
| ||||||||||||||||

6.20 | Write a program that runs 1000 games of craps (without human intervention) and answers each of the following questions:
How many games are won on the first roll, second roll, ..., twentieth roll and after the twentieth roll? How many games are lost on the first roll, second roll, ..., twentieth roll and after the twentieth roll? 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?] What is the average length of a game of craps? Do the chances of winning improve with the length of the game?
| ||||||||||||||||

6.21 | (Airline Reservations System) A small airline has just purchased a computer for its new automated reservations system. The president has asked you 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: 90 Please type 1 for "first class" Please type 2 for "economy" If the person types 1, then your program should assign a seat in the first class section (seats 1–5). If the person types 2, then your program should assign a seat in the economy section (seats 6–10). Your program should then print a boarding pass indicating the person’s seat number and whether it is in the first class or economy section of the plane. Use a 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 element 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 first class section is full, your program should ask the person if it is acceptable to be placed in the economy section (and vice versa). If yes, then make the appropriate seat assignment. If no, then print the message | ||||||||||||||||

6.22 | Use a double-subscripted array to solve the following problem. A company has four sales-people (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 salesperson number The product number 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 | ||||||||||||||||

6.23 | (Turtle Graphics) The Logo language, which is particularly popular among personal computer users, made the concept of turtle graphics famous. Imagine a mechanical turtle that walks around the room under the control of a C 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 50-by-50 array 90 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 | ||||||||||||||||

6.24 | (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. 6.25. Draw an 8-by-8 chessboard on a sheet of paper and attempt a Knight’s Tour by hand. Put a `1`in the first square you move to, a`2`in the second square, a`3`in the third, and so on. Before starting the tour, estimate how far you think you will get, remembering that a full tour consists of 64 moves. How far did you get? Were you close to the estimate?Now let us develop a program that will move the knight around a chessboard. The board itself 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. 6.25 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,`horizontal`and`vertical`, as follows:90 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 ##### Fig. 6.25. The eight possible moves of the knight.Let the variables `currentRow`and`currentColumn`indicate the row and column of the knight’s current position on the board. To make a move of type`moveNumber`, where`moveNumber`is between 0 and 7, your program uses the statements90 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. Remember to test each potential move to see if the knight has already visited that square. And, of course, test every potential move to make sure that the knight does not land off the chessboard. Now write a program to move the knight around the chessboard. Run the program. How many moves did the knight make?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 in some sense more troublesome than the squares nearer the center of the board. In fact, the most troublesome, or inaccessible, squares are the four corners. Intuition may suggest that you should attempt to move the knight to the most troublesome squares first and leave open those that are easiest to get to, so that when the board gets congested near the end of the tour, there will be a greater chance of success. We may develop an “accessibility heuristic” by classifying each of the squares according to how accessible it is and always moving the knight to the square (within the knight’s L-shaped moves, of course) that is most inaccessible. We label a doublesubscripted array `accessibility`with numbers indicating from how many squares each particular square is accessible. On a blank chessboard, the center squares are therefore rated as`8`s, the corner squares are rated as`2`s, and the other squares have accessibility numbers of`3`,`4`, or`6`as follows:90 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 Now write a version of the Knight’s Tour program using the accessibility heuristic. At any time, the knight should 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 and 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? Now modify the program to run 64 tours, one from each square of the chessboard. How many full tours did you get? Write a version of the Knight’s Tour program which, 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.
| ||||||||||||||||

6.25 | (Knight’s Tour: Brute-Force Approaches) In Exercise 6.24 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 many problems with sheer computer power and relatively unsophisticated algorithms. Let us call this approach “brute-force” problem solving. Use random number generation to enable the knight to walk around the chess board (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? 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? 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? 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.
| ||||||||||||||||

6.26 | (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—that is, so that no two queens are in the same row, the same column, or along the same diagonal? Use the kind of thinking developed in Exercise 6.24 to formulate a heuristic for solving the Eight Queens problem. Run your program. [Hint: It is possible to assign a numeric value to each square of the chessboard indicating how many squares of an empty chessboard are “eliminated” once a queen is placed in that square. For example, each of the four corners would be assigned the value 22, as in Fig. 6.26.]
## Fig. 6.26. The 22 squares eliminated by placing a queen in the upper-left corner.
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? | ||||||||||||||||

6.27 | (Eight Queens: Brute-Force Approaches) In this problem you will develop several brute-orce approaches to solving the Eight Queens problem introduced in Exercise 6.26.
Solve the Eight Queens problem, using the random brute-force technique developed in Exercise 6.25. Use an exhaustive technique (i.e., try all possible combinations of eight queens on the chessboard). Why do you suppose the exhaustive brute-force approach may not be appropriate for solving the Eight Queens problem? Compare and contrast the random brute-force and exhaustive brute-force approaches in general.
| ||||||||||||||||

6.28 | (Duplicate Elimination) In Chapter 12, we explore the high-speed binary search tree data structure. One feature of a binary search tree is that duplicate values are discarded when insertions are made into the tree. This is referred to as duplicate elimination. Write a program that produces 20 random numbers between 1 and 20. The program should store all nonduplicate values in an array. Use the smallest possible array to accomplish this task. | ||||||||||||||||

6.29 | (Knight’s Tour: Closed Tour Test) In the Knight’s Tour, a full tour is 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 location in which the knight started the tour. Modify the Knight’s Tour program you wrote in Exercise 6.24 to test for a closed tour if a full tour has occurred. | ||||||||||||||||

6.30 | (The Sieve of Eratosthenes) A prime integer is any integer greater than 1 that can be divided evenly only by itself and 1. The Sieve of Eratosthenes is a method of finding prime numbers. It works as follows:
Create an array with all elements initialized to 1 (true). Array elements with prime subscripts will remain 1. All other array elements will eventually be set to zero. Starting with array subscript 2 (subscript 1 is not prime), every time an array element is found whose value is 1, loop through the remainder of the array and set to zero every element whose subscript is a multiple of the subscript for the element with value 1. For array subscript 2, all elements beyond 2 in the array that are multiples of 2 will be set to zero (subscripts 4, 6, 8, 10, and so on.). For array subscript 3, all elements beyond 3 in the array that are multiples of 3 will be set to zero (subscripts 6, 9, 12, 15, and so on.).
When this process is complete, the array elements that are still set to 1 indicate that the subscript is a prime number. 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. |