7363. Sum of fractions
Find the sum of
two proper fractions a / b and c / d. Present the result
as an irreducible fraction. If the result is an integer, then print only this integer.
Input. One line contains four positive integers a, b,
c, d – the numerators and denominators of the fractions. All numbers do
not exceed 1000.
Output. Print the
numerator and denominator of the resulting fraction, or an integer if the
result is a whole number.
|
Sample
input 1 |
Sample
output 1 |
|
1 2 1 4 |
3 4 |
|
|
|
|
Sample
input 2 |
Sample
output 2 |
|
3 4 1 4 |
1 |
SOLUTION
gcd
Algorithm analysis
It’s obvious that 
. We need to simplify the resulting fraction by their greatest common divisor.
Algorithm implementation
The gcd function returns the greatest common divisor
of the numbers a and b.
int gcd(int
a, int b)
{
return (!b) ?
a : gcd(b,a % b);
}
The main part of the program. Read the input data.
scanf("%d %d %d %d",&a,&b,&c,&d);
Compute the resulting fraction p / q.
p = a * d + c *
b;
q = b * d;
Compute the GCD of the numerator and denominator. Simplify the fraction.
g = gcd(p,q);
p /= g; q /= g;
Print the answer. If the answer is an integer (denominator q equals 1), then print only the numerator.
if (q == 1) printf("%d\n",p);
else printf("%d
%d\n",p,q);
Algorithm implementation
– class
#include <stdio.h>
class Fraction
{
private:
int a, b;
public:
Fraction(int
a = 1, int b = 1) : a(a), b(b) {};
void
ReadData(void)
{
scanf("%d
%d",&a,&b);
}
static int gcd(int a, int b)
{
return (!b)
? a : gcd(b,a % b);
}
Fraction operator+(const Fraction &f)
{
int p = this->a * f.b + f.a * this->b;
int q = this->b * f.b;
int d =
gcd(p,q);
return
Fraction(p/d,q/d);
}
void Print()
{
if (b == 1)
printf("%d\n",a);
else
printf("%d %d\n",a,b);
}
};
int main(void)
{
Fraction a, b, c;
a.ReadData();
b.ReadData();
c = a + b;
c.Print();
return 0;
}
Python implementation
Read the input data.
a, b, c, d = map(int, input().split())
Compute the resulting fraction p / q.
p = a * d + c * b
q = b * d
Compute the GCD of the numerator and denominator. Simplify the fraction.
g = math.gcd(p, q)
p //= g
q //= g
Print the answer. If the answer is an integer (denominator q equals 1), then print only the numerator.
if q == 1: print(p)
else: print(p, q)