BIG C++

Cay Horstmann
& Timothy Budd

**Laboratory Notebook
Chapter 9 - Vectors and Arrays**

Your name: | |

Your email address: | |

Your student ID number: |

Once this form has been customized for your institution, you can use this button

To gain experience with

- using vectors to collect objects
- accessing vector elements and resizing vectors
- passing vectors to functions
- common array algorithms
- using matrices for one-dimensional and two-dimensional arrays

In the text, we have frequently used the `rand_int` function to generate random integers. For example,
`rand_int(1, 6)` generates random numbers between 1 and 6, simulating the throw of a die. In this lab assignment
you will use a vector to test whether the random generator is fair, that is, whether each possible value is generated
approximately equally often.

Your program should ask the user

- how many random numbers should be generated
- what is the lowest number in the range (e.g. 1)
- what is the highest number in the range (e.g. 6)

Make a vector with `high - low + 1` elements, one for each possible outcome. Set each element to 0. Then
keep calling the random number generator. If it returns a value `v`, then increment the counter belonging
to `v`. There is just one catch. The random numbers are generated in the range `low...high`. The
vector subscripts fall in the range `0...high - low`. Therefore, you need to shift the ranges: the vector
element corresponding to the random value `v` has subscript `v - low`.

After all numbers have been generated, print the counters. Here is a typical program run:

How many numbers do you want to generate? 1000 What is the low value? 1 What is the high value? 10 1 78 2 101 3 118 4 97 5 103 6 102 7 112 8 91 9 94 10 104

Vectors are frequently used to store and provide random access to a collection of objects of like type. In the following lab program, you will generate random circle objects and store them in a vector. If a circle does not intersect any of the previously stored circles, you will add it to the vector. Finally, display all circles that you collected in the vector. The result should look something like this: (Note that none of the circles intersect.)

Use the code of the `circle_intersect` function that is given below to test whether two circles intersect.
To randomly generate a circle, simply pick random x- and y- positions between -10 and 10 for the center and a random
radius between 0 and 1. You need to compare each newly generated circle with *all* other circles before you
can add it. (For that reason, we need a vector to hold all circles.) If the new circle passes the test, use `push_back`
to add it to the end of the vector.

#include <vector> using namespace std; #include "ccc_win.cpp" bool circle_intersect(Circle c1, Circle c2) /* PURPOSE: Test if two circles intersect (distance between centers is less than sum of radii) */ { if ( (c1.get_radius() + c2.get_radius()) < sqrt( pow((c2.get_center().get_x() - c1.get_center().get_x()),2) + pow((c2.get_center().get_y() - c1.get_center().get_y()),2))) return false; else return true; } int main() /* PURPOSE: Program to plot a finite number of non-overlapping, randomly sized circles. */ { vector<Circle> rand_circles; int max_circles; double rand_radius; double x,y; Point rand_center; Circle c1; bool intersect; max_circles = cwin.get_int("How many random circles would you like to see ? "); /* YOUR WORK GOES HERE */ return 0; }

We can dynamically resize vectors so that they may grow and shrink. While this is very convenient, it is inefficient. It is best to know the number of elements that you need for your vector when you create it. However, you might come across a situation someday where you do not know the number of elements in advance and need to implement a dynamic vector.

Rewrite the following program so that the user can enter any number of purchases instead of just 10.

#include <vector> #include <iostream> using namespace std; int main() { vector <double> purchases(10); int i; for (i=0;i< 10;i++) { cout <<"Enter a purchase amount"; cin >>purchases[i]; } return (0); }

/* paste program here */

Now, add to the above code to print out the vector in reverse order and remove each element after it is printed.

As with any other data type, when passing a vector as a parameter to a function, you need to choose between
"pass by value" and "pass by reference". If vector elements are being changed in the function,
pass the vector as a reference parameter, for example, `vector<Employee>& empl`. If the vector's
contents are not going to be changed, then pass it as a value, `vector<Employee> empl`, or, for greater
efficiency, as a const reference paramter, like `vector<Employee> const& empl`.

Copying an entire vector into a function can be expensive. Similarly, returning an entire vector as the result
of a function can be expensive. Rewrite (and re-comment) the following function into a procedure that accepts a
reference parameter and updates that parameter instead of returning a new vector as the result. Supply a `main`
function that tests your function.

/* PURPOSE: procedure to reverse elements in an integer vector RECEIVES: int_values - a vector of integer values RETURNS: a copy of the vector, with the elements reversed */ vector<int> reverse(vector<int> int_values) { int temp; vector<int> result(int_values.size()); for(i = 0 ; i < int_values.size() / 2; i++) result[int_values.size() - i - 1] = int_values[i]; return int_values; }

Consider finding an average shipping cost from a sequence of 5 shipments where the lowest shipping cost is discarded.
Write a program to locate the max and min values in `1.52, 3.44, 5.34, 6.43,4.44, 9.87,` discard the lowest, and compute the average of the remaining scores.

How does your program handle duplicate shipping costs ? For example, how would it process 3.43,3.43,3.43,2.11,2,11? What do you think it should do?

Write a program that reads in the names and scores of students and displays the names of the students with the highest and lowest score.

A simple method of carrying out this task would be to have two parallel vectors

vector<string> names; vector<int> scores;

However, you should avoid parallel vectors in your solution.

Vectors are generally more convenient to use than the traditional C-style *arrays*. When defining an array,
you must initialize its size to a constant value, and you cannot change that value again. If you fill the array
gradually, you must keep track of the actual size of the array and ensure that it does not exceed the maximum size.

Rewrite the program in exercise P2, but store the circles in an array

Circle bubbles[BUBBLES_MAXSIZE];

Do not show more circles than `BUBBLES_MAXSIZE`, even if the user requests a larger value.

Vectors store a linear arrangement of values accessed by a single index. Two-dimensional arrays store a tabular
arrangement of values accessed by two indexes, for example `matrix[i][j]`, where `i` is the row
index and `j` is the column index. A common two-dimensional array that you should have seen early on in
your education is a multiplication table. For example, here is the multiplication table up to 5 x 5:

1 | 2 | 3 | 4 | 5 | |

1 | 1 | 2 | 3 | 4 | 5 |

2 | 2 | 4 | 6 | 8 | 10 |

3 | 3 | 6 | 9 | 12 | 15 |

4 | 4 | 8 | 12 | 16 | 20 |

5 | 5 | 10 | 15 | 20 | 25 |

Write a program which asks the user for the number of rows and columns for a multiplication table and prints out the corresponding results.

Crosswords are a type of puzzle which have letters in common. For example,

d across w n

share the letter 'o'.

Write a program that will accept a list of words into a vector of strings, then make a 20 x 20 array of characters that contains a crossword puzzle with these words.

const int PUZZLE_ROWS = 20; const int PUZZLE_COLS = 20; char puzzle[PUZZLE_ROWS][PUZZLE_COLS];

For example, your program when given the list `addle, apple, clowning, incline, plan, burr` it displays
it as:

addle p p clowning e n c l i plan e

That is, use the following method: Place the first word horizontally in the center of the top row. Place the next word vertically. Check if there is a common letter with the preceding word, and if all the squares into which you want to place that word are still empty. (If you cannot place it, skip the word.) Then switch back to horizontal, place the next word if possible, and so on.

Do not forget to send your answers when you are finished.