Description

Given n positive fractions, add them one by one in the given order.

The running total starts as 0/1. After each fraction is added, print the total in lowest terms. The denomiantor is always positive, and the numerator and denominator are coprime.

When combining two fractions, use their least common denominator instead of directly multiplying their denominators.

The program uses four global variables:

• gcd_steps: the total number of times gcd has been called. Every call counts, including the outermost call and the final call where b=0. Its initial value is 0.
• total_n, total_d: the numerator and denominator of the current total. Their initial values are 0 and 1, respectively.

You need to complete the following three functions:

• gcd(a, b): returns the greatest common divisor of a and b, and keeps count of how many times gcd is called. It must be recursive.
• simplify(num, den): returns the simplified numerator / denominator. It must use gcd.
• add_fraction(p, q): adds p/q to the current total using the least common denominator, simplifies the result and prints the new total. It must use both gcd and simplify.

Hint

• When a fraction needs to be reduced to lowest terms, the greatest common divisor of its numerator and denominator is useful. The Euclidean algorithm provides a recursive way to compute it.
• Example of the Euclidean Algorithm:
  To find the gcd of 8 and 12

  8  = 12 * 0 + 8
  12 = 8 * 1 + 4 ➡️ gcd(8, 12) = 4
  8 = 4 * 2 + 0
  

  ​

Starter Code

Your program must define and use all the functions in the starter code and do not use gcd function provided by any library. Otherwise, you will receive no credit.

gcd_steps = 0
total_n = 0
total_d = 1

def gcd(a, b):
    # TODO
    pass

def simplify(num, den):
    # TODO
    pass

def add_fraction(p, q):
    # TODO
    pass

n = int(input())
for _ in range(n):
    p, q = map(int, input().split())
    add_fraction(p, q)
print(f"Total gcd steps: {gcd_steps}")

Input

The first line input one postive integer n , where1 ≤ n ≤ 10.
Each of the next n lines contains two positive integers p and q, representing the fraction p/q , where 1 ≤  p,q ≤ 20

Output

After each fraction is added, print the current total in lowest terms on one line format numerator / denominator

Finally, print out total gcd steps on the last line.

Sample Input  Download

Sample Output  Download

Discuss