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 <iostream.h>
#include <string>
#include <stdlib.h>     // random, srandom
#include <time.h>       // 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;
}