SOLUTIONS FOR THE MIDTERM PROGRAMMING ASSIGNMENT.
Problem 1: Implement division using only addition and subtraction.
// returns n/k for positive integers n, k
// for other values of n, k the behavior of this function is undefined
int divide( int n, int k ){
int count = 0;
while( k <= n ){ // count how many times k "goes" into n, i.e.
// can be subtracted from n withot getting a negative
n = n - k;
count++;
}
return count;
}
-----------------------------------------------------------------------
Problem 2: Factor an integer.
int n, p;
cin >> n;
cout << n << " : " ; // print the number itself
while( n > 0 ){ // end the loop if the input is negative
if( n == 1 ) // this is a special case: 1 is never printed otherwise
cout << 1 << endl;
else {
p = 2;
while( n > 1 ){ // n will be changing throughout this loop
while( n % p == 0 ){ // p divides n
cout << p << " ";
n = n/p; // remove a copy of p from n
}
// after this loop all copies of p have been "divided out" of n, and
// p will be printed as many times as it divides n
p++; // go to the next number that might divide n (see NOTE)
}
cout << endl;
}
// enter a new number
cin >> n;
}
NOTE: Not only primes, but ALL numbers up to the actual largest divisor
of n will be tried as values of p . This may seem to be a bug, because we
only want to print the prime divisors of n . However, NONE of non-prime
divisors will be printed.
To see why this is so, consider the following example: take n==120 and
trace the algorithm starting with p = 2. n will be divided by 2 for as long
as what remains is divisible by 2, i.e. 3 times ( 120 = 2*2*2*3*5 ). After
this n==15. Then it will be divided by 3, so that n==5. The next p to try
is 4=2*2, a non-prime number. BUT, all 2's have already been "divided out"
of n . And so for each non-prime value of p all of the primes that compose
p will be "divided out" earlier. So no non-prime divisor p will ever enter
the inner while loop.
Notice how the names n and p get re-used on every iteration. This is
a very common technique.
-----------------------------------------------------------------------
Problem 3: Here's my program, complete with testing. You may
disregard the testing part and go directly to the function
num that does the transformation.
#include
#include
#include // random, srandom
#include // srandom is seeded with current time
// DISCLAMER: This is neither the shortest, nor the most
// elegant way of solving the problem.
// Constants for testing: Declare any parameters of your program
// as const at the top. Leaving unexplained numbers in your code
// is bad style.
const int MAX_NUMBER = 999999; // this is the largest number
// for which the output is correct
const int ALL_UP_TO = 2000; // test all numbers up to this one
const int RANDOM_TESTS = 100; // the number of random tests to run
string upto20[] = { "zero", "one ", "two ", "three ", "four ", "five ",
"six ", "seven ", "eight ", "nine ", "ten ", "eleven ",
"twelve ", "thirteen ", "fourteen ", "fifteen ",
"sixteen ", "seventeen ", "eighteen ", "nineteen " };
string tens[] = { "NaN", "NaN", "twenty ", "thirty ", "forty ", "fifty ",
"sixty ", "seventy ", "eighty ", "ninety " };
// the first two entries should never get printed
string num(int);
string num3(int);
int main(){
for( int i=0; i <= ALL_UP_TO ; i++)
cout << i << " : " << num(i) << endl;
// srandom seeds the pseudo-random number generator. It is usually
// seeded with current time (expressed in seconds since 00:00:00
// Jan 1, 1970), which is returned by the system call time(NULL)
int x;
srandom( (unsigned int) time(NULL) );
for( int i=0; i < RANDOM_TESTS ; i++ ){
x = random() % MAX_NUMBER;
cout << x << " : " << num(x) << endl;
}
return 0;
}
// takes a number and returns the string corresponding to that number
string num( int n ){
if ( n == 0 ) return "zero"; // this is a special case, because
// "zero" doesn't appear otherwise
string result = "";
int thousands_part = n / 1000; // separate the thousands
if( thousands_part != 0 )
result += num3( thousands_part ) + "thousand ";
result += num3( n % 1000 ); // the other part ( < 1000 )
return result;
}
// process a number with no more than 3 digits
string num3( int n ){
string result = "";
int hundreds_place = n/100;
if( hundreds_place != 0 )
result += upto20[ hundreds_place ] + "hundred ";
int last_two = n%100;
if ( last_two != 0 ){ // don't print zero
if ( last_two < 20 ) result += upto20[ last_two ];
else{ // n >= 20 subdivide into tens and units
int tens_place = last_two/10;
if( tens_place != 0 ) result += tens[ tens_place ];
int units_place = last_two % 10;
if ( units_place !=0 ) result += upto20[ units_place ];
}
}
return result;
}