For this assignment, you will implement support for using Rational Numbers (aka.

Question

For this assignment, you will implement support for using Rational Numbers (aka. Fractions). These rational numbers will be stored in records of Rational type declared as follows:

struct Rational {

int num;

int denom;

}

A record of Rational type stores a rational number's numerator and denominator. A negative number is represented by a negative numerator and a positive denominator.  The following questions ask you to implement functions for carrying out operations on rational numbers or on arrays of rational numbers.  

Note: Functions 4 through 14 should never directly access the num and denom fields of a Rational record.  In other words, to create a new Rational, they should use function makeRational and to access the numerator and denominator of a Rational, they should use the numerator and denominator functions.  

Note: For functions 13 through 15, you may adapt the code already available in the course readings.  In other words, you do not have to write the code for the sorting and searching algorithms from scratch.  All you need to do is to adapt them so that they sort or search for a Rational rather than (say) an integer.

Note: Unlike Assignment 8, the functions which you write for this assignment do not have to be recursive.

Implement the following functions:

1, Rational makeRational(int n, int d)

Creates and returns a Rational with numerator n and denominator d.

2. int numerator(Rational r)

Returns the numerator of r.  For example, for 9/2, 9 should be returned.

3. int denominator(Rational r)

Returns the denominator.  For example, for 9/2, 2 should be returned.

4. bool equal(Rational r1, Rational r2)

Returns true if r1 and r2 are equal, and false otherwise.  For example, 3/2 and 6/4 are equal; 3/2 and 2/3 are not equal. [Hint: x1/y1 == x2/y2 iff x1*y2 == x2*y1]

5. bool lessThan(Rational r1, Rational r2)

Returns true if r1 is less than r2, and false otherwise. [Hint: Similar to equal]

6. bool greaterThan(Rational r1, Rational r2)

Returns true if r1 is greater than r2, and false otherwise. [Hint: Similar to equal]

7. Rational add(Rational r1, Rational r2)

Returns the sum of r1 and r2.

8. Rational subtract(Rational r1, Rational r2)

Returns the result of subtracting r1 from r2.

9. Rational multiply(Rational r1, Rational r2)

Returns the product of r1 and r2.

10. Rational divide(Rational r1, Rational r2)

Returns the result of dividing r1 by r2.

11. void print(Rational r)

Outputs the rational number to cout in the format w n/d, where w is the whole part of the fraction, and n and d are the numerator and the denominator of the fractional part, respectively.  Negative numbers are preceded with a minus (-) sign and a space character.  Numbers which reduce to a whole number simply appear as integers. For example, 9/2 is printed as 4 1/2, -9/2 is printed as - 4 1/2, 1/3 is printed as 1/3, 6/2 is printed as 3, -6/2 is printed as - 3, etc. However, the rational numbers should not be printed in their reduced form.  For example, 2/6 should be printed as 2/6, not as 1/3.  In either case, the contents of the record should not change as a result of the printing.

This function may be quite involved because of the number of cases involved.  You may find the abs() function useful in handling negative numbers.  Recall that a negative rational number is represented by a negative numerator and a positive denominator.

12. void printRationalArray(Rational ra[], int n)

Prints the contents of an array of rational numbers.  For example, an array containing two rational numbers 1/2 and 3/2 should be printed as [ 1/2 , 1 1/2 ].

13. int linearSearch(Rational ra[], int n, Rational s)

Searches for instances of a rational number s in an array ra of size n; the array may or may not be sorted. The function returns the number of instances of s found in the array.  In other words, it returns 0 if no instances have been found, returns 1 if it appears once in the array, and so on.

14. void insertionSort(Rational ra[], int n)

Sorts array ra of size n containing rational numbers using Insertion Sort

15. int binarySearch(Rational ra[], int n, Rational s)

Searches for an instance of rational number s in a sorted array ra of size n. If s is found, returns index of the first instance found (ignoring any others); if not found, returns -1.

Explanation / Answer

#include <iostream>
#include <cmath>
using namespace std;
struct Rational
{
    int num;
    int denom;
};
// Creates and returns a Rational with numerator n and denominator d.
Rational makeRational(int n, int d)
{
Rational R;
R.num = n;
R.denom = d;
return R;
}

// Returns the numerator of r. For example, for 9/2, 9 should be returned.
int numerator(Rational r)
{
return r.num;
}

// Returns the denominator. For example, for 9/2, 2 should be returned.
int denominator(Rational r)
{
return r.denom;
}

// Returns true if r1 and r2 are equal, and false otherwise. For example,
// 3/2 and 6/4 are equal; 3/2 and 2/3 are not equal.
// [Hint: x1/y1 == x2/y2 iff x1*y2 == x2*y1]
bool equal(Rational r1, Rational r2)
{
return (numerator(r1)*denominator(r2)==numerator(r2)*denominator(r1));
}

// Returns true if r1 is less than r2, and false otherwise. [Hint: Similar to equal]
bool lessThan(Rational r1, Rational r2)
{
return (numerator(r1)*denominator(r2)<=numerator(r2)*denominator(r1));
}

// Returns true if r1 is greater than r2, and false otherwise. [Hint: Similar to equal]
bool greaterThan(Rational r1, Rational r2)
{
return (numerator(r1)*denominator(r2) > numerator(r2)*denominator(r1));
}

// Returns the sum of r1 and r2.
Rational add(Rational r1, Rational r2)
{
return makeRational((numerator(r1)*denominator(r2)+numerator(r2)*denominator(r1)) , (denominator(r1)*denominator(r2)));
}

// Returns the result of subtracting r1 from r2.
Rational subtract(Rational r1, Rational r2)
{
return makeRational((numerator(r1)*denominator(r2)-numerator(r2)*denominator(r1)) , (denominator(r1)*denominator(r2)));
}

// Returns the product of r1 and r2.
Rational multiply(Rational r1, Rational r2)
{
return makeRational((numerator(r1)*numerator(r2)) , (denominator(r1)*denominator(r2)));
}

// Returns the result of dividing r1 by r2.
Rational divide(Rational r1, Rational r2)
{
return makeRational((numerator(r1)*denominator(r2)) , (numerator(r2)*denominator(r1)));
}

// Prints the rational number to console in the format w n/d, where w is the whole
// part of the fraction, and n and d are the numerator and the denominator of the
// fractional part, respectively. Negative numbers are preceded with a minus (-)
// sign and a space character. Numbers which reduce to a whole number simply
// appear as integers. For example, 9/2 is printed as 4 1/2, -9/2 is printed as
// - 4 1/2, 1/3 is printed as 1/3, 6/2 is printed as 3, -6/2 is printed as - 3, etc.
// However, the rational numbers should not be printed in their reduced form.
// For example, 2/6 should be printed as 2/6, not as 1/3. In either case, the
// contents of the record should not change as a result of the printing.

// You may find the abs() function useful in handling negative numbers. Recall
// that a negative rational number is represented by a negative numerator and
// a positive denominator.
void print(Rational r)
{
    int w;
if(numerator(r)%denominator(r)==0)
{
w = abs(numerator(r))/abs(denominator(r));
if(numerator(r)<0)
w = -w;
cout << w ;
}
else
{
w = abs(numerator(r))/abs(denominator(r));
if(numerator(r)<0)
{
if(w!=0)
cout << w << " " << "-";
else
cout << "-";
}
else
{
if(w!=0)
cout << w << " ";
else
cout << " ";

}
cout << (abs(numerator(r))-w*denominator(r)) << "/" << denominator(r) ;
}
}
// Prints the contents of an array of rational numbers on console.
// For example, an array containing two rational numbers 1/2 and 3/2
// should be printed as [ 1/2 , 1 1/2 ].
void printRationalArray(Rational ra[], int n)
{
cout << "[ ";
for(int i=0; i<n; i++)
{
print(ra[i]);
if(i!=n-1)
cout << " , ";
}
cout << " ]";
}

// Searches for instances of a rational number s in an array ra of size n;
// the array may or may not be sorted. The function returns the number of
// instances of s found in the array. In other words, it returns 0 if no
// instances have been found, returns 1 if it appears once in the array, and so on.
int linearSearch(Rational r[], int n, Rational s)
{
int count=0;
for(int i=0; i<n; i++)
{
if(equal(s,r[i])) count++;
}
return count;
}

// Sorts array ra of size n containing rational numbers using Insertion Sort.
void insertionSort(Rational ra[], int n)
{
for (int i = 1; i < n; i++)
{
   Rational value = ra[i];
    int j;
   for (j = i; j > 0 && lessThan(value,ra[j - 1]); j--)
   {
   ra[j] = ra[j - 1];
   }
   ra[j] = value;
}
}

// Searches for an instance of rational number s in a sorted array ra of size n.
// If s is found, returns index of the first instance found (ignoring any others);
// if not found, returns -1.
int binarySearch(Rational ra[], int n, Rational s)
{
int begin = 0;
int end = n-1;
int mid = (begin+end)/2;
while(begin<=end)
{
if(lessThan(ra[mid],s))
         begin = mid + 1;  
else if(equal(ra[mid],s))
         return mid;
else
         end = mid - 1;
   mid = (begin+end)/2;
}
}


int main() {
        Rational ra[10] = {{2,3},{-1,7},{6,3},{1,3},{2,5},{-7,5},
                        {5,2},{2,4},{-1,5},{2,6}};

        printRationalArray(ra,10);
        cout << endl;

        Rational r1 = makeRational(2,6);

        cout << "Result of linearSearch: " << linearSearch(ra, 10, r1) << endl;

        insertionSort(ra,10);

        cout << "Sorted: ";
        printRationalArray(ra,10);

        cout << endl;

        cout << "Result of binarySearch: " << binarySearch(ra, 10, r1) << endl;

        return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.