4.17. 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 two values should be calculated. [NOTE: each die can show an integer value from 1 to 6, so the sum of the two values will vary from 2 to 12, with 7 being the most frequent sum and 2 and 12 being the least frequent sum.] Fig 4.28 shows the 36 possible combination 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 result 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 the rolls should be 7).
Fig 4.28 The 36 possible outcomeof rolling two dice.
|
1 |
2 |
3 |
4 |
5 |
6 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
4.20. (Airline Reservation systems) A small airline has just purchased a computer for its new automated reservation system. You have been asked to program the new computer. 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 "First Class" and Please type 2 for "Economy". If the person types 1, your program should assign a seat in first class section (seats 1-5). if the person types 2, your program should assign a seat in the economy section (seats 6-10). Your program should 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 all the 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 first class section class is full, your program should ask the person if it is acceptable to be placed in the economy section 9 and vice versa). if yes, then make the appropriate seat assignment. If no, then print the message "Next flight leaves in 3 hours."
4.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 trace 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 as position 0,0 of the floor with its pen up. The set of turtle commands your program must process are shown in FIG 4.29.
Suppose that the turtle is somewhere near the center of the floor. The following "program" would draw and print a 12 by 12 square and end with the pen in the up position.
FIG. 4.29 Turtle graphics commands.
| Command |
Meaning |
1 |
Pen up |
2 |
Pen down |
3 |
Turn right |
4 |
Turn left |
5 , n |
Move forward n spaces |
6 |
Print 20-by-20 array |
9 |
End of data (sentinel) |
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 element of the array floor to 1's. 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.
4.30. (
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 sorted array is referred to as a bucket. Write a function
bucketSort that takes an integer array and the array size as arguments and perform as follows:
a) Place each value of the single-subscripted array into a row of 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 ten digit) and 97 is placed in row 9. After the gathering pass, the order of 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 zero and 97 is placed in row zero (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 10 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 data back to the original array on each pass. Another possibility is to create a second double-subscripted array and repeatedly swap the data between the two bucket arrays.
4.31. (Selection Sort) A selection sort searches an array 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 array results in one element being placed in its proper location. This sort performs comparably to the bubble sort 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 function selectionSort to perform this algorithm.
4.36. (Print an array) Write a recursive function printarray that takes an array and the size of the array as arguments and returns nothing. The function should stop processing and return when it receives an array of size zero.
4.38. (Find the minimum value in an array) Write a recursive function recursiveMinimum that takes an integer array and the array size as arguments and return the smallest element of the array. The function should stop processing and return when it receives an array of 1 element.
