You may want to review the idea of a "Design Recipe" from the following wiki pages:
Before starting this lab:
Create a new subdirectory ~/cisc105/lab10, and make that your working directory.
The files for this lab are in the directory /www/htdocs/CIS/105/haggerty/07F/labs/lab10
The work you do in step 2 of this lab is only for practice and learning. There is nothing to turn in from this step of the lab.
So you could skip it if you wanted to, and neither your instructor nor your TA would know.
Well, actually that's not entirely true.
We'd know if,
So, don't skip this step.
We have learned about some simple data types in C++ such as int, char, double
and
bool
. In this section we will look at structures.
Note: The following was borrowed from: http://ece-www.colorado.edu/~pfefferz/cpp/tutorial/tutorial/tut3-5.html on 11/24/2007
A data structure is a set of diverse types of data that may have different lengths grouped together under a unique declaration. Its form is the following:where model_name is a name for the model of the structure type and the optional parameter object_name is a valid identifier (or identifiers) for structure object instantiations. Within curly brackets { } they are the types and their sub-identifiers corresponding to the elements that compose the structure.struct model_name { type1 element1; type2 element2; type3 element3; . . } object_name;
If the structure definition includes the parameter model_name (optional), that parameter becomes a valid type name equivalent to the structure. For example:
We have first defined the structure model products with two fields: name and price, each of a different type. We have then used the name of the structure type (products) to declare three objects of that type: apple, orange and melon.struct products { string name; float price; } ; products apple; products orange, melon;
Once declared, products has become a new valid type name like the fundamental ones int, char or short and we are able to declare objects (variables) of that type.
The optional field object_name that can go at the end of the structure declaration serves to directly declare objects of the structure type. For example, we can also declare the structure objects apple, orange and melon this way:
Moreover, in cases like the last one in which we took advantage of the declaration of the structure model to declare objects of it, the parameter model_name (in this case products) becomes optional. Although if model_name is not included it will not be possible to declare more objects of this same model later.struct products { string name; float price; } apple, orange, melon;
It is important to clearly differentiate between what is a structure model, and what is a structure object. Using the terms we used with variables, the model is the type, and the object is the variable. We can instantiate many objects (variables) from a single model (type).
Once we have declared our three objects of a determined structure model (apple, orange and melon) we can operate with the fields that form them. To do that we have to use a point (.) inserted between the object name and the field name. For example, we could operate with any of these elements as if they were standard variables of their respective types:
apple.nameeach one being of its corresponding data type: apple.name, orange.name and melon.name are of type string, and apple.price, orange.price and melon.price are of type float.
apple.price
orange.name
orange.price
melon.name
melon.price
Now look at struct1.cc
and examine how a structure works in
code. Make sure you understand how a structure works... There is
nothing to turn in for this step but you may be tested on this in
the future!!! Could you write a structure for a student with
the following information: first name, last name, expected graduation year
and GPA? If so, you are ready to move on!
The directory lab10 contains several files this week pertaining to recursion. More examples have been—or will be—discussed in lecture.
In this step, we'll review the recursion related files in the lab10 directory. Then, in Step 4, you'll then be assigned the task of writing several recursive functions yourself.
You may need more discussion of recursion in lecture to know how to tackle these problems. If so, raise this issue with your instructor. These problems are appearing in lab at this time so that you will be more inclined to want to hear more about recursion in the next several lectures!
As you may know, finding the sum of a vector in MATLAB is easy—we can use the built-in MATLAB function sum()
:
>> sum([4 3 0 3]) ans = 10 >> sum([1 1 2 5 1]) ans = 10 >> sum([3 5 1]) ans = 9 >>
However, it is an important programming skill to know how to find the sum of a vector (or an array) without using a built-in function, because many languages, such as C++, do not have such a function.
So here are two examples of such functions. The first, addElements()
in mySum1.cc
, initializes the result to zero, and then uses a for loop to step through every element in the vector, adding it into the sum found so far. This is a very common approach:
int addElements(int list[], int size) { int result = 0; for(int i = 0; i < size; i++) result += list[i]; return result; }
The second example, mySum3.m
, uses an entirely different approach. This approach uses the following reasoning:
There are only three possibilities for a vector x:
x
is an empty vector, which has the sum 0
x
is really just a single element—hence x
is already the sum of the vector x
x
is vector with at least two elements, and can thus be divided into two parts;
x[0]
The first two cases are trivial to code:
if ( size ) return result; elseif ( lower == size-1) return list[lower]; else ...
But the third case is where we do the really neat trick. We use a kind of mathematical Jiu-Jitsu to turn the problem against itself, and thus emerge victorious against our opponent.
list[0]
, plus the sum of the rest of the vector else result = list[lower] + addElements(list, lower + 1, size);
At first, you may be worried that this could not possibly work.
The trick is that the recursive call—that is the function call to mySum2()
inside the definition of mySum2()
is on a smaller vector.
And if the vector is getting smaller with each successive recursive call, eventually we hit one of the base cases—the parts of the function that do not use recursion. At that point, the recursive calls don't go any deeper—we bottom out, and the computation starts winding back out, returning the result we are looking for.
Many students—especially those who have been programming with for loops for a long time—may wonder why recursion is useful. There are several reasons:
One of the strengths of using recursion is that it is easy to reason about the problem—construct a logical argument—and then translate that argument directly into code. This often results in code that is easy to understand and maintain.
Don't believe everything you hear, or read. It is true that some recursive functions are slower than the corresponding function written using a for loop—but there are also cases where the recursive version is nearly as fast, or even faster, than the for-loop version. Many textbooks contain statements about recursion that are simply not accurate.
Also, efficiency of computer time is not the only thing we need to optimize for. We also need to take into account how easy code is to write, maintain, and debug. It is often the case that programmer time is more expensive than computer time!
By the way, the word for solutions that use a for loop is iteration.
We contrast these two techniques:
Now, some exercises to turn in for credit.
For each of these exercises:
Write a function xAppearsInA(x,a)
that uses a for loop (iteration) to solve this problem:
a
, and an integer x
, return true
if x
appears in v
, and false if x
does not. Rules:
for
loop to check each value in the vector. Note: The file xAppearsInA.cc
does not separate out the test file from the code
and should be used as a template only... Make sure that you hand in separate files for xAppearsInA.cc
and testXAppearsInA.cc
(see lab09 if you are unsure how to do this!).
Write a function doesXAppearInV(x,a)
that solves the same problem as Step 4a, but using recursion.
Again, do not use any built-in C++ functions
Write a function myMin(v, lower, size). This is similar to the myMax() function from lab08—but
this time, you are finding the minimum element, and doing it using recursion.
Write a function countHowMany(x, a, size)
that counts how many times the number x appears in the
array a. Use a for
loop.
Write a function countTheXs(x,a,lower,size) that solves the same problem as 4d, but using recursion.
Write a function sevensToNines(a,lower,size) that returns a new vector where all the sevens have been changed to nines. Use recursion.
function M-file | test script M-file | technique | |
---|---|---|---|
Step4a | xAppearsInV.cc | testXAppearsInV.cc | iteration |
Step4b | doesXAppearInV.cc | testDoesXAppearInV.cc | recursion |
Step4c | myMin.cc | testMyMin.cc | recursion |
Step4d | countHowMany.cc | testCountHowMany.cc | iteration |
Step4e | countTheXs.cc | testCountTheXs.cc | recursion |
Step4f | sevensToNines.cc | testSevensToNines.cc | recursion |
lab10_step4.txt
.Now, we want to make a diary file called lab10_step4.txt
documenting the work from step 4 of this week's lab.
Put yourself inside the directory ~/cisc105/lab10
, and start a
script file called lab10.txt
.
Then, for each of the parts of step4 (4a, 4b, etc.)
Create a zip file that contains all of your files for this week.
It is ok if the files provided with the lab are included along with the ones you yourself created.
To create and test the zip file, follow the instructions from step11 of lab06 and/or lab07.
The script files may be included directly in the zip file this week.
Now you can submit your work on WebCT, and you are done!
step | what we're looking for | points |
---|---|---|
4a | xAppearsInV.cc testXAppearsInV.cc |
15 |
4b | doesXAppearInV.cc testDoesXAppearInV.cc | 15 |
4c | myMin.cc testMyMin.cc | 15 |
4d | countHowMany.cc testCountHowMany.cc | 15 |
4e | countTheXs.cc testCountTheXs.cc | 15 |
4f | sevensToNines.cc testSevensToNines.cc | 15 |
general programming style issues: | commenting, formatting, indenting, variable names | 25 |
overall following of directions | student should follow the directions given | 10 |
Total | 125 |