function1.C,
function1.txt
main
function.
function2.C,
function2.txt
chorus,
in addition to the
main
function.
()
means that we are not attempting
to carry any information from the
main
function
down to the
chorus
function.
void
means that we are not attempting
to carry any information back from the
chorus
function
back up to the
main
function.
The product of all the integers from 1 to n is called n factorial, and is written n! with an exclamation point. Here are three examples:
3! = 1 × 2 × 3 = 6
4! = 1 × 2 × 3 × 4 = 24
5! = 1 × 2 × 3 × 4 × 5 = 120
One use of a factorial is to tell us how many orders n objects can be arranged in. n objects can be arranged in n! different orders. For example, the three objects a, b, c can be arranged in 6 different orders, and the four objects a, b, c, d can be arranged in 24 different orders:
automatic.C,
automatic.txt
f
within the {curly
braces}
of a function body.
In the above program,
we created the variable f within the
{curly
braces}
of the factorial
function.
When we create a variable within any pair of
{curly
braces},
we can mention the name of the variable only
within those curly braces.
We therefore say that the variable has
local scope.
In the above program, for example, the variable
f
could not be mentioned in the
main
function.
In the above program,
we created the variable f within the
{curly
braces}
of the factorial
function.
When we create a variable within any pair of
{curly
braces}
as the computer executes the program,
the variable stays alive only until the computer reaches the closing curly brace
};
at that point the variable dies.
(Here’s what “death” means:
when a variable dies, it stops holding a value.)
We therefore say that the variable is automatically allocated.
In the above program, for example, the variable f
dies as we return form the factorial
function to the main
function.
If the computer executes the code within the
{curly
braces}
a second time,
then the variables created within the braces are reincarnated.
In the following excerpt, for example,
a variable named j
is born holding the value 2.
After it dies, another variable named j
is born holding the value 4.
The two
j’s
are two different variables,
living at different times and holding different values.
They just happen to have the same name and data type.
for (int i {1}; i <= 2; ++i) { //The loop iterates 2 times.
int j {2 * i};
cout << j << "\n";
}
argument.C,
argument.txt
graphpaper1.C:,
graphpaper1.txt
main
function to the
graphPaper
function.
graphpaper2.C,
graphpaper2.txt
main
function calls the
graphPaper
function, which calls the
line
function.
retval.C,
retval.txt
main
function of
retval.C,
call the
factorial
function 13 times in a loop
for (int i {0}; i <= 12; ++i) {
cout << setw(2) << i << " " << setw(9) << factorial(i) << "\n";
}
to output the following table of factorials.
Remember to
#include <iomanip>
for the i/o manipulator
setw.
0 1 1 1 2 2 3 6 4 24 5 120 6 720 7 5040 8 40320 9 362880 10 3628800 11 39916800 12 479001600To go all the way to 20!, we would have change the data type of the return value of the function to
long int
and set the width to 20.
The biggest number we can store in a plain old
int
on our machine is only
numeric_limits<int>::max() = 2,147,483,647
long int
on our machine is
numeric_limits<long int>::max() = 9,223,372,036,854,775,807
0 1 1 1 2 2 3 6 4 24 5 120 6 720 7 5040 8 40320 9 362880 10 3628800 11 39916800 12 479001600 13 6227020800 14 87178291200 15 1307674368000 16 20922789888000 17 355687428096000 18 6402373705728000 19 121645100408832000 20 2432902008176640000Back in 1968, Donald Knuth wrote, “It is helpful to keep the value
pi.C,
pi.txt
pi
that returns an approximation of the value of π.
The argument
n
of the function specifies
how much work the function should do;
more work gives a better approximation.
We saw this algorithm in the old
pi.C;
now it is neatly packaged as a function.
The
main
function concentrates on formatting the nice output table;
the
pi
function concentrates on the numerical computation.
queue.C
vp
and
qp
that hold the subscripts.
Our queue is stored in an array of 10
strings,
so the subscripts must remain in the range 0 to 9 inclusive.
When we increment a subscript that is already 9,
we must wrap it around to 0
so that it does not go beyond the end of the array.
And when we decrement a subscript that is already 0,
we must wrap it around to 9
so that it does not go beyond the beginning of the array.
The code that keeps the subscripts within legal bounds has been packaged
as a function named
f.
It receives a subscript and returns the subscript confined to the
range 0 to 9 inclusive.
To make a variable acessible to (i.e., mentionable by) more than
one function,
declare the variable at the top of the file.
See the
n
in this program.
true
if a year is leap.
strings:
last hired, first fired.
stack1.C:
a simplified version of the
stack.C we saw earlier,
with all the code written in the main
function.
stack2.C:
separate functions to
push
and
pop
the stack.
The contents of the stack are held in variables of
global scope and
static allocation.
These variables live as long as the program is running.
12hour.C,
12hour.txt
main
function.
12hour2.C,
12hour2.txt
gethour.
range.C
eof,
clear,
and
ignore
are function that “belong to” the “object”
cin.
chars
have been input from
cin,
or output to
cout
(or to
cerr),
should be of data type
streamsize.
static1.C,
static1.txt
f
has amnesia every time we return from it.
static2.C,
static2.txt
static
variable to avoid amnesia.
betterpgm.C
betterpgm.C
find_if.
newweight.C
gravity * 9.8
is in the denominator.
newweight.C
find_if.
convert
now has a return value.
WIPMorseTranslator.C
morse.C,
morse.txt
transform
and
find_if.
r
is a
reference to
(i.e., another name for)
the variable
i.
reference.C,
reference.txt
r,
this program
can read and write (i.e., use and change) the value of the variable
i.
constreference.C,
constreference.txt
const
reference
r,
this program
can read but not write (i.e., use but not change) the value of the variable
i.
r
gives us “read-only” access to the value of
i.
passby.C,
passby.txt
a,
and then passes this copy to the function
f.
i.
i
(which it does with an increment),
but this has no effect on the value of
a.
The most common use of a reference in C++
is to pass a variable to a function
without making a copy of the value of the variable.
The
r
received by the function
is just a reference to (i.e., an alternative name for)
b,
not a copy of the value of
b.
No copy of the value of
b
is manufactured.
Using this reference,
the function can access the value of
b
and can also change the value of
b.
The official jargon is:
the variable
a
is
passed by value,
and the variable
b
is
passed by reference.
speed.C,
speed.txt
b
in
passby.C
and
speed.C:
The other reason
is to avoid the expense of manufacturing a copy of the value of the variable.
For example, if the variable is big
(like the
bigstruct
in
speed.C),
it would take too much time
to manufacture a copy of the value of the variable.
We pass
bigstruct
by refernce to avoid manufacturing a copy of it,
and the reference is
const
to ensure that the function can not accidentally use the reference
to damage the value of
bigstruct.
If the variable is comparatively small and simple
(like the
int
variable
a
in
passby.C),
manufacturing a copy of its value is so fast
that we don’t worry about it.
threeways.C,
threeways.txt
string
or a
struct
is expensive to copy,
so it should be passsed by reference.
referencedate.C:
static
variables inside a function.
Exercise.
In
referencedate.C,
make the last argument of the function
travel
optional.
Change the function declaration at the top of the program to
void travel(int& month, int& day, int& year, int distance = 1);Then change the statement that calls this function to
travel(month, day, year); //distance defaults to 1Only trailing arguments can be made optional.
Exercise.
Instead of going a specified number of days into the future from the current
date,
change
referencedate.C
so that it goes a specified number of seconds into the future
from the current time.
Since every minute has the same number of seconds,
and every hour has the same number of minutes,
the
travel
function in
referencetime.C
can do its job without loops and
if
statements.
For example, let’s say it’s 6:00 a.m.:
| hour | minute | second |
|---|---|---|
| 6 | 0 | 0 |
second += distance;
adds 600 to
seconds:
| hour | minute | second |
|---|---|---|
| 6 | 0 | 600 |
seconds
is obviously much too large.
second %= 60;
knocks it down to therange 0 to 59 inclusive.
second / 60
computes how many minutes are in these 600 seconds.
minute += (second / 60);
adds this number to
minutes.
| hour | minute | second |
|---|---|---|
| 6 | 10 | 0 |
The word
“algorithm”
has more than one meaning in Computer Science.
In this course, an
algorithm
is a function in the C++ STL that takes as its arguments the
beginning
and the
end
of an array.
The algorithm probably contains a
for
loop.
In many cases, you can call the algorithm instead of writing your own
for
loop.
accumulate1.C,
accumulate1.txt
+=
assignment statement inside of a
for
loop.
accumulate2.C,
accumulate2.txt
accumulate.
#include <numeric>
this time.
accumulate3.C,
accumulate3.txt
strings
in the array
by calling the algorithm
accumulate.
string {}
creates an empty object of class
string.
It plays the same rôle
as the third argument
0
of the call to
accumulate
in
accumulate2.C.
count1.C,
count1.txt
++
inside of an
if
inside of a
for
loop.
count2.C,
count2.txt
count.
count
to return a value of data type
size_t,
but unfortunately it returns a value of type
long int.
size_t
is just another name for the data type
long unsigned int
on our machine.)
find1.C,
find1.txt
if
statement inside of a
for
loop.
find2.C,
find2.txt
find.
distance
returs the distance from the start of the array
to the position marked by the iterator.
min_element1.C,
min_element1.txt
if
statement inside of a
for
loop.
min_element2.C,
min_element2.txt
min_element.
max_element
algorithm.)
*
gives us the value (in this case,
28)
at the position marked by the iterator.
sort1.C,
sort1.txt
for
loops.
sort2.C,
sort2.txt
sort.
<
operator.
sortstrings.C,
sortstrings.txt
strings
into alphabetical order by calling the algorithm
sort.
<
operator compare a pair of
strings.
random_shuffle.C,
random_shuffle.txt
random_shuffle.
sort2.C,
sort2.txt
sort.
<
operator.
sortdecreasing.C,
sortdecreasing.txt
sort.
greater_int
function.
greater_int
returns
false,
the algorithm swaps the two values.
sortlambda.C,
sortlambda.txt
sort.
greater_int
to the algorithm,
we pass a little function with no name to the algorithm.
greater_int
in
sort3.C.
true
if its first argument is greater than the second.
[](int a, int b) {return a > b;}
sort5.C,
sort5.txt
sort
algorithm,
we must always pass a comparison function to the algorithm
(until next semester).
greater_int
function in
sortdecreasing.C),
or it can be a lambda function (like the one in
sortlambda.C).
const
references to make sure that the comparison function can’t
damage the two structures.
[](const month& a, const month& b) {return a.name < b.name;}
to
[](const month& a, const month& b) {return a.name > b.name;}
[](const month& a, const month& b) {return a.length < b.length;}
[](const month& a, const month& b) {return a.length > b.length;}
[](const month& a, const month& b) {return a.name.size() < b.name.size();}
sort6.C,
sort6.txt
true
if its first argument is an earlier
date
than its second argument.
sortpoint.C,
sortpoint.txt.
true
if its first argument is closer to the origin than its second argument.
calories.C,
calories2.txt
+=
inside a
for
loop.
calories.C,
calories.txt
[](int total, const food& f) {return total + f.calories;}
recursion1.C,
recursion1.txt
ints
from 1 to 10 inclusive
with a
for
loop.
recursion2.C,
recursion2.txt
ints
from 1 to 10 inclusive
without any loop at all.
=
or
++
at all.
recursion3.C,
recursion3.txt
main
function.
if
statement that
prevents
the function from calling itself
if the job is already completely finished.
factorial1.C,
factorial1.txt
ints
from 1 to 10 inclusive
with a for
loop.
factorial2.C,
factorial2.txt
ints
from 1 to 10 inclusive
without any loop at all.
maze.C,
maze.txt,
maze.html
storm.cis.fordham.edu,
change the statement
cout << a[row][col];in
maze.C
to
if (a[row][col] == '.') {
cout << "\033[48;5;9m.\033[0m"; //dot with red background
} else {
cout << a[row][col];
}
These crazy numeric codes are the
xterm-256color
control codes.
\033
is the ASCII
ESCape
character.
48
means background,
38
would mean foreground.
5
means 8-bit color,
2
would mean 24-bit color.
9
means red,
10
would mean green,
etc.
sed,
and have
sed
surround every period
(.)
with the control codes:
jsmith@storm:~$ compile maze jsmith@storm:~$ maze | sed $'s/\./\033[48;5;9m.\033[0m/g'
Exercise.
Have
maze.C
display a moving red snake that gets longer and longer as it
feels its way through the maze,
and that retracts when the algorithm backtracks from a dead end.
void display()
{
for (int row {0}; row < nrows; ++row) {
for (int col {0}; col < ncols; ++col) {
cout << a[row][col];
}
cout << "\n"; //at the end of each row
}
}
display
function.
display
function.
cout << "\033[H\033[J" << flush; //Home the cursor, clear the screen.
display
function.
#include
the header files
chrono
and
thread
at the top of the program.)
sleep_for
in
beer.C.
//Sleep for 1/5 of a second. this_thread::sleep_for(chrono::milliseconds(200));
display
function,
make the change we saw in the previous exercise.
Change the statement
cout << a[row][col];to
if (a[row][col] == '.') {
cout << "\033[48;5;9m.\033[0m"; //dot with red background
} else {
cout << a[row][col];
}
display
function immediately after every statement in the
findpath
function that changes any
character in the array.
There are two such statements:
a[row][col] = '.'; //step on it. display();
a[row][col] = ' '; display();
storm.cis.fordham.edu
and run
~mmeretzky/bin/snakefor inspiration. Watch the snake extend and retract. Have fun and good luck. You could change the number of milliseconds, or add more paths and dead ends to the maze.