Programming Exercise: Set Comparisons - Matching
In this exercise, we will develop a technique for comparing the
contents of two multi-sets (the mathematical term "set" means roughly
"group of items whose order doesn't matter, which cannot have
duplicated values." "Multi-set" means "set of items where each value
may be duplicated an arbitrary number of times.")
Remeber that to use vectors you need to have #include
<vector> in your file.
3 points
- Write a function bool hasVal(const vector<int>& l,
int n) that returns true if n appears in l and false
otherwise.
- Write a function void replaceVal(vector <int>& l, int
n) that replaces the first instance of n in l with
-1. For example, if the list l begins as [1, 5, 3, 10, 4] and you call
replaceVal(l, 3) then the list would become [1, 5, -1, 10, 4].
- Write a function bool isSameSet(vector<int> l1,
vector<int> l2) that loops through the values of l1,
and tries to find them in l2. If they don't exist, return false,
otherwise, call replaceVal on them and continue. If each value
can be found, return true.
Extra Credit Options
- 1 points: Rewrite all of these functions only using
while loops (no for loops).
- 2 points: Rewrite all of these functions using
only recursion, no loops.