Exercise 5.2 pp. 122-123.
To run a C++ program:
myprogram.cpp
)cd
command to get to the folder where your C++ files areg++ myprogram.cpp
to compile. If there are error messages, correct the mistake and compile again (note: an old executable a.out
will still be there until it is overwritten by a new one. If your program failed to compile and you still try to run it, you would be running the old version).a.out
on the command line. If you get file not found
error, use ./a.out
instead.
Write a void C++ function order
that takes two pointers
to int
, checks if the value at the first address is larger
than at the second one, and if it is, switches the values at the two
addresses. I.e. if I have n = 7, m = 2
then after the call
order(&n,&m)
n should have the value 2, and m the
value 7.
Submit the file with your function and the testing code. Your program must compile and run on the dungeon machines. Important: Even if you are familiar with a different C++ style of declaring parameter passing by reference, please use the style that was used in the example in class.
Consider the following two C++ loops:
while(n >= m) {
n = n - 1;
}
while (*p >= *q) {
*p = *p - 1;
}
For each of the loop please answer: is it guaranteed to terminate? If yes, please explain why. If not, please write a program that initializes variables used in the loop in such a way that the program goes into an infinite loop (Ctrl-C stops a program).
The function traverse
defined below is analogous to the
Scheme traverse
function.
let rec traverse combine action seed = function
| [] -> seed
| x :: xs -> combine (action x) (traverse combine action seed (xs));;
do
is a reserved word in ML so the corresponding
parameter is called action
.
Below are two examples of using traverse
to define
functions on ML lists. Note that, unlike in Scheme, in ML * is an
operator, not a function, so you cannot pass it as an argument to
traverse
. Instead we define a simple function
mult
and pass it as a parameter. The same needs to be
done for +, -, and ::.
let comb x y = x :: y;;
let mult x = x * x;;
let mapsquare = traverse comb mult [];;
mapsquare [1; 5; 7; -2];;
let comb x y = x + y;;
let act x = 1;;
let count x = (traverse comb act 0) x;;
Note a different syntax used to define count
(x is used
in the definition). This syntax makes a function that can be applied
to a list of any type.
Your task is to define the following functions by passing
appropriate parameters to traverse
:
sumlist
to sum up elements of an integer listremove5
to remove all 5s from an integer listmin
to find a minimum of a list integers (you must
use traverse
). It should
return a very large number for an empty listreverse
to reverse any list (try it on a list of
strings and a list of integers). You may use append
function in the lab for this problem.You are given the following definition of a tree type and two sample trees:
(* tree type and two sample trees *)
type 'a tree = Empty | Node of 'a * 'a tree * 'a tree;;
let intTree = Node (5, Node (3, Empty, Empty),
Node (6, Node (7, Empty, Empty), Empty));;
let strTree = Node ("apples", Empty, Node ("bananas",
Node ("oranges", Empty, Node ("grapes", Empty, Empty)), Empty));;
Draw a picture of the two given trees.
Write a function traversetree
which takes three
parameters, combine, action,
and seed
,
and returns a function to perform an operation on a tree, the same way
as traverse
returns a function that works on lists.
Here are more details:
combine
takes 3 parameters: the result of
action
on a Node and the result of two recursive calls:
to the left and to the right subtrees.action
is applied to the value of a Nodeseed
is returned from an empty tree
Use the traversetree
function to define the following
functions:
addtree
to add all elements in a tree of integersconcattree
to concatenate all strings in a tree of
strings. The operation ^
performs string
concatenation.flattentree
to return a list of all elements in a
tree. For instance, for the first tree above it should
return [5; 3; 6; 7]
The order of elements in the list
does not matter. Important: the function should work
on trees of any type. See count
example above for the
correct syntax.find
that takes a tree
and an element and returns true if the element is in the tree and
false otherwise. Hint: action
should perform the check.