Introduction
This lab will provide students with an introduction to the fundamentals of one-dimensional arrays in the C++ programming language. The focus of this lab is on how to solve complex problems using one-dimensional arrays. At the end of this lab, students will…
- Be able to solve simple problems using one-dimensional arrays
- Understand the structure of one-dimensional arrays in C++
- Understand the use of one-dimensional arrays as function parameters
These exercises have two different types of answers. Some questions ask for answers to specific questions; you should collect these answers in a Microsoft Word document. Other exercises ask you to write code. Let’s begin!
Part 1: One-Dimensional Arrays in C++
Many problems in Computer Science involve manipulating one or more lists of information. In programming terms, these lists are called arrays. An array is a block of memory storage that consists of multiple elements, all of the same data type. Arrays are very much like a list or collection of variables – an array has one name, but the individual elements can be accessed on their own. For example, the following C++ definition creates an array of 16 integer variables:
int my_list[16];
This variable declaration works differently than normal variables. A normal variable of type int typically takes up four bytes of memory; The array definition above asks the computer to allocate 16 contiguous four-byte segments of memory (64 bytes total). We have said before that a variable name is simply a symbolic identifier for a memory address; in the case of an array, the name refers to the address of the first element in the array only.
The [16] in the aforementioned array declaration indicates the number of elements (size) of the array. The individual elements of the array can be accessed by means of a computable index or subscript; this allows us to refer to each integer variable in the array separately. Array indices start at zero and end at one less than the size of the array. In our earlier example, the valid indices are [0…15]. We can use subscripts to access the elements in the following manner:
int my_list[16];
my_list[5] = 94;
my_list[7] = 41;
my_list[0] = 300;
We use an integer as the subscript/index. This integer can be a literal, a variable containing an integer value, or an expression that evaluates to an integer value. We say the index is computed because the computer uses the subscript given to compute the location in memory of the requested array element; for instance, if the code calls for my_list[5] then the computer will compute the memory address of the 6th element in the array according to the formula:
(Address of 0th element) + (5 * (sizeof int))
Where (sizeof int) is four bytes (on 32-bit computers). The use arrays means that there will be a need to process each element in an array with some repeated operation. For example, suppose we wanted to output the entire contents of an array, one element at a time. Since the indices are sequential (0, 1, 2, 3, …) and the process involves repetition, we can use a for loop:
for (int i = 0; i < 16; i++)
{
cout << my_list[i] << endl;
}
At this point you should watch and listen to the One-Dimensional Arrays in C++ podcast:
Arrays as Parameters
Like other variables, arrays can be passed to functions as arguments. However, doing so requires special syntax. Remember that an argument is a value used in a function call. An argument can be either a literal value (e.g. 10, “Ricky Bobby”, 24.22) or a variable. Each argument corresponds to a function parameter, a “placeholder” that needs to be “filled” in a function call. Parameters are used by a function to complete its work.
Most of the parameters we have used are value parameters. This means that the arguments we provide have their value passed to the function; changes to the parameters inside the function have no effect on the actual argument. Array arguments are treated as reference parameters. When an array is passed as a parameter, the memory address of the element at index 0 is passed rather than a copy of the value stored at that memory address. Because the memory address of the array is passed as the argument to a function, any changes made to the contents of the array parameter are actually made to the array argument in the calling function.
For example, suppose we had a function called fillList which took an array as a parameter. We could specify an array parameter in the function header by using the [ ] notation to indicate the parameter is an array:
int fillList(double list[], int size)
{
// code for the function body…
}
This identifies list as an array parameter. Inside the function, the variable list can be accessed just like any other array. When the function is called, the corresponding argument of an array type is specified by using the name of the array variable, just like other arguments:
double my_list[10]; int num_items = fillList(my_list, 10);
Note that the [ ] are not used when specifying an argument to a function call. It is important to remember that the called function has no knowledge of the actual size of the array. In this example, the second argument (“10”) is used to signify the size of the array. This argument corresponds to an integer parameter (“size”) that the function uses to help it do its work.
If we want to pass an array by value, simply precede the data type in the parameter list by the keyword const. A const parameter is constant, i.e. it cannot be altered by the function; a const parameter can have its contents fetched and examined, but not changed. This restriction is enforced by the C++ compiler. For example:
void computeSum(const double list[], int size)
{
// code for the function body; changes cannot be made to the
// contents of the parameter “list” without a compile error.
}
At this point you should watch and listen to the Reference and Value Parameters in C++ podcast to learn more about these types of parameters:
Part 2: Applications of Arrays
The following exercises represent just a sample of the types of problems which use arrays. Any problem which needs to process large amounts of data is well-suited to the use of arrays.
Arrays and Grade Calculators
The GradeCalculator program from the “For Loops” lab is a great example of a problem well-suited to arrays. The problem involves a repeated set of instructions (the instructions to provide input) which differ only in terms of the prompt: each user prompt includes a number (#0, #1, etc) which increases by 1 each time. The repeated prompting of the user has a defined starting point (Exam Score #0) and a defined ending point (Exam Score #10). Consider the input/output dialog:
Enter the student ID: 11AB Enter Exam Score #0: 80 Enter Exam Score #1: 82 Enter Exam Score #2: 87 Enter Exam Score #3: 74 Enter Exam Score #4: 68 Enter Exam Score #5: 89 Enter Exam Score #6: 80 Enter Exam Score #7: 92 Enter Exam Score #8: 83 Enter Exam Score #9: 81 Enter Exam Score #10: 84 The lowest score was removed (68). Student 11AB has a total score of 832 (83.20 percent, B).
The succession of prompts is an example of counter-driven repetition, and the set of 11 scores could easily be stored in an array.
Exercise 1: Create a new C++ program called GradeCalculator2.cpp and re-construct the GradeCalculator program using arrays. A few notes as you construct the program:
- Your input function must place the input values into an array.
- Your function which computes the average must iterate through the array as part of its calculation. Use for loops!
Compile and Build your program to verify it works as expected. Enter in several different tests cases to verify your program’s logic.
Arrays and Bacterial Growth
An array-based computer program can be useful in modeling the projected growth of bacteria. Uninhibited bacterial growth is said to follow the exponential law given by
Where
- N(t) is the number of bacteria present at time t.
- N0 is the initial number of bacteria present.
- k is a positive constant of proportionality.
- t is the number of hours elapsed.
Suppose we wanted to write a C++ program to compute the number of bacteria present at increasing time steps 0, 1, 2, 3, 4, 5, …, 10 hours. We could use an array of double values to store the number of bacteria at each time step. Once the computations were complete, the program could iterate through the array and output the values to the screen.
Exercise 2: Create a new C++ program called BacterialGrowth.cpp. Construct the program described above. User input should consist of the following:
- k, a
doublevalue in the range [0-1); - n0, the initial population size in the range [1-1000].
Your user inputs should be validated according to the rules above. Your program must use arrays to store your computations. Once the processing is complete, your program must loop through the array and produce a table in the following format:
Bacterial Growth Summary
Hour Population
---- ----------
NN NNNNN.NNN
NN NNNNN.NNN
.. . . .
Please note that C++ provides the following function to compute the exponential value (e):
double exp(double power);
The following test cases are provided for this exercise:
Test Case #1:
Enter the constant of proportionality [0.0-1.0): 0.2
Enter the size of the initial population [1-1000]: 10
Bacterial Growth Summary
Hour Population
---- ----------
0 10.000
1 12.214
2 14.918
3 18.221
4 22.255
5 27.183
6 33.201
7 40.552
8 49.530
9 60.496
10 73.891
Test Case #2:
Enter the constant of proportionality [0.0-1.0): 0.5
Enter the size of the initial population [1-1000]: 1000
Bacterial Growth Summary
Hour Population
---- ----------
0 1000.000
1 1648.721
2 2718.282
3 4481.689
4 7389.056
5 12182.494
6 20085.537
7 33115.452
8 54598.150
9 90017.131
10 148413.159
Test Case #3:
Enter the constant of proportionality [0.0-1.0): 1.0
*** Invalid input; the value must be in the range [0.0...1.0). Try again.
Enter the constant of proportionality [0.0-1.0): -1
*** Invalid input; the value must be in the range [0.0...1.0). Try again.
Enter the constant of proportionality [0.0-1.0): 0.456
Enter the size of the initial population [1-1000]: 0
*** Invalid input; the value must be in the range [1...1000]. Try again.
Enter the size of the initial population [1-1000]: 1001
*** Invalid input; the value must be in the range [1...1000]. Try again.
Enter the size of the initial population [1-1000]: 2
Bacterial Growth Summary
Hour Population
---- ----------
0 2.000
1 3.156
2 4.979
3 7.855
4 12.393
5 19.553
6 30.850
7 48.674
8 76.796
9 121.164
10 191.167
Sieve of Eratosthenes
A prime number is a number that is only divisible by itself and one (1). One of the earliest known algorithms for determining a set of prime numbers up to a given limit comes from Eratosthenes of Cyrene, who is said to have come up with the algorithm in the third century B.C. This algorithm is called a sieve because it distinguishes the desired facts (i.e. prime numbers) from the undesired facts (i.e. non-primes).
Exercise 3: Construct a C++ program to print all of the prime numbers in the range [1…100]. The algorithm you should use is as follows:
- Create an array to hold a boolean “flag” value for all the numbers in [1…100].
- Note: Remember that array indices always start at 0; it is recommend that your array declaration create an array which holds 101 values with indices [0…100]. The value at index 0 will be unused.
- The value in the list at index i should be true if number i is prime, and it should be false otherwise. Initially, set all the values in the list to be true.
- Determine if each number i is prime. If it is, set the list value for the number i to true, and set the list value for all multiples of i to be false, since if a number is a multiple of another number it cannot be prime.
- Go back through the list and show all the prime numbers, indicated by a true value at the list position.
No user input is needed for this program. Think about what type of control structure is needed to solve the problem; given that you know the bounds of your list, the best solution should be obvious. Test your program thoroughly when finished.
Election Results
Congratulations! The U.S. Election Commission has ordered you to write a computer program to help it determine who will be the next President.
Exercise 4: Create a C++ program which asks the user for the following input values:
- The candidate’s first name, a
string; - The candidate’s vote total, an
int.
Your program should repeatedly prompt the user for these two pieces of information until the user has entered three (3) names. Your program should validate each vote total to make sure that the number of votes is greater than or equal to 0. Your input values for each candidate should be stored in two parallel arrays (one of type string, one of type int).
Parallel arrays mean that the first candidates’ name is stored in index 0 of the “names” array while his vote total is stored at index 0 of the “votes” array, the second candidates’ name is stored in index 1 of the “names” array while his vote total is stored at index 1 of the “votes” array and so on. You will always have exactly three (3) sets of input values.
Once the input is complete, process your arrays by displaying a three-column table for the user listing the candidate’s first name, the total votes they received, and the percentage of the total vote they received. For example, the following output displays the results of the 2004 election:
Candidate First Name Vote Total Percentage
==================== ========== ==========
George 62040606 51.07
John 59028109 48.59
Ralph 411304 0.34
Remember that the percentage of the vote received is the candidates’ vote total divided by the total number of votes for all candidates. You will need to compute this “total vote” before calculating any of the individual percentages. Your prompts should be descriptive messages, and the numerical output for percentages should use two (2) digits of precision. Beware of integer division! Remember that you can use typecasting to avoid this issue (e.g. (double)x / (double)y). Here are few sample tests:
Test Case #1: 2004 Presidential Election
Enter the Candidate's first name: George
Enter the Candidate's vote total: 62040606
Enter the Candidate's first name: John
Enter the Candidate's vote total: 59028109
Enter the Candidate's first name: Ralph
Enter the Candidate's vote total: 411304
Candidate First Name Vote Total Percentage
==================== ========== ==========
George 62040606 51.07
John 59028109 48.59
Ralph 411304 0.34
Test Case #2: 1980 Presidential Election
Enter the Candidate's first name: Ronald
Enter the Candidate's vote total: 43903230
Enter the Candidate's first name: Jimmy
Enter the Candidate's vote total: 35480115
Enter the Candidate's first name: John
Enter the Candidate's vote total: 5719850
Candidate First Name Vote Total Percentage
==================== ========== ==========
Ronald 43903230 51.59
Jimmy 35480115 41.69
John 5719850 6.72
Test Case #3: Fictional Presidential Election
Enter the Candidate's first name: Manny
Enter the Candidate's vote total: 500
Enter the Candidate's first name: Moe
Enter the Candidate's vote total: 100
Enter the Candidate's first name: Jack
Enter the Candidate's vote total: 400
Candidate First Name Vote Total Percentage
==================== ========== ==========
Manny 500 50.00
Moe 100 10.00
Jack 400 40.00
Part 4: Vocabulary Words
You will be assessed on your knowledge of the following terms and concepts as well as the C++ concepts discussed in this document. As a result, you are encouraged to review these terms in the preceding document.
Array – An array is a block of memory storage that consists of multiple elements, all of the same data type. An array has one name, but the individual elements can be accessed on their own.
Index – An integer which allows us to refer to each element of an array separately. Array indices start at zero and end at one less than the size of the array.
Reference Parameters – function parameters for which the arguments provided have their memory address passed to the function; changes to the parameters inside the function are made to the actual argument(s).
Subscript – see the definition for Index.
Value Parameters – function parameters for which the arguments provided have their value passed to the function; changes to the parameters inside the function have no effect on the actual argument.