Physics 5—Introduction to Scientific Computing in C++
Final Exam Problems/Solutions—Spring
’04
1. The following questions
refer to program listing 1. This program
compiles and runs without any syntax errors.
Assume that the necessary #include files are prefacing the
code.
a.
What
is the scope of the variable ‘counter’ in the function main() ?
SOLN: Variable ‘counter’ has a scope of main().
b.
Five
an example of a variable that is passed by reference in this program.
SOLN: The array ‘a’ is passed by reference
(implicitly.)
c.
What
is the importance of the const
modifier in variable declarations here and what principle guides its usage?
SOLN: The const modifier is used to the principle
of least priviledge: if a function doesn’t need to change a variable, this is a
way of ensuring that it doesn’t.
Why don’t these variables need to be changed?
To see that, let’s see what functions use them and what for dost they?
d.
Describe
the parameter list for the function flop.
SOLN: The prototype function declares types
int * const, int * const
which are both constant pointers to integers.
That means that these can be modified through the pointer, but the
pointer always points to the same location in memory. Thus a “ptr = &y”-type command would create
an error. (p335)
e.
What
does flop do? How does it do this? Describe in detail.
SOLN: It swaps the value in the first passed memory
location with the value in the second memory location, but it leaves the
locations in the same place…
f.
Describe
the parameter list for the function trouble.
SOLN: The prototype function for trouble declares types
int w[], const int size
which is the address of the first element of an array of integers. This array may or may not be named w. The second parameter is the size of the array
which must be constant.
g.
What
does trouble do? How does it do this? Describe in detail.
SOLN: The function trouble iterates size times the command
flop( &w[
rand()%size ], &w[ rand()%size ]
This will swap the contents of two randomly chosen elements (not even
necessarily different) elements of the array.
Note that because we’re addressing that particular random element of the
array, we must explicitly precede the variable with the address reference.
h.
What
might a typical console screen look like after a user has interacted with this
program?
SOLN:
Oh, I don’t know, maybe, for instance….
Press any key to see the original
array:
3
3 1 1
1 1
Press key to see a troubled array:
3
3 1 1 1 1
Press key to see a troubled array:
3
1 1 3
1 1
Press key to see a troubled array:
3
1 1 3
1 1
Press key to see a troubled array:
1
3 1 1
3 1
Press key to see a troubled array:
1
1 1 3
1 3
Press key to see a troubled array:
1
3 3 1
1 1
Press key to see a troubled array:
1
3 3 1
1 1
Press key to see a troubled array:
i.
Suppose
the double indexed array
int permutations[ 15 ][ arraySize ]
is declared. How would you modify the
program so that it fills this array with the 15 permutations of 3,3,1,1,1,1
?
SOLN: The basic idea here is to keep troubling the
array and, if this creates a new permutation, adding it to the list—until we
have all 15 permutations.
One might create a function for seeing whether or not a given permutation is
new or not. The prototype might look
like
bool
equal( int [][6], int [], const int, const int);
where the first parameter is the array of permutations, the second parameter is
a candidate for a new permutation and the two constants are the dimensions of
the arrays. The definition of this
function below returns FALSE as soon as a difference is detected and true if no
difference is ever found:
bool equal( int
first[][6], int second[],
const
int size, const int p) {
for(int i = 0; i < size; ++i)
if(first[p][i]!=second[i])
return 0;
return
1;
}
Now the body of main() should be altered something like this:
int main()
{
const
int arraySize = 6;
int
perms = 0;
int
a[ arraySize ] = { 3, 3, 1, 1, 1, 1 };
int
permutations[ 15 ][ arraySize ] = {0};
bool
theSame = 0;
while
( perms < 15 ) {
trouble( a, arraySize );
theSame = 0;
for(int p = 0; p < perms;
++p)
//
see if a the same as on of the others
if(equal(permutations,a,arraySize,i))
theSame = 1;
// If this permutation is new, add
it to the list
if(theSame==0) {
for(int j = 0; j < arraySize; ++j)
permutations[perms][j] = a[j];
++perms;
}
}
// end while
cout << "\nHere are 15
permutations: \n";
for(int i = 0; i < 15; ++i) {
for(int j = 0; j <
arraySize; ++j)
cout << setw( 4 )
<< b[ i ][ j ];
cout << endl;
}
cin.get();
return
0;
} // end main
A typical run of the modified program will produce this output:
Here are 15 permutations:
3 3
1 1 1 1
3
1 1 3
1 1
1
3 1 1
3 1
1
1 1 3 1 3
1
3 3 1
1 1
1
3 1 1
1 3
3
1 1 1
3 1
1
1 3 3
1 1
1
1 3 1
3 1
1
1 1 3
3 1
1
3 1 3
1 1
1
1 1 1
3 3
3
1 3 1
1 1
3
1 1 1
1 3
1
1 3 1
1 3
Can
you suggest a more efficient way for generating the 15 permutations? How would you modify the code would you write
to implement this more efficient algorithm?
SOLN: The permutations we want to write are
3,3,1,1,1,1
3,1,3,1,1,1
3,1,1,3,1,1
3,1,1,1,3,1
3,1,1,1,1,3
1,3,3,1,1,1
1,3,1,3,1,1
1,3,1,1,3,1
1,3,1,1,1,3
1,1,3,3,1,1
1,1,3,1,3,1
1,1,3,1,1,3
1,1,1,3,3,1
1,1,1,3,1,3
1,1,1,1,3,3
Writing them this way suggests nested loops.
Indeed, it’s quite simple:
#include
<iostream.h>
#include <stdlib.h>
#include <iomanip.h>
int main()
{
const int arraySize = 6;
int b[15][ arraySize ];
// Initialize the array to all 1's
for(int i = 0; i < 15; ++i) {
for(int j = 0; j < arraySize; ++j)
b[ i ][ j ] = 1;
}
// p is the index of the permutation
int p = 0;
for(int i = 0; i < arraySize-1; ++i) {
for(int j = i+1; j < arraySize; ++j) {
b[p][i] = 3;
b[p][j] = 3;
++p; // Increment to the next permutation.
}
}
cout << "\nHere are the 15 permutations: \n";
for(int i = 0; i < 15; ++i) {
for(int j = 0; j < arraySize; ++j)
cout << setw( 4 ) << b[ i ][ j ];
cout << endl;
}
cin.get();
return 0;
} // end main
The
above program produces the following output:
Here are the 15 permutations:
3
3 1 1
1 1
3
1 3 1
1 1
3
1 1 3
1 1
3
1 1 1
3 1
3
1 1 1
1 3
1
3 3 1
1 1
1
3 1 3
1 1
1
3 1 1
3 1
1
3 1 1
1 3
1
1 3 3
1 1
1
1 3 1
3 1
1
1 3 1
1 3
1
1 1 3
3 1
1
1 1 3
1 3
1
1 1 1
3 3
Program
Listing 1
void trouble( int [], const int ); // 10
void flop( int * const, int * const ); // 20
int main() // 30
{
const int arraySize = 6; // 40
int counter; // 50
int a[ arraySize ] = { 3, 3, 1, 1, 1, 1 }; // 60
cout << "Press any key to see the original array:\n"; // 70
while ( cin.get() ) { // 80
for ( counter = 0; counter < arraySize; counter++ ) // 90
cout << setw( 4 ) << a[ counter ]; // 100
trouble( a, arraySize ); // 110
cout << "\nPress key to see a troubled array:\n"; // 120
}
return 0;
} // end main
void trouble( int w[], const int size ) // 130
{
for ( int pass = 1; pass < size; pass++ ) // 140
flop( &w[ rand()%size ], &w[ rand()%size ] ); // 150
} // end function trouble
void flop( int * const n1Ptr, int * const n2Ptr ) // 160
{
int temp = *n1Ptr; // 170
*n1Ptr = *n2Ptr; // 180
*n2Ptr = temp; // 190
} // end function flop
2. The following questions
refer to program listing 2. This program
compiles and runs without any syntax errors.
Assume that the necessary #include files are prefacing the
code.
a.
Where
is a constructor for the Triangle class declared? Where is it defined?
SOLN: Line number 30.
b.
What
methods does the class provide to access the private data?
SOLN: Both defineTriangle and printCoords are methods used to access
the private data.
c.
Write
code to declare and define new Triangle methods (class functions)
called length12, length13 and length23 that will compute the length of the
sides connecting points 1&2, 1&3 and 2&3, respectively.
SOLN: First, one way to save overhead on this is to
define an inline version (very short code, so that’s appropriate) which appears in the prototype area:
inline
double squr(const double A) {
double
x=A, xtemp = A/2;
while(xtemp
!= x) {
x = xtemp;
xtemp = (A/x + x)/2;
}
return
x;
}
Now, to create
functions for computing the lengths of the various sides, we declare in the
public section of the Triangle class, the prototypes:
double length12();
double
length13();
double
length23();
Lengths are
computed using the distance formula (Pythagorus’ theorem.) Thus the following definitions can be
appended to extend the definition of the Triangle class:
double Triangle::length12() {
return
squr((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));
}
double Triangle::length13() {
return
squr((x1-x3)*(x1-x3) + (y1-y3)*(y1-y3));
}
double Triangle::length23() {
return
squr((x3-x2)*(x3-x2) + (y3-y2)*(y3-y2));
}
d.
Write
a function prototype and definition for a method that computes the perimeter of
a Triangle.
SOLN: Start with the prototype in the public
section of the class definition:
double perimeter();
Then extend the
definition of the triangle class using something like:
double
Triangle::perimeter() {
return length12()+length13()+length23();
}
e.
Use Heron’s formula to write a function prototype and definition for a
method that computes the area of a Triangle. where s=(a+b+c)/2 is half the perimeter. Avoid using the math.h header.
SOLN: We need a prototype in the public section,
say
double area();
Then we can use Heron’s formula to define the function:
double
Triangle::area() {
double
s = perimeter()/2;
return
squr(s*(s-length12())
*(s-length13())
*(s-length23()));
}
f.
The coordinates of the point where the perpendicular bisectors of any
two sides is called the orthocenter of the Triangle. Write code for the prototype and definition
of a method that returns the orthocenter of a Triangle.
SOLN: In the public section of the Triangle class declare the prototype
void orthoCent();
and maybe add the coordinate pair to the private data members:
private:
double x1,y1,x2,y2,x3,y3;
double orthoC[2];
and then define it something like so:
void Triangle::orthoCent() {
double m1, m2, p1x, p1y,
p2x, p2y;
// Compute slopes perpendicular to
two of the sides.
m1 = (x3 - x1)/(y1 - y3);
m2 = (x2 - x1)/(y1 - y2);
// Compute the corresponding
midpoints.
p1x = (x1 + x3)/2;
p1y = (y1 + y3)/2;
p2x = (x1 + x2)/2;
p2y = (y1 + y2)/2;
// A little algebra shows these
are the coordinates
// of the point of intersection of
the perp. Bisecters.
orthoC[0] = (p2y - p1y + m1*p1x -
m2*p2x)/(m1 - m2);
orthoC[1] = p1y +
m1*(orthoC[0] - p1x);
}
g.
Write code for the function prototype and definition that will return
true if the triangle is a right triangle and false otherwise.
SOLN: There are at least two different approaches
you might consider here. One is to use
Pythagorus and the other is to use slope.
In either case, the prototype is defined in the public section like so:
bool right();
In the
Pythagorean scheme, you’d write something like:
bool
Triangle::right()
{
if((length12()*length12()+length13()*length13())
==(length12()*length12())
||(length12()*length12()+length13()*length13())
==(length12()*length12())
||(length12()*length12()+length13()*length13())
==(length12()*length12()))
return true;
}
Note that a potential improvement of this is to find the side of maximum length
first, and then test the case where that’s the hypotenuse.
In the slope
scheme, the abbreviated technique involves using the fact that if one slope is
perpendicular to another then :
bool
Triangle::right()
{
if((y3-y1)*(y2-y1)+(x3-x1)*(x2-x1)==0
||(y3-y2)*(y1-y2)+(x3-x2)*(x1-x2)==0
||(y2-y3)*(y1-y3)+(x2-x3)*(x1-x3)==0)
return true;
}
h.
Write code to overload the == operator for Triangle to return true if two Triangle are similar (have proportional sides.)
SOLN: The comparison operator overload needs at
least one prototype. It is implicit that
the left operand of is a Triangle, but the right operand is
also a Triangle, so we pass the operand its
address like so:
bool operator==(const Triangle &) const;
Defining this thoroughly is a bit tedious (at least, they way I’ve done it)
since you don’t know before hand which sides correspond and thus must consider many
cases. Here’s what I came up with:
bool
Triangle::operator==(const Triangle & t2) const {
double ratio;
ratio = length12()/t2.length12();
if(((length13()/t2.length13()==ratio)
&&(length23()/t2.length23()==ratio))
||((length13()/t2.length23()==ratio)
&&(length23()/t2.length13()==ratio)))
return true;
ratio = length12()/t2.length13();
if(((length13()/t2.length23()==ratio)
&&(length23()/t2.length12()==ratio))
||((length13()/t2.length12()==ratio)
&&(length23()/t2.length23()==ratio)))
return true;
ratio = length12()/t2.length23();
if(((length13()/t2.length12()==ratio)
&&(length23()/t2.length13()==ratio))
||((length13()/t2.length13()==ratio)
&&(length23()/t2.length12()==ratio)))
return true;
return false;
}
i.
Write code to overload the + operator so that two Triangles are added by adding corresponding
coordinates of the three vertices.
SOLN: Again, it is implicit that the left operand
of is a Triangle and, in this case, the
right operand is also a Triangle, so we pass the operand its
address like so:
Triangle
Triangle::operator+(Triangle & t2) {
t2.x1 += x1;
t2.y1 += y1;
t2.x2 += x2;
t2.y2 += y2;
t2.x3 += x3;
t2.y3 += y3;
return t2;
}
j.
Modify
the main() program to test all your
new code.
main()
{
Triangle ABC;
ABC.printCoords();
ABC.defineTriangle(1.2,2.3,3.4,4.5,5.6,6.7);
ABC.printCoords();
cout << "\nAB has
length "<<ABC.length12() << endl;
cout << "\nAC has
length "<<ABC.length13() << endl;
cout << "\nBC has
length "<<ABC.length23() << endl;
cout << "\nThe
perimeter is "<<ABC.perimeter();
cout << "\nThe area
is "<<ABC.area();
if(ABC.right()) cout << "\nThe
triangle is a right triangel";
else cout << "\nThe
triangle is not a right triangle.";
Triangle DEF;
DEF.defineTriangle(0,0,0,1,1,1);
DEF.printCoords();
Triangle GHI;
GHI.defineTriangle(0,0,0,2,2,2);
GHI.printCoords();
if(DEF==GHI) cout << "\nDEF is
similar to GHI" << endl;
if(ABC==DEF) cout << "\nDEF is
similar to ABC" << endl;
else cout << "\nDEF is not
similar to ABC\n" << endl;
DEF = DEF+GHI;
DEF.printCoords();
cin.get();
return 0;
}
The output for this function is below:
Point 1: (0, 0)
Point 2: (0, 0)
Point 3: (0, 0)
orthocenter: (8.52482e+268,1.22015e-311)
Point 1: (1.2, 2.3)
Point 2: (3.4, 4.5)
Point 3: (5.6, 6.7)
orthocenter: (-9.90792e+15,9.90792e+15)
AB has length 3.11127
AC has length 6.22254
BC has length 3.11127
The perimeter is 12.4451
The area is 0
The triangle is not a right triangle.
Point 1: (0, 0)
Point 2: (0, 1)
Point 3: (1, 1)
orthocenter: (0.5,0.5)
Point 1: (0, 0)
Point 2: (0, 2)
Point 3: (2, 2)
orthocenter: (1,1)
DEF is similar to GHI
DEF is not similar to ABC
Point 1: (0, 0)
Point 2: (0, 3)
Point 3: (3, 3)
orthocenter: (1,1)—this last bit is wrong, no?
Why?
Program Listing 2
class Triangle { // 10
public: // 20
Triangle(); // 30
void defineTriangle(double, double, // 40
double, double,
double, double);
void printCoords(); // 50
private: // 60
double x1,y1,x2,y2,x3,y3; // 70
}; // end class Triangle
Triangle::Triangle() { // 80
x1 = y1 = x2 = y2 = x3 = y3 = 0.; // 90
}
int main() // 100
{
Triangle ABC; // 110
ABC.printCoords(); // 120
ABC.defineTriangle(1.2,2.3,3.4,4.5,5.6,6.7); // 130
ABC.printCoords(); // 140
cin.get();
return 0;
}
void Triangle::printCoords() { // 150
cout << "\nPoint 1: (" << x1 << ", " << y1 << ")" // 160
<< "\nPoint 2: (" << x2 << ", " << y2 << ")"
<< "\nPoint 3: (" << x3 << ", " << y3 << ")";
}
void Triangle::defineTriangle(double a_x, double a_y, // 170
double b_x, double b_y,
double c_x, double c_y) {
x1 = a_x; y1 = a_y; // 180
x2 = b_x; y2 = b_y; // 190
x3 = c_x; y3 = c_y; // 200
}