Solutions to Fall 2000 Assignments 1998 A Exam: Question 1
bool Code::IsValid() const {
// postcondition: returns true if MINLEN <= Length() < MAXLEN - 2
// and for every k, 0 <= k < Length(),
// myChars[k] is a digit '0'--'9' or a char 'A' -- 'Z'
if (Length() < MINLEN || MAXLEN - 2 < Length()) {
return false;
}
int k;
for(k=0; k < Length(); k++) {
if (! isupper(myChars[k]) && ! isdigit(myChars[k])) return false;
}
return true;
}
void Code::AppendCheckSum() {
// postcondition: if IsValid() then myLength is updated and
// myChars contains the original characters followed
// by a dash and the appropriate checksum; otherwise
// myLength and myChars are unchanged
if (IsValid()) {
int k, sum(0), len = Length();
for(k=0; k < len; k++) {
if (isdigit(myChars[k])) {
sum += digitToInt(myChars[k]);
}
}
myChars[myLength] = '-';
myChars[myLength+1] = intToDigit(sum % 10);
myLength += 2;
}
}
In period 5, Pavel pointed out that this solution shouldn't work if there were three
or more duplicates:
template<class T>
void remDups(apvector<T> &v) {
// precond: v is in ascending order
//postcond: all duplicate elements in v are removed
for (int current = 0; current < v.length() - 1; current++) {
if ( v[current] == v[current+1] ) { // if should be while
for (int p = current; p < v.length() - 1; p++) {
v[p] = v[p+1];
}
v.resize(v.length()-1);
if ( current >= v.length() - 1 ) return;
}
}
}
Pavel reasoned that after shifting every element from v[current+1] to v[v.length()-1] one position forward (toward v[0]), current would be incremented before v[current] could be compared against the third duplicate element. The real mystery was why Benny and Elan's code (shown above) eliminated two of the triplicate values of 5.00 when the code was executed in the driver program. In period 6, Norman (Sherlock) Yung solved the mystery. Norman noticed that the main() driver accidentally called remDups() twice. When one of the calls is deleted, remDups() removes only one of the three duplicates, as Pavel had predicted! Note: we need only change if to while to overcome the problem of prematurely moving past the third duplicate. A solution that starts from position v.length()-1 is a little trickier. Try it!
Replacing the parallel vectors of long and Position in getLargest() with
a single vector of longPos.
class longPos {
public:
longPos(void);
longPos(long, const Position &);
long x;
Position pos;
};
longPos::longPos(void) :
x(0), pos(Position())
{}
longPos::longPos(long x2, const Position &pos2):
x(x2), pos(pos2)
{}
Neighborhood getLargest(const apmatrix<long> &m) {
// precond: m has at least 4 elements, all elements > 0
//postcond: returns neighborhood object which contains
// positions of 4 largest elements in m
Neighborhood temp;
const int COLS = m.numcols(), ROWS = m.numrows(), vSIZE = ROWS*COLS;
//*** apvector<long> v(vSIZE);
//*** apvector<Position> v2(vSIZE);
apvector<longPos> lpVec(vSIZE);
// 1. Write m's values and corresponding indices to parallel vectors
//======================================
for (int r = 0; r < ROWS; r++)
for (int c = 0; c < COLS; c++) {
//*** v[r*COLS + c] = m[r][c];
//*** v2[r*COLS + c] = Position(r, c);
lpVec[r*COLS + c] = longPos(m[r][c], Position(r, c));
}
// 2. Selection sort: while v is sorted, v2 is changed in parallel
//=======================================
for (int current = 0; current < vSIZE - 1; current++) {
int minPos = current;
for (int pos = current+1; pos < vSIZE; pos++) {
//*** if ( v[pos] < v[minPos] )
if (lpVec[pos].x < lpVec[minPos].x )
minPos = pos;
}//**for pos
//*** long hold = v[minPos]; Position hold2 = v2[minPos];
longPos hold(lpVec[minPos]);
//*** v[minPos] = v[current]; v2[minPos] = v2[current];
lpVec[minPos] = lpVec[current];
//*** v[current] = hold; v2[current] = hold2;
lpVec[current] = hold;
}//**for current
// 3. The positions of the 4 largest elements in m
// are loaded in Neighborhood object temp
for (int k = vSIZE-1; k >= vSIZE - 4; k--)
//*** temp.Add(v2[k]);
temp.Add(lpVec[k].pos);
return temp;
}
void magic(apmatrix<int> &m, int n) {
//precond: n is # of elements in a side; n is odd
//post: m is resized to n by n and it's a Magic Square by Coxeter!!
const int nSQRD = n*n;
m = apmatrix<int>(n, n, 0);
int x1(n/2), y1(0);
m[y1][x1] = 1;
for (int n2 = 2; n2 <= nSQRD; n2++) {
int x2(x1), y2(y1); // Save coords
x1 = (x1 - 1 + n) % n; // Move up and left
y1 = (y1 - 1 + n) % n;
if ( m[y1][x1] != 0 ) { // Drop down safely
x1 = x2;
y1 = (y2 + 1) % n; // If y1 is n-1, it will be 0
}//**if
m[y1][x1] = n2;
}//==for n2
}
Neil Xu's superb and surprising solution:
void magic(apmatrix<int> &m, const int n) {
m = apmatrix<int>(n, n, 0);
int n2(n*n), r(n2), c(n2 + n/2);
for (int k = 1; k <= n2; k++){
m[r % n][c % n] = k;
if(m[(r - 1) % n][(c - 1) % n] == 0){
c--;
r--;
}
else{
r++;
}
}
void Rational::reduce(void) {
if ( p == 0 || q == 0 ) {
p = 0; q = 1;
}
else if ( q < 0 ) { // q never negative
q = -q;
p = -p;
}
int n(p), d(q);
if ( n < 0 ) n = -n; // n and d never negative
for (;;) {
int r = n % d;
if ( r == 0 ) break; // d is GCD
n = d;
d = r;
}
p /= d;
q /= d;
}
ostream &operator << (ostream &os, const Rational &r) {
return (os << r.getP() << "/" << r.getQ());
}
Rational operator + (const Rational &right, const Rational &left) {
// **** a/b + c/d = (ad + bc)/(bd)
int num = left.getP()* right.getQ() + left.getQ()* right.getP(); //** ad + bc
int den = left.getQ() * right.getQ(); //** bd
return Rational(num, den);
}
void main(void) {
RandGen r(17);
unsigned int nCircle(0), nSquare(0);
cout << setprecision(6) << setiosflags(ios::fixed | ios::showpoint);
for (;;) {
double x = r.RandReal();
double y = r.RandReal();
++nSquare;
if ( sqrt(x*x + y*y) < 1 )
++nCircle;
if ( nSquare % 1000000 == 0 ) {
cout << "nSquare: " << setw(10) << nSquare
<< "\tnCircle: " << setw(10) << nCircle
<< "\npi approximation: " << (4.0 * nCircle)/nSquare << endl;
}
}
cout << endl << endl;
}//*** main
int sumBorder(const apmatrix<int> &M) {
//precondition: M.numrows() > 1, M.numcols() > 1
//postcondition: returns the sum of the values in the border of the matrix
//----------------------------------------------------------------------
const int ROWS = M.numrows(), COLS = M.numcols();
int sum(0);
for (int r = 0; r < ROWS; r++) //** total the left and right borders
sum += M[r][0] + M[r][COLS-1];
for (int c = 1; c < COLS - 1; c++) //** Skip the 4 corners while
sum += M[0][c] + M[ROWS-1][c]; // totalling the top and bottom borders
return sum;
}//*** sumBorder
void deleteBorder(apmatrix<int> &M) {
//precondition: M.numrows() > 1, M.numcols() > 1
//postcondition: removes the border of M by moving rows up and columns left
// and by resizing M to have 2 fewer rows and 2 fewer columns
// EXAMPLE: M.resize(M.numrows()-2, M.numcols()-2);
//------------------------------------------------------------------------
const int ROWS = M.numrows(), COLS = M.numcols();
for (int r = 1; r < ROWS - 1; r++) {
for (int c = 1; c < COLS - 1; c++) {
M[r-1][c-1] = M[r][c];
}
}
M.resize(ROWS-2, COLS-2);
}//*** deleteBorder
long sumMat(const apmatrix<long> &mat) {
// postcond: if mat has elements, their sum is returned
// otherwise, 0 is returned
const int ROWS = mat.numrows(), COLS = mat.numcols();
long sum(0);
for (int r = 0; r < ROWS; r++) {
for (int c = 0; c < COLS; c++) {
sum += mat[r][c];
}// for c
}//** for r
return sum;
}
void maxRow(const apmatrix<long> &m, long &rowSum, int &rowNum) {
// precond: m isn't an empty apmatrix
// postcond: the row whose sum is largest has its total assigned
// to rowSum and its index position stored to rowNum
const int ROWS = m.numrows(), COLS = m.numcols();
long currentSum;
rowSum = LONG_MIN; //*** include "limits.h" for LONG_MIN
for (int r = 0; r < ROWS; r++) {
currentSum = 0;
for (int c = 0; c < COLS; c++) {
currentSum += m[r][c];
}//** for c
if ( currentSum > rowSum ) {
rowSum = currentSum;
rowNum = r;
}
}//** for r
}
void swapCols(apmatrix<long> &m, int c1, int c2) {
// precond: m isn't an empty matrix, c1 and c2 < m.numcols()
// postcond: the columns with index positions c1 and c2 are swapped
const int ROWS = m.numrows();
for (int r = 0; r < ROWS; r++) {
long temp = m[r][c1];
m[r][c1] = m[r][c2];
m[r][c2] = temp;
}
}
void swapRows(apmatrix<long> &m, int r1, int r2) {
// precond: m isn't an empty matrix, r1 and r2 < m.numrows()
// postcond: the rows with index positions c1 and c2 are swapped
apvector<long> temp(m[r1]); // This only works with rows!!
m[r1] = m[r2];
m[r2] = temp;
}
bool Customer::isGreater(const Customer &right) const {
return ( name > right.name );
}
void addCustomer(apvector<Customer> &V) {
// HINT: don't use bSearch()--use a linear search here!!
//postcondition: specified Customer object is added by shifting
// all successors (if any) back and V is resized accordingly
// EXAMPLE adding L: A D G K M Q X ----> A D G K L M Q X
// 0 1 2 3 4 5 6 0 1 2 3 4 5 6 7
const int SIZE(V.length());
apstring name;
cout << "Enter name of customer to add: ";
getline(cin, name);
// 1. Implement sequential search to find insertion position
int insertPos; // Use meaningful name for insertion position
for (insertPos = 0; insertPos < SIZE; ++insertPos) {
if ( name < V[insertPos].getName() )// This is where to insert new customer
break;
}
V.resize(SIZE+1);
// 2. Shift V[index-1] back to V[index] for index = V.length()-1 to insertPos + 1
for (int index = SIZE; index > insertPos; --index) {
V[index] = V[index-1];
}
V[insertPos] = Customer(name, 0.0); //You can use explicit constructor here!!
}
Customer::Customer(const Customer &customer):
name(customer.name), balance(customer.balance){
}
void list1000(const apvector<Customer> &V) {
const int SIZE = V.length();
if ( SIZE == 0 )
cout << "The bank has no customers. Thus no customer has balance >= 0\n";
else {
int count(0);
for (int index = 0; index < SIZE; ++index) {
if ( V[index].getBalance() >= 1000 ) {
cout << setiosflags(ios::left) << setw(12)
<< V[index].getName() << "" << setiosflags(ios::fixed | ios::right)
<< setprecision(2) << setw(7) << V[index].getBalance() << endl;
count++;
}//*** if
}//*** for index
cout << "Number of Customers on list: " << count << endl;
}
}
int bSearch(const apvector<Customer> &v, const apstring &key) {
// precondition: v's elements are in ascending order
//postcondition: when Customer's name = key, its index is returned
// otherwise -1 is returned
int lo(0), hi(v.length()-1);
while ( lo <= hi ) {
int mid = (lo + hi)/2;
if ( key < v[mid].getName() )
hi = mid - 1;
else if ( key > v[mid].getName() )
lo = mid + 1;
else
return mid;
}
return -1;
}
void withdrawDriver(apvector<Customer> &V) {
// precondition: bSearch() function works!!!
//postcondition: this is the counterpart to depositDriver(). Therefore
// use depositDriver() as a model to complete this function
apstring name;
cout << "Enter customer name: ";
getline(cin, name);
int index = bSearch(V, name);
if ( index < 0 ) {
cout << name << " not found.\n";
}
else {
cout << "Enter amount to withdraw: ";
double amount;
cin >> amount; cin.ignore(10, '\n');
V[index].withdraw(amount);
cout << "New balance is: " << V[index].getBalance() << endl;
}
}
void averageBalance(const apvector<Customer> &V) {
//postcondtion: reports average balance of all customers,
// the largest and the smallest balance
const int SIZE = V.length();
if ( SIZE == 0 ) {
cout << "No customers; therefore no average is possible\n";
}
else {
int maxPos(0), minPos(0);
double mean, sum(V[0].getBalance());
for (int index = 1; index < SIZE; ++index) {
sum += V[index].getBalance();
if ( V[index].getBalance() > V[maxPos].getBalance() )
maxPos = index;
else if ( V[index].getBalance() < V[minPos].getBalance() )
minPos = index;
}//***for index
mean = sum/SIZE;
cout << "Mean balance: " << mean << "\tLargest balance: "
<< V[maxPos].getBalance() << "\nSmallest balance: "
<< V[minPos].getBalance() << endl;
}//***else
}
void deleteCustomer(apvector<Customer> &V) {
// precondtion: bSearch() works!!
//postcondition: if found, specified Customer object is removed by
// shifting all successors (if any) forward and V is resized accordingly
// EXAMPLE deleting L: A D G K L M Q X ----> A D G K M Q X
// 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6
apstring name;
cout << "Enter name of customer to delete: ";
getline(cin, name);
int index = bSearch(V, name);
if ( index < 0 ) {
cout << "ERROR: " << name << " not found.\n";
}
else { // shift every element with position > index one position toward V[0]
const int SIZE = V.length();
for (int p = index; p < SIZE-1; p++) {
V[p] = V[p+1];
}
V.resize(SIZE-1); // chop off last element
}
}
void sortByName(apvector<Customer> &v) {
//postcondition: Elements of v are in ascending order by name
const int SIZE = v.length();
for (int current = 0; current < SIZE-1; current++) {
int minPos = current;
for (int k = current+1; k < SIZE; k++) {
if ( v[k].name < v[minPos].name )
minPos = k;
}
Customer temp = v[current];
v[current] = v[minPos];
v[minPos] = temp;
}
}
void addOneThousand(apvector<Customer> &v) {
//postcondition: 1000 is added to balance of every customer whose
// name contains two or more LOWERCASE vowels
const int SIZE = v.length();
for (int index = 0; index < SIZE; index++) {
int vCount = 0;
for (int stPos = 0; stPos < v[index].name.length() && vCount < 2;
stPos++) {
switch( v[index].name[stPos] ) {
case 'a':
case 'e':
case 'i':
case 'o':
case 'u': vCount++; break;
default: break;
} //** switch
} //** for stPos
if ( vCount >= 2 )
v[index].balance += 1000;
} //** for index
}
void selectSort(apvector<apstring> &V) {
//postcondition: V's elements are in ascending order
const int SIZE = V.length();
for (int current = 0; current < SIZE - 1; ++current) {
int minPos = current;
for (int p = current + 1; p < SIZE; p++) {
if ( V[p] < V[minPos] )
minPos = p;
}
apstring temp = V[current];
V[current] = V[minPos];
V[minPos] = temp;
}
}
int PosOfMax(const apvector<long> &A) {
const int SIZE = A.length();
int maxPos = 0;
for (int k = 1; k < SIZE; k++)
if ( A[k] > A[maxPos] )
maxPos = k;
return maxPos;
}//*** PosOfMax
int PosOf2nd(apvector<long> &A) {
const int SIZE = A.length();
int maxPos = PosOfMax(A), maxPos2;
if ( maxPos == 0 ) // maxPos2 can't = maxPos
maxPos2 = 1;
else
maxPos2 = 0;
for (int index = 0; index < SIZE; index++) {
if ( A[index] > A[maxPos2] && index != maxPos )
maxPos2 = index;
}
return maxPos2;
}//*** PosOf2nd
// non-iterative version
int PosOf2nd(apvector<long> &A) {
int maxPos = PosOfMax(A);
long maxVal = A[maxPos];
A[maxPos] = LONG_MIN;
int maxPos2 = PosOfMax(A);
A[maxPos] = maxVal;
return maxPos2;
}//*** PosOf2nd
void ZeroBetween(apvector<long> &A) {
int left = PosOfMax(A);
int right = PosOf2nd(A);
if ( left > right) {
int tmp = left;
left = right;
right = tmp;
}
for (int k = left + 1; k < right; k++ )
A[k] = 0;
}//*** ZeroBetween
//------------------------------------------------
// Linear search algorithm (sorted list)
//------------------------------------------------
int linearSearch(const apvector<apstring> &V, const apstring &item) {
// precondition: vector V is sorted and contains no duplicates
//postcondition: If item is in V, its index is returned, else -1 is returned
const int SIZE = V.length();
for (int index = 0; index < SIZE; index++) {
if ( V[index] == item )
return index;
else if ( V[index] > item ) // A match is no longer possible!!
return -1;
}
return -1;
}
//------------------------------------------------
// Binary search
//------------------------------------------------
int binarySearch(const apvector<apstring> &V, const apstring &item) {
// precondition: vector V is sorted and contains no duplicates
//postcondition: If item is in V, its index is returned, else -1 is returned
int lo(0), hi = V.length() - 1, mid;
while ( lo <= hi ) {
mid = (lo + hi)/2;
if ( item < V[mid] )
hi = mid - 1;
else if ( item > V[mid] )
lo = mid + 1;
else
return mid;
}
return -1;
}
void reverse(apvector<int> &apv) {
//postcondition: elements (if any) of apvector apv are
// put in reverse order: 21 15 13 17 ---> 17 13 15 21
const int LEN = apv.length();
//--------------------------------------------------------
// Your Code (define additonal variables as needed):
for (int k = 0; k < LEN/2; ++k) {
int temp = apv[k];
apv[k] = apv[LEN - 1 - k];
apv[LEN - 1 - k] = temp;
}
}
void stats(const apvector<int> &apv, double &mean, int &index) {
const int LEN = apv.length();
int sum(0);
index = 0;
for (int k = 0; k < LEN; ++k) {
sum += apv[k];
if ( apv[k] <apv[index] )
index = k;
}
mean = double(sum)/LEN;
}
void findLargest(void) {
// precondition: SIZE > 0, list[] contains no duplicate elements
//postcondition: variable index contains position of largest element
const int SIZE(10);
double list[SIZE] = { 3.5, -4.7, 100, 7, 100.1, 23, -57, -0.09, 99, -77 };
int index(0);
//------------------------------------------------------------------------
for (int k = 1; k < SIZE; k++) {
if ( list[k] > list[index] ) {
index = k;
}
}
//------------------------------------------------------------------------
cout << "\nindex position = " << index
<< "\tlargest value = " << list[index] << endl << endl;
}
int toInt(apstring number, int r) {
// precondition: number represents number in radix r, 2 <= r <= 10
//postcondition: returns numerical value that number represents
int sum(0);
const int len(number.length());
for (int digitPos = 0; digitPos < len; ++digitPos) {
sum = r*sum + int(number[digitPos] - '0'); //**int() isn't necessary
}
return sum;
}
apstring toRadix(int n, int r) {
// precondition: n >= 0, 2 <= r <= 36
//postcondtion: Returns st which is a representation of n
// in r's scale of notation
const apstring digit("0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ");
apstring st;
do {
st = digit[n % r] + st;
n /= r;
} while ( n != 0 );
return st;
}
apstring toRadix(int n, int r) {
// precondition: n >= 0, 2 <= r <= 10
//postcondtion: Returns st which is a representation of n
// in r's scale of notation
apstring st;
do {
st = char('0' + n % r) + st;
n /= r;
} while ( n != 0 );
return st;
}
//-----------------------------------------------------------------
// X Letter Grade
// ---------------- ------------------
// x > 50 error
// 30 <= x <= 50 A
// 20 <= x < 30 B
// 10 <= x < 20 C
// x < 10 D
//-----------------------------------------------------------------
This solution illustrates the properties of the switch statement
at the expense of being practical. A more practical approach would
be to replace each assignment to st with a return statement involving
the same string value, thereby eliminating the need for all the break
statements.
apstring letterGrade(int n) {
//postcondition: returns letter grade specified in table above
apstring errorMessage("ERROR: n greater than 50"), st;
switch ( n/10 ) {
case 5: if ( n > 50 ) { st = errorMessage; break; }
case 4:
case 3: st = "A"; break;
case 2: st = "B"; break;
case 1: st = "C"; break;
default: if ( n < 10 ) {st = "D"; break; }
else { st = errorMessage; break; }
}//***switch
return st;
}
Leo and Reid's multiplication table challenge solutions
// Reid Sheridan
int main(){
int x(1);
while(x <= 100){
if(x % 10 == 0){
cout << x << endl;
}
else{
cout << x % 10 * (x / 10 + 1) << " ";
}
x ++;
}
// Leo Gertsenshteyn
int count(0);
while (count <= 99)
{
cout<< ( (count / 10) + 1 ) * ( (count % 10) + 1) << "\t";
if ( count % 10 == 9 ) { cout<<endl;}
count++;
}
cout << endl << endl;
apstring decToBinary(int n) {
// precondition: n >= 0
//postcondtion: returns binary representation of n
apstring binary;
for (;;) {
if ( n % 2 == 0 )
binary = '0' + binary;
else
binary = '1' + binary;
n /= 2;
if ( n == 0 ) break;
}
return binary;
}
void eFormat(void) {
//postcondition: x is assigned 8.123 x 10^47 using e-format
// y is assigned 0.00008123 using e-format
apstring title("Using e-format to assign floating point values");
cout << "\n\n\n" << setw(38 + title.length()/2) << title.c_str() << endl << endl;
//---------------------------------------------------
// replace assignments to x, y with appropriate ones:
//---------------------------------------------------
double x(-77), y(-77);
x = 8.123e47;
cout << "x should print out as 8.123e47, x = " << x << endl;
y = 8.123e-5;
cout << "y should print out as 8.123e-5 , y = " << y << endl;
}
int sigma(int n) {
// precondition: n > 0
//postcondition: returns sum of n's proper divisors
//EXAMPLE: sigma(8) = 1 + 2 + 4 = 7 and sigma(12) = 1 + 2 + 3 + 4 + 6 = 16
int sum(1), d;
double sqrtN = sqrt(n);
for (d = 2; d < sqrtN; d++) // d < sqrt(n) condition means that testing
if (n % d == 0) // for perfect square n can be done after the loop
sum += d + n/d;
if (d == sqrtN) // now determine whether or not n's a perfect square!!
return sum + d;
else
return sum;
}
bool isPerfect(int n) {
// precondition: n > 1
// postcondition: Uses sigma() to return true when n is the sum of its
// proper divisors, otherwise return false
// EXAMPLE: 6 is perfect since 1 + 2 + 3 = 6; 28 because 1 + 2 + 4 + 7 + 14 = 28
return (sigma(n) == n);
}
void listAmicable(void) {
//post: lists amicable pairs from 2 to n
const int LAST(100000);
string title("Listing Amicable Pairs from 2 to ");
cout << "\n\n\n\n\n" << setw(37 + title.length()/2) << title.c_str()
<< LAST << endl << endl;
cout << "You should print out 13 unique pairs, the last being (79750, 88730)\n\n";
int count(0), amicable2;
for (int n = 2; n <= LAST; n++) {
amicable2 = sigma(n); // (n, amicable2) amicable?
if (amicable2 > n && sigma(amicable2) == n) { // Don't use sigma() again
count++; // unless it's necessary!!
cout << setw(3) << count << ". " << setw(15)
<< n << setw(15) << amicable2 << endl;
}
}//***for
}
bool isPrime(int n) {
//postcondition: returns true if n is prime
// else returns false
if ( n == 2 )
return true;
else if ( n % 2 == 0 ) // test for evenness before testing for any other factor
return false;
else {
int last = int(sqrt(n)); // test to <= sqrt(n) instead of < n/2
for (int d = 3; d <= last; d += 2) { //increment by twos, not by ones
if ( n % d == 0 )
return false;
}
return true;
}
}
1. string conversion problem
apstring toUpper(apstring s) {
//postcondition: returns upper case version of s
int len = s.length();
apstring temp("");
for ( int index = 0; index < len; ++index ) {
if ( s[index] >= 'a' && s[index] <= 'z' )
temp = temp + char( s[index] + 'A' - 'a' );
else
temp = temp + s[index];
}
return temp;
}
2. primitive triples problem
int GCD(int n, int d) {
//precondition: n, d > 0
//postcondition: returns gcd(n,d)
for (;;) {
int r = n % d;
if ( r == 0 ) break;
n = d;
d = r;
}
return d;
}
...
...
for ( m = 2; m <= max; ++m )
for ( n = 1; n < m; ++n ) {
if ( m % 2 != n % 2 && GCD(m,n) == 1 ) { // different parity and rel prime
if ( count % 10 == 0 ) {
cout << " k m n a b c\n"
<< "------------------------------------------------\n";
}
++count;
a = 2*m*n;
b = m*m - n*n;
c = m*m + n*n;
cout << setw(wdth) << count << setw(wdth) << m << setw(wdth) << n
<< setw(wdth) << a << setw(wdth) << b << setw(wdth) << c << endl;
}//*** if m % 2 != n % 2 && relatively prime
}
// ================================================================= // CODE TO GENERATE PRIMITIVE TRIPLES int n2, d2, r;
for ( m = 2; m <= max; ++m )
for ( n = 1; n < m; ++n ) {
if ( m % 2 != n % 2 ) { // one odd, one even
n2 = m; d2 = n;
for (;;) {
r = n2 % d2;
if ( r == 0 ) break;
n2 = d2;
d2 = r;
}
if ( d2 == 1 ) { // GCD(m,n) = 1
if ( count % 10 == 0 ) {
cout << " k m n a b c\n"
<< "------------------------------------------------\n";
}
++count;
a = 2*m*n;
b = m*m - n*n;
c = m*m + n*n;
cout << setw(wdth) << count << setw(wdth) << m << setw(wdth) << n
<< setw(wdth) << a << setw(wdth) << b << setw(wdth) << c << endl;
}//*** if d2 == 1
}//*** if m % 2 != n % 2
}
cout << endl << endl;
for ( m = 2; m <= max; ++m )
for ( n = 1; n < m; ++n ) {
if ( count % 10 == 0 ) {
cout << " k m n a b c\n"
<< "------------------------------------------------\n";
}
++count;
a = 2*m*n;
b = m*m - n*n;
c = m*m + n*n;
cout << setw(wdth) << count << setw(wdth) << m << setw(wdth) << n
<< setw(wdth) << a << setw(wdth) << b << setw(wdth) << c << endl;
}//*** for n
Wednesday 10/25 solutions
Note that if condition in if statement includes tests for a2 + c2 = b2 and b2 + c2 = a2, no duplicate
triples will be printed! By initializing b to ensure that it's always greater than a, and by initializing c
to ensure that it's always greater than b, tests that assume a or b is the hypotenuse become irrelevant.
// THE NESTED LOOPS:
cout << " n a b c\n\n";
for ( a = 3; a <= max-2; ++a ) {
for ( b = a + 1; b <= max-1; ++b ) {
for ( c = b + 1; c <= max; c++ ) {
if ( a*a + b*b == c*c ) {
count += 1;
cout << setw(wdth) << count << setw(wdth) << a << setw(wdth) << b
<< setw(wdth) << c << endl;
}
} //*** for c
} //*** for b
} //*** for a
// FILE: gcd2.cpp // PURPOSE: Implement Euclid's Algorithm with a for loop and break stmt //===================================================================== #include <iostream.h>
int main() {
//===============================================================
// PROBLEM: Get natural numbers n and d from keyboard, find
// their GCD, and use GCD to express n/d in lowest terms
//==============================================================
int n, d, r, gcd;
cout << "\n\n\n\n\n\t\t" << "Using Euclid's Algorithm to express n/d "
<< "in lowest terms" << endl << endl;
cout << "Enter natural number n: ";
cin >> n;
while ( n <= 0 ) {
cout << "ERROR: n must be positive---"
<< "Enter positive n: ";
cin >> n;
}
cout << "\nEnter natural number d: ";
cin >> d;
while ( d <= 0 ) {
cout << "ERROR: d must be positive---"
<< "Enter positive d: ";
cin >> d;
}
cout << endl;
// ==============================================================
// INSTRUCTIONS: Define any additional variables you need.
// -------------------------------------------------------------
// SAMPLE OUTPUT: Enter natural numbers n d: 30 108
// GCD = 6
// 30/108 = 5/18
// -----------------------------------------------------------------
// TEST DATA: (1449, 460) = 23, (328, 1804) = 164, (1976, 7429) = 19
// =================================================================
// YOUR CODE:
int n2(n), d2(d); //*** Save values of n and d for output after loop!!!
for ( ; ; ) {
r = n % d;
if ( r == 0 ) break;
n = d;
d = r;
}
gcd = d;
// ==============================================================
cout << endl << "GCD(" << n2 << ", " << d2 << ") = " << gcd << endl;
cout << n2 << "/" << d2 << " = " << n2/gcd << "/" << d2/gcd
<< endl << endl;
return 0;
}
Fibonacci Solution
// =================================================================
// YOUR CODE:
while ( n <= 0 ) {
cout << "ERROR---Enter positive n: ";
cin >> n;
}
int fibBack1, fibBack2, counter;
if ( n == 1 || n == 2 ) { // Note: An if/else control structure isn't
fib = 1; // necessary: The blue-colored statements accomplish
} // the same task when the if/else framework is removed!!
else {
fibBack1 = 1; fibBack2 = 1;
for ( counter = 3; counter <= n; ++counter ) {
fib = fibBack1 + fibBack2;
fibBack2 = fibBack1;
fibBack1 = fib;
}
}
// ==============================================================
cout << "fib(" << n << ") = " << fib << endl << endl;
// FILE: while3.cpp // PURPOSE: Solve problems with while loops //================================================================= #include <iostream.h> #include "apstring.h"
int main() {
//===============================================================
// Problem 1. Calculate an average using 'sentinel' or 'dummy'
// value of -1 for user to terminate end of input
// INSTRUCTIONS: Data input terminates after 5 valid scores or
// after score of -1 is entered. Define variables if needed.
//==============================================================
int counter, score, sum, max(5);
double average;
cout << "\n\n\n\n\n\n\n\n" << "Computing an average of " << max
<< " or fewer integer scores with sentinel value of -1" << endl << endl;
// ==============================================================
// YOUR CODE:
counter = 0;
sum = 0;
while ( counter < max ) {
cout << "Enter score (-1 to quit): ";
cin >> score;
if ( score == -1 )
break;
++counter;
sum += score;
}
//---------------------- Determine if there's a basis for an average:
if ( counter > 0 ) {
average = double(sum)/counter;
cout << "average = " << average << endl;
}
else {
cout << "No basis for average\n";
}
// ==============================================================
cout << endl << endl;
return 0;
}
// FILE: while2.cpp // PURPOSE: Solve problems with while loops //================================================================= #include <iostream.h> #include "apstring.h"
int main() {
apstring title("Solving problems with while loops");
cout << "\n\n\n\n\n" << "\t\t" << title << endl << endl;
//----------------------------------------------------------------------------
// Problem 1. Use while loop to find sum of 1st 50 terms of 2 + 5 + 8 + ...
// NOTE: The answer is 3775
//----------------------------------------------------------------------------
cout << "Using a while loop to find sum of 1st 50 terms of: 2 + 5 + 8 + ...\n\n";
int sum, counter;
//============================================================================
// INSTRUCTIONS: 1. Use variables sum, counter. Define additional variables if needed.
// 2. At the end of the code, the variable sum should contain solution
int a(2);
sum = 0; counter = 1;
while ( counter <= 50 ) {
sum = sum + a;
a = a + 3;
++counter;
}
//============================================================================
cout << "The sum is: " << sum << endl << endl << endl << endl;
//----------------------------------------------------------------------------
// Problem 2. Reverse a string WITHOUT defining another string (using indexing)
// Test data: "ABCD" reverses to "DCBA", "ABC" to "CBA", and "A" to "A"
//----------------------------------------------------------------------------
int cntr;
apstring st, stars("**********************");
cout << stars + stars + stars << "\n\n\n\t\t"
<< "Reversing a string without defining another string\n\n";
cout << "Enter a string to reverse: ";
getline(cin, st);
//============================================================================
// INSTRUCTIONS: 1. Use variables st and cntr. Do NOT define additional string.
// 2. At the end of the code, the variable st should contain solution
int len(st.length());
char tmp;
cntr = 0;
while ( cntr < len/2 ) {
tmp = st[cntr];
st[cntr] = st[len - 1 - cntr];
st[len - 1 - cntr] = tmp;
++cntr;
}
//============================================================================
cout << "st is now ==============>: " << st << endl << endl;
return 0; }
// FILE: while1.cpp
// PURPOSE: Solve problems with while loops (due 10/16)
//=================================================================
#include <iostream.h>
#include "apstring.h"
int main() {
//===============================================================
// Problem 1. Convert string to lower case using indexing,
// repetition, and a counter.
//==============================================================
apstring st;
cout << "\n\n\n\n\n\t\tConverting string to lower case\n\n";
cout << "Enter string ===>: ";
getline(cin, st); // equivalent to: cin >> st;
// ==============================================
// Your code:
int index(0), last(st.length()-1), diff('a' - 'A');
while ( index <= last ) {
if ( st[index] >= 'A' && st[index] <= 'Z' )
st[index] = char(st[index] + diff);
++index;
}
// ==============================================
cout << "string now equals: " << st << endl << endl << endl << endl;
//===============================================================
// Problem 2. Calculate an average when number of scores is
// entered interactively.
//==============================================================
apstring stars("**********************");
int numScores, score, sum;
double average;
cout << stars + stars + stars << "\n\n\n\t\t"
<< "Computing an average of integer scores" << endl << endl;
cout << "Enter number of scores: ";
cin >> numScores;
// ==============================================================
// Your code:
int counter = 1;
sum = 0;
while ( counter <= numScores ) {
cout << "Enter score: ";
cin >> score;
sum = sum + score;
counter = counter + 1;
}
//---------------------- Determine if there's a basis for an average:
if ( numScores > 0 ) {
average = double(sum)/numScores;
cout << "average = " << average << endl << endl;
}
else {
cout << "No basis for average\n\n";
}
// ==============================================================
return 0; }
// FILE: quad2.cpp // PURPOSE: Use nesting to implement quad formula program //================================================================= #include <iostream.h> #include <iomanip.h> #include <math.h> #include "apstring.h"
int main() {
double x1, x2, a_, b_; // (a_, b_) represent (a, b) in a + bi
int a, b, c, discrim;
apstring title("Solving ax^2 + bx + c = 0");
cout << "\n\n\n\n\n\n" << setw(39 + title.length()/2)
<< title.c_str() << endl << endl;
cout << "Enter coefficients a b c: ";
cin >> a >> b >> c;
cout << endl;
if ( a == 0 ) {
cout << "ERROR: quadratic coefficient can't be 0\n";
}
else {
discrim = b*b - 4*a*c;
if ( discrim < 0 ) { //============> imaginary roots
a_ = -b/(2*a);
b_ = sqrt(-discrim)/(2*a);
cout << "{" << a_ << " + " << fabs(b_) << "i, "
<< a_ << " - " << fabs(b_) << "i}" << endl;
cout << "Roots are imaginary\n\n";
}
else { // =================> real roots
x1 = (-b + sqrt(discrim))/(2*a);
if ( discrim == 0 ) { // ========> double root
cout << "{" << x1 << "}\n";
}
else { // ======> 2 distinct roots
x2 = (-b - sqrt(discrim))/(2*a);
cout << "{" << x1 << ", " << x2 << "}\n";
}
if ( sqrt(discrim) == floor(sqrt(discrim)) )
cout << "Roots are real and rational.\n\n";
else
cout << "Roots are real and irrational.\n\n";
}
}
return 0;
}
if ( a >= b + c || b >= a + c || c >= a + b )
cout << "ERROR: the lengths don't form a triangle\n";
else if ( a*a < b*b + c*c && b*b << a*a + c*c && c*c < a*a + b*b ) {
cout << "Triangle is acute\n\n";
}
else if ( a*a > b*b + c*c || b*b > a*a + c*c || c*c > a*a + b*b ) {
cout << "Triangle is obtuse\n\n";
}
else {
cout << "Triangle is right\n\n";
}
1. Leaving aside the question of whether or not it's wise not to compare lengths a, b, and c; it is
clearly not necessary.
2. Using Pythagoras to test for acuteness and obtuseness, if we don't know which length is longest, it is
necessary to choose carefully between the logical operators && (for acuteness) and || (for obtuseness).
if ( a*a < b*b + c*c && b*b << a*a + c*c && c*c < a*a + b*b ) {
cout << "Triangle is acute\n\n";
}
else if ( a*a > b*b + c*c || b*b > a*a + c*c || c*c > a*a + b*b ) {
cout << "Triangle is obtuse\n\n";
}
else {
cout << "Triangle is right\n\n";
}
// FILE: escape.cpp
#include <iostream.h>
#include "apstring.h"
int main() {
apstring st("ABCDE"), t, u, v;
cout << "\n\n\n\n" << "st = " << st << endl;
// 1. Replace "?" with and expression that assigns t the value represented // by st WITHOUT the leading character and the last character t = st.substr(1, st.length() - 2); cout << "1. Without st's lead and last characters, t = " << t << endl;
// 2. Replace "?" with an expression that assigns u the value of st // with the lead and last character interchanged u = st.substr(st.length() - 1, 1) + st.substr(1, st.length() - 2) + st.substr(0, 1); cout << "2. With st's lead and last characters swapped, u = " << u << endl;
// 3. Replace "?" with an expression that assigns u the value of st // without its "middle" character. Let numerical value of middle be defined as st.length()/2 v = st.substr(0, st.length()/2) + st.substr(st.length()/2+1, st.length() - st.length()/2); cout << "3. Without st's middle character, v = " << v << endl;
return 0; }
#include <iostream.h>
#include "apstring.h"
int main() {
apstring st1, st2;
// Setting up st1 for this output==> "Hello" he said. I
said "Bye" sadly.
st1 = "\"Hello\" he said. I said \"Bye\"
sadly.";
// Setting up st2 for this output==> The new line character is '\n'.
st2 = "The new line character is '\\n'.";
cout << "\n\n\n\n\n" << "st1 = " << st1
<< endl
<< "st2 = "
<< st2 << endl;
return 0;
}
// FILE: coins.cpp // PURPOSE: Use int properties and int division to solve // minimum # of coins problem
#include <iostream.h> #include <math.h>
int main() {
double amount;
int quarters, dimes, nickels, cents;
int totalCents;
cout << endl << endl;
cout << "Finding the minimum number of total coins to "
<< "produce the given $ amount" << endl;
cout << "By Anna" << endl << endl;
cout << "Enter dollar amount: ";
cin >> amount;
cout << endl;
totalCents = int(100 * amount + 0.5); // double to int assignment
// totalCents = int(100 * amount) didn't work when user entered 2.69!!
quarters = totalCents / 25; totalCents = totalCents - 25 * quarters; //*there's a better way to do this dimes = totalCents / 10; totalCents = totalCents - 10 * dimes; //*there's a better way to do this nickels = totalCents / 5; totalCents = totalCents - 5 * nickels; //*there's a better way to do this cents = totalCents; cout << "Number of quarters: " << quarters << endl; cout << "Number of dimes: " << dimes << endl; cout << "Number of nickels: " << nickels << endl; cout << "Number of pennies: " << cents << endl; cout << "$ in quarters: " << 0.25 * quarters << endl; cout << "$ in dimes: " << 0.10 * dimes << endl; cout << "$ in nickels: " << 0.05 * nickels << endl; cout << "$ in cents: " << 0.01 * cents << endl;
double total(0.25 * quarters + 0.10 * dimes + 0.05 * nickels + 0.01 * cents); cout << "Total = " << total << endl << endl;
return 0; }
The strategy here is to utilize the properties of the floor() function for
rounding to nearest
tenth and hundredth. Consider problem of rounding 79.538 to nearest 100th. The floor
function can't help us
operate on the digit in the hundredth place of the given number, but if we multiply 79.538
by 100, it can!!
Therefore, floor(100 * x + 0.5) = floor(100 * 79.538 + 0.5) = floor(7953.8 + 0.5) =
floor(7954.3) = 7954.0.
Now since we multiplied x by 100, we simply divide floor(100 * x + 0.5) by 100: 7954.0/100
= 79.54, which
is 79.538 to the nearest 100th!!
Note: additional variables here are fine, but I don't see how they contribute the clarity
of your program.
// FILE: round.cpp // PURPOSE: round non-negative number to nearest integer, tenth, hundredth
#include <iostream.h> #include <math.h>
int main() {
double x;
cout << endl << endl;
cout << "Rounding to nearest integer, nearest 10th, and nearest 100th"
<< endl << "By Anna" << endl << endl;
cout << "Enter a non-negative number with 3 or more decimal places: ";
cin >> x;
cout << endl << "To nearest integer: " << floor(x + 0.5) << endl; cout << "To nearest tenth: " << floor(10*x + 0.5) /10 << endl; cout << "To nearest hundredth: " << floor(100*x + 0.5) /100 << endl; return 0; }