Programming Projects

Programming Projects require more problem-solving than Practice Programs and can usually be solved many different ways. Visit www.myprogramminglab.com to complete many of these Programming Projects online and get instant feedback.

Projects 7 through 11 can be written more elegantly using structures or classes. Projects 12 through 15 are meant to be written using multidimen-sional arrays and do not require structures or classes. See Chapters 10 and 11 for information on defining classes and structures.

  1. There are three versions of this project.

    Version 1 (all interactive). Write a program that reads in the average monthly rainfall for a city for each month of the year and then reads in the actual monthly rainfall for each of the previous 12 months. The program then prints out a nicely formatted table showing the rainfall for each of the previous 12 months as well as how much above or below average the rainfall was for each month. The average monthly rainfall is given for the months January, February, and so forth, in order. To obtain the actual rainfall for the previous 12 months, the program first asks what the current month is and then asks for the rainfall figures for the previous 12 months. The output should correctly label the months.

    There are a variety of ways to deal with the month names. One straightforward method is to code the months as integers and then do a conversion before doing the output. A large switch statement is acceptable in an output function. The month input can be handled in any manner you wish, as long as it is relatively easy and pleasant for the user.

    After you have completed this program, produce an enhanced version that also outputs a graph showing the average rainfall and the actual rainfall for each of the previous 12 months. The graph should be similar to the one shown in Display 7.8, except that there should be two bar graphs for each month and they should be labeled as the average rainfall and the rainfall for the most recent month. Your program should ask the user whether she or he wants to see the table or the bar graph and then should display whichever format is requested. Include a loop that allows the user to see either format as often as the user wishes until the user requests that the program end.

    Version 2 (combines interactive and file output). For a more elaborate version, also allow the user to request that the table and graph be output to a file. The file name is entered by the user. This program does everything that the Version 1 program does but has this added feature. To read a file name, you must use material presented in the optional section of Chapter 5 entitled “File Names as Input.”

    Version 3 (all I/O with files). This version is like Version 1 except that input is taken from a file and the output is sent to a file. Since there is no user to interact with, there is no loop to allow repeating the display; both the table and the graph are output to the same file. If this is a class assignment, ask your instructor for instructions on what file names to use.

  2. Hexadecimal numerals are integers written in base 16. The 16 digits used are ‘0’ through ‘9’ plus ‘a’ for the “digit 10”, ‘b’ for the “digit 11”, ‘c’ for the “digit 12”, ‘d’ for the “digit 13”, ‘e’ for the “digit 14”, and ‘f’ for the “digit 15”. For example, the hexadecimal numeral d is the same as base 10 numeral 13 and the hexadecimal numeral 1d is the same as the base 10 numeral 29. Write a C++ program to perform addition of two hexadecimal numerals each with up to 10 digits. If the result of the addition is more than 10 digits long, then simply give the output message “Addition Overflow” and not the result of the addition. Use arrays to store hexadecimal numerals as arrays of characters. Include a loop to repeat this calculation for new numbers until the user says she or he wants to end the program.

  3. Write a function called deleteRepeats that has a partially filled array of characters as a formal parameter and that deletes all repeated letters from the array. Since a partially filled array requires two arguments, the function will actually have two formal parameters: an array parameter and a formal parameter of type int that gives the number of array positions used. When a letter is deleted, the remaining letters are moved forward to fill in the gap. This will create empty positions at the end of the array so that less of the array is used. Since the formal parameter is a partially filled array, a second formal parameter of type int will tell how many array positions are filled. This second formal parameter will be a call-by-reference parameter and will be changed to show how much of the array is used after the repeated letters are deleted.

    For example, consider the following code:

    char a[10];
a[0] = 'a';
a[1] = 'b';
a[2] = 'a';
a[3] = 'c';
int size = 4;
deleteRepeats(a, size);

    After this code is executed, the value of a[0] is 'a', the value of a[1] is 'b', the value of a[2] is 'c', and the value of size is 3. (The value of a[3] is no longer of any concern, since the partially filled array no longer uses this indexed variable.)

    You may assume that the partially filled array contains only lowercase letters. Embed your function in a suitable test program.

  4. The standard deviation of a list of numbers is a measure of how much the numbers deviate from the average. If the standard deviation is small, the numbers are clustered close to the average. If the standard deviation is large, the numbers are scattered far from the average. The standard deviation, S, of a list of N numbers x is defined as follows:

    s=∑i=1N=(xi−x¯)2N

    where x is the average of the N numbers x1, x2, … . Define a function that takes a partially filled array of numbers as its arguments and returns the standard deviation of the numbers in the partially filled array. Since a partially filled array requires two arguments, the function will actually have two formal parameters: an array parameter and a formal parameter of type int that gives the number of array positions used. The numbers in the array will be of type double. Embed your function in a suitable test program.

  5. Write a program that reads in a list of integers into an array with base type int. Provide the facility to either read this array from the keyboard or from a file, at the user’s option. If the user chooses file input, the program should request a file name. You may assume that there are fewer than 50 entries in the array. Your program determines how many entries there are. The output is to be a two-column list. The first column is a list of the distinct array elements; the second column is the count of the number of occurrences of each element. The list should be sorted on entries in the first column, largest to smallest.

    For example, for the input

    −12 3 −12 4 1 1 −12 1 −1 1 2 3 4 2 3 −12

    the output should be

     N   Count
 4   2
 3   3
 2   2
 1   4
−1   1
−12  4

  6. The text discusses the selection sort. We propose a different “sort” routine, the insertion sort. This routine is in a sense the opposite of the selection sort in that it picks up successive elements from the array and inserts each of these into the correct position in an already sorted subarray (at one end of the array we are sorting).

    The array to be sorted is divided into a sorted subarray and to-be-sorted subarray. Initially, the sorted subarray is empty. Each element of the to-be-sorted subarray is picked and inserted into its correct position in the sorted subarray.

    Write a function and a test program to implement the selection sort. Thoroughly test your program.

    Example and hints: The implementation involves an outside loop that selects successive elements in the to-be-sorted subarray and a nested loop that inserts each element in its proper position in the sorted subarray.

    Initially, the sorted subarray is empty, and the to-be-sorted subarray is all of the array:

    a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9]
    8 6 10 2 16 4 18 14 12 10

    Pick the first element, a[0] (that is, 8), and place it in the first position. The inside loop has nothing to do in this first case. The array and subarrays look like this:

    sorted to-be-sorted
    a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9]
    8 6 10 2 16 4 18 14 12 10

    The first element from the to-be-sorted subarray is a[1], which has value 6. Insert this into the sorted subarray in its proper position. These are out of order, so the inside loop must swap values in position 0 and position 1. The result is as follows:

    sorted to-be-sorted
    a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9]
    6 8 10 2 16 4 18 14 10 12

    Note that the sorted subarray has grown by one entry.

    Repeat the process for the first to-be-sorted subarray entry, a[2], finding a place where a[2] can be placed so that the subarray remains sorted. Since a[2] is already in place—that is, it is larger than the largest element in the sorted subarray—the inside loop has nothing to do. The result is as follows:

    sorted to-be-sorted
    a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9]
    6 8 10 2 16 4 18 14 10 12

    Again, pick the first to-be-sorted array element, a[3]. This time the inside loop has to swap values until the value of a[3] is in its proper position. This involves some swapping:

    sorted to-be-sorted
    a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9]
    6 8 10<-->2 16 4 18 14 10 12
    sorted to-be-sorted
    a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9]
    6 8<--->2 10 16 4 18 14 10 12
    sorted to-be-sorted
    a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9]
    6<--->2 8 10 16 4 18 14 10 12

    The result of placing the 2 in the sorted subarray is

    sorted to-be-sorted
    a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9]
    2 6 8 10 16 4 18 14 10 12

    The algorithm continues in this fashion until the to-be-sorted array is empty and the sorted array has all the original array’s elements.

  7. An array can be used to store large integers one digit at a time. For example, the integer 1234 could be stored in the array a by setting a[0] to 1, a[1] to 2, a[2] to 3, and a[3] to 4. However, for this exercise you might find it more useful to store the digits backward, that is, place 4 in a[0], 3 in a[1], 2 in a[2], and 1 in a[3].

    In this exercise you will write a program that reads in two positive integers that are 20 or fewer digits in length and then outputs the sum of the two numbers. Your program will read the digits as values of type char so that the number 1234 is read as the four characters '1', '2', '3', and '4'.

    After they are read into the program, the characters are changed to values of type int. The digits will be read into a partially filled array, and you might find it useful to reverse the order of the elements in the array after the array is filled with data from the keyboard. (Whether or not you reverse the order of the elements in the array is up to you. It can be done either way, and each way has its advantages and disadvantages.)

    Your program will perform the addition by implementing the usual paper-and-pencil addition algorithm. The result of the addition is stored in an array of size 20, and the result is then written to the screen. If the result of the addition is an integer with more than the maximum number of digits (that is, more than 20 digits), then your program should issue a message saying that it has encountered “integer overflow.” You should be able to change the maximum length of the integers by changing only one globally defined constant. Include a loop that allows the user to continue to do more additions until the user says the program should end.

  8. Write a program that will read a line of text and output a list of all the letters that occur in the text together with the number of times each letter occurs in the line. End the line with a period that serves as a sentinel value. The letters should be listed in the following order: the most frequently occurring letter, the next most frequently occurring letter, and so forth. Use two arrays, one to hold integers and one to hold letters. You may assume that the input uses all lowercase letters. For example, the input

    do be do bo.

    should produce output similar to the following:

    Letter Number of Occurrences
    o 3
    d 2
    b 2
    e 1

    Your program will need to sort the arrays according to the values in the integer array. This will require that you modify the function sort given in Display 7.12. You cannot use sort to solve this problem without changing the function. If this is a class assignment, ask your instructor if input/output should be done with the keyboard and screen or if it should be done with files. If it is to be done with files, ask your instructor for instructions on file names.

  9. Write a program to score five-card poker hands into one of the following categories: nothing, one pair, two pairs, three of a kind, straight (in order, with no gaps), flush (all the same suit, for example, all spades), full house (one pair and three of a kind), four of a kind, straight flush (both a straight and a flush). Use two arrays, one to hold the value of the card and one to hold the suit. Include a loop that allows the user to continue to score more hands until the user says the program should end.

  10. Write a program that will allow two users to play tic-tac-toe. The program should ask for moves alternately from player X and player O. The program displays the game positions as follows:

    1 2 3
4 5 6
7 8 9

    The players enter their moves by entering the position number they wish to mark. After each move, the program displays the changed board. A sample board configuration is as follows:

    X X O
4 5 6
O 8 9

  11. Write a program to assign passengers seats in an airplane. Assume a small airplane with seat numbering as follows:

    1 A B C D
2 A B C D
3 A B C D
4 A B C D
5 A B C D
6 A B C D
7 A B C D

    The program should display the seat pattern, with an X marking the seats already assigned. For example, after seats 1A, 2B, and 4C are taken, the display should look like this:

    1 X B C D
2 A X C D
3 A B C D
4 A B X D
5 A B C D
6 A B C D
7 A B C D

    After displaying the seats available, the program prompts for the seat desired, the user types in a seat, and then the display of available seats is updated. This continues until all seats are filled or until the user signals that the program should end. If the user types in a seat that is already assigned, the program should say that that seat is occupied and ask for another choice.

  12. Write a program that accepts input like the program in Display 7.8 and that outputs a bar graph like the one in that display except that your program will output the bars vertically rather than horizontally. A two-dimensional array may be useful.

  13. The mathematician John Horton Conway invented the “Game of Life.” Though not a “game” in any traditional sense, it provides interesting beha-vior that is specified with only a few rules. This project asks you to write a program that allows you to specify an initial configuration. The program follows the rules of LIFE to show the continuing behavior of the configuration.

    LIFE is an organism that lives in a discrete, two-dimensional world. While this world is actually unlimited, we don’t have that luxury, so we restrict the array to 80 characters wide by 22 character positions high. If you have access to a larger screen, by all means use it.

    This world is an array with each cell capable of holding one LIFE cell. Generations mark the passing of time. Each generation brings births and deaths to the LIFE community. The births and deaths follow the following set of rules.

    • We define each cell to have eight neighbor cells. The neighbors of a cell are the cells directly above, below, to the right, to the left, diagonally above to the right and left, and diagonally below to the right and left.

    • If an occupied cell has zero or one neighbors, it dies of loneliness. If an occupied cell has more than three neighbors, it dies of overcrowding.

    • If an empty cell has exactly three occupied neighbor cells, there is a birth of a new cell to replace the empty cell.

    • Births and deaths are instantaneous and occur at the changes of generation. A cell dying for whatever reason may help cause birth, but a newborn cell cannot resurrect a cell that is dying, nor will a cell’s death prevent the death of another, say, by reducing the local population.

    Notes: Some configurations grow from relatively small starting configurations. Others move across the region. It is recommended that for text output you use a rectangular array of char with 80 columns and 22 rows to store the LIFE world’s successive generations. Use an asterisk * to indicate a living cell, and use a blank to indicate an empty (or dead) cell. If you have a screen with more rows than that, by all means make use of the whole screen.

    Examples:

    ***

    becomes

    *
*
*

    then becomes

    ***

    again, and so on.

    Suggestions: Look for stable configurations. That is, look for communities that repeat patterns continually. The number of configurations in the repetition is called the period. There are configurations that are fixed, which continue without change. A possible project is to find such configurations.

    Hints: Define a void function named generation that takes the array we call world, an 80-column by 22-row array of char, which contains the initial configuration. The function scans the array and modifies the cells, marking the cells with births and deaths in accord with the rules listed earlier. This involves examining each cell in turn, either killing the cell, letting it live, or, if the cell is empty, deciding whether a cell should be born. There should be a function display that accepts the array world and displays the array on the screen. Some sort of time delay is appropriate between calls to generation and display. To do this, your program should generate and display the next generation when you press Return. You are at liberty to automate this, but automation is not necessary for the program.

  14. Redo (or do for the first time) Programming Project 10 from Chapter 6. Your program should first load all boy names and girl names from the file into separate arrays. Search for the target name from the arrays, not directly from the file.

  15. Redo (or do for the first time) Programming Project 11 from Chapter 6. Your program should not be hard-coded to create a bar chart of exactly four integers, but should be able to graph an array of up to 100 integers. Scale the graph appropriately in the horizontal and vertical dimensions so the bar chart fits within a 400 by 400 pixel area. You can impose the constraint that all integers in the array are nonnegative. Use the sentinel value of −1 to indicate the end of the values to draw in the bar chart. For example, to create the bar chart with values 20, 40, 60, and 120, your program would operate on the array:

    a[0]  =  20
a[1]  =  40
a[2]  =  60
a[3]  =  120
a[4]  =  −1

    Test your program by creating several bar charts with different values and up to 100 entries and view the resulting SVG files to ensure that they are drawn correctly.

  16. A common memory matching game played by young children is to start with a deck of cards that contains identical pairs. For example, given six cards in the deck, two might be labeled “1,” two might be labeled “2,” and two might be labeled “3.” The cards are shuffled and placed face down on the table. The player then selects two cards that are face down, turns them face up, and if they match they are left face up. If the two cards do not match, they are returned to their original position face down. The game continues in this fashion until all cards are face up.

    Write a program that plays the memory matching game. Use 16 cards that are laid out in a 4 X 4 square and are labeled with pairs of numbers from 1 to 8. Your program should allow the player to specify the cards that she would like to select through a coordinate system.

    For example, suppose the cards are in the following layout:

    A typed coordinate grid in a four-by-four square.

    All of the cards are face down except for the pair 8, which has been located at coordinates (1, 1) and (2, 3). To hide the cards that have been temporarily placed face up, output a large number of newlines to force the old board off the screen.

    (Hint: Use a two-dimensional array for the arrangement of cards and another two-dimensional array that indicates if a card is face up or face down. Write a function that “shuffles” the cards in the array by repeatedly selecting two cards at random and swapping them. Random number generation is described in Chapter 4.)

  17. Your swim school has two swimming instructors, Jeff and Anna. Their current schedules are shown below. An “X” denotes a 1-hour time slot that is occupied with a lesson.

    Two tables showing the lesson schedules for Jeff and Anna.

    Write a program with array(s) capable of storing the schedules. Create a main menu that allows the user to mark a time slot as busy or free for either instructor. Also, add an option to output the schedules to the screen. Next, add an option to output all time slots available for individual lessons (slots when at least one instructor is free). Finally, add an option to output all time slots available for group lessons (when both instructors are free).

  18. Modify Programming Project 17 by adding menu options to load and save the schedules from a file.

  19. Traditional password entry schemes are susceptible to “shoulder surfing” in which an attacker watches an unsuspecting user enter their password or PIN number and uses it later to gain access to the account. One way to combat this problem is with a randomized challenge-response system. In these systems, the user enters different information every time based on a secret in response to a randomly generated challenge. Consider the following scheme in which the password consists of a five-digit PIN number (00000 to 99999). Each digit is assigned a random number that is 1, 2, or 3. The user enters the random numbers that correspond to their PIN instead of their actual PIN numbers.

    For example, consider an actual PIN number of 12345. To authenticate the user would be presented with a screen such as:

    PIN:    0 1 2 3 4 5 6 7 8 9
NUM:    3 2 3 1 1 3 2 2 1 3

    The user would enter 23113 instead of 12345. This doesn’t divulge the password even if an attacker intercepts the entry because 23113 could correspond to other PIN numbers, such as 69440 or 70439. The next time the user logs in, a different sequence of random numbers would be generated, such as:

    PIN:    0 1 2 3 4 5 6 7 8 9
NUM:    1 1 2 3 1 2 2 3 3 3

    Your program should simulate the authentication process. Store an actual PIN number in your program. The program should use an array to assign random numbers to the digits from 0 to 9. Output the random digits to the screen, input the response from the user, and output whether or not the user’s response correctly matches the PIN number.

  20. The Social Security Administration maintains an actuarial life table that contains the probability that a person in the United States will die (http://www.ssa.gov/OACT/STATS/table4c6.html). The death probabilities from this table for 2009 are stored in the file LifeDeathProbability.txt and it is included on the website for the book. There are three values for each row, the age, death probability for a male, and death probability for a female. For example, the first five lines are:

    0 0.006990 0.005728
1 0.000447 0.000373
2 0.000301 0.000241
3 0.000233 0.000186
4 0.000177 0.000150

    This says that a 3 year old female has a 0.000186 chance of dying.

    Write a program that reads the data into arrays from the file. Next, let the user enter his or her sex and age. The program should simulate to what age the user will live by starting with the death probability for the user’s current age and sex. Generate a random number between 0-1; if this number is less than or equal to the death probability then predict that the user will live to the current age. If the random number is greater than the death probability then increase the age by one and repeat the calculation with a new random number for the next probability value.

    If the simulation reaches age 120 then stop and predict that the user will live to 120. This program is merely a simulation and will give different results each time it is run, assuming you change the seed for the random number generator.