Fractions, Fractions, Fractions

(Solved, coded, and written by Sean Rae)

The general gist of this problem is that they present a sequence of numbers that are fractions between 0 and 1.  The sequence as it was given is as follows:

  1. 1/2

  2. 1/3

  3. 2/3

  4. 1/4

  5. 2/4

  6. 3/4

  7. 1/5

  8. 2/5

  9. 3/5

  10. 4/5  (note that the original erroneously had 4/6 here)

  11. 1/6

  12. 2/6

  13. 3/6

  14. 4/6

The input would be two integers that represent positions in the sequence.  For instance, if they gave "13" and "7" as inputs, we would have to translate that to "3/6" and "1/5".  Once we translate these positions to fractions, we add them together and simplify the result.  The final output will be the position in the list of the resulting fraction.

Examples:

Input:
2 13		 Output:
15
Input:
4 3		 Output:
66

Our Solution:

First of all, thanks to Dr. Goolsby of the math department for helping me solve this.  The code is in black text and the comments are in bright blue.

#include <iostream.h>
#include <fstream.h>

#undef DEBUG

struct fraction
{
   int num;
   int denom;
};
The returnFraction() subroutine is the part of the code that generates the desired number sequence.  It uses what I call "bins" as a way of collecting like terms.  I chose to have a change in denominator (e.g. going from thirds to fourths) signal a change in bins.
// take a position and find its fraction
fraction returnFraction(int position)
{
   // binTop is the location of n-1/n
   // binBottom is the location of 1/n
   int binTop=0, binBottom=0;
   int i; // nth bin
   fraction clangy; // the fraction to return

   for(i=1; binTop < position; i++)
   {
      binTop += i;
   }
   binBottom = binTop - i + 2;
   clangy.denom = i;
   clangy.num = position - binBottom + 1;
   return clangy;
}
I know, I know.  This is just a hack.  A better solution would be to logically step through returnFraction(), line by line, and rewrite it backwards, instead of just repeatedly calling it.  Oh well, it still works.
// take a fraction and find its location
int returnPosition(fraction incoming)
{
   fraction temp;

   // the 100000 is just to not have an infinite loop... it's bad style.
   for(int i=1; i != 100000; i++)
   {
      temp = returnFraction(i);
   // if we found it
   if(temp.num == incoming.num && temp.denom == incoming.denom)
      return i;
}

#ifdef DEBUG
   cout << "ERROR: could not match a position to "
        << incoming.num << "/" << incoming.denom << "!" << endl;
#endif

   return 0; // uh-oh, shouldn't ever happen
}
This was based very heavily upon a pseudocode version found in Discrete Mathematics by Richard Johnsonbaugh, on page 155.  The basis of the algorithm is mostly self-explanatory, as it is usually covered in introductory programming classes.
// euclid's greatest common denominator algorithm
int euclid(int a, int b)
{
   int temp=0;

   // make sure that a is the larger number
   if(a < b)
   {
      temp = a;
      a = b;
      b = temp;
   }

   while(b != 0)
   {
      // the classic division "algorithm"
      // a/b -> a = bq + r, where 0 <= r < b
      temp = a;
      a = b;
      b = temp % b;
   }
   return a;
}
This is just the rest of the code, mostly the input/output rather than the majority of the effort.  Note that I made use of preprocessor directives (the #define stuff) to make it easy to change from descriptive output to the output that the ACM competition required.
void main()
{
   ifstream input;
   int posOne=0, posTwo=0;
   fraction a, b, c;
   int gcd=0;

   input.open("one");
   input >> posOne >> posTwo;
   input.close();

   a = returnFraction(posOne);
   b = returnFraction(posTwo);

#ifdef DEBUG
   cout << "a: " << a.num << "/" << a.denom << endl;
   cout << "b: " << b.num << "/" << b.denom << endl;
#endif

   c.num = a.num*b.denom + b.num*a.denom;
   c.denom = a.denom*b.denom;

   // simplify c, the answer fraction
   gcd = euclid(c.num, c.denom);
   if(gcd != 1) // i.e. needs to be reduced
   {
      c.num = c.num / gcd;
      c.denom = c.denom / gcd;
   }

#ifdef DEBUG
   cout << "Final fraction is: " << c.num << "/" << c.denom << endl;
   cout << "Position: " << returnPosition(c) << endl;
#else
   cout << returnPosition(c) << endl;
#endif
}