PAT 1081 Rational Sum python解法
10269 ワード
1081 Rational Sum(20分)Given N rational numbers in the form numerator/denominator,you are supposed to calculate their sum.
Input Specification: Each input file contains one test case. Each case starts with a positive integer N (≤100), followed in the next line N rational numbers a1/b1 a2/b2 … where all the numerators and denominators are in the range of long int. If there is a negative number, then the sign must appear in front of the numerator.
Output Specification: For each test case, output the sum in the simplest form integer numerator/denominator where integer is the integer part of the sum, numerator < denominator, and the numerator and the denominator have no common factor. You must output only the fractional part if the integer part is 0.
Sample Input 1: 5 2/5 4/15 1/30 -2/60 8/3 Sample Output 1: 3 1/3 Sample Input 2: 2 4/3 2/3 Sample Output 2: 2 Sample Input 3: 3 1/3 -1/6 1/8 Sample Output 3: 7/24
いくつかの点数の和を求めて、結果は最も簡単な点数になります.
問題を解く構想:1.点数計算の主な問題は最大公約数と最小公倍数を求めることであり、最大公約数は転がり相除算法を用いることができ、最小公倍数は2数積/最大公倍数から得ることができる.2.二つの点数を加算するには、まず二つの分母の最小公倍数、すなわち通分を求め、加算してから和を簡略化し、分子分母の最大公約数を求める.3.複数の数の加算は、2つのスコアの加算をループして呼び出す関数です.4.最後に結果をフォーマット出力するには、分子が0、分母が1、分子が分母より大きく、分子が負の数である場合がいくつかの判断が必要である.
Input Specification: Each input file contains one test case. Each case starts with a positive integer N (≤100), followed in the next line N rational numbers a1/b1 a2/b2 … where all the numerators and denominators are in the range of long int. If there is a negative number, then the sign must appear in front of the numerator.
Output Specification: For each test case, output the sum in the simplest form integer numerator/denominator where integer is the integer part of the sum, numerator < denominator, and the numerator and the denominator have no common factor. You must output only the fractional part if the integer part is 0.
Sample Input 1: 5 2/5 4/15 1/30 -2/60 8/3 Sample Output 1: 3 1/3 Sample Input 2: 2 4/3 2/3 Sample Output 2: 2 Sample Input 3: 3 1/3 -1/6 1/8 Sample Output 3: 7/24
いくつかの点数の和を求めて、結果は最も簡単な点数になります.
問題を解く構想:1.点数計算の主な問題は最大公約数と最小公倍数を求めることであり、最大公約数は転がり相除算法を用いることができ、最小公倍数は2数積/最大公倍数から得ることができる.2.二つの点数を加算するには、まず二つの分母の最小公倍数、すなわち通分を求め、加算してから和を簡略化し、分子分母の最大公約数を求める.3.複数の数の加算は、2つのスコアの加算をループして呼び出す関数です.4.最後に結果をフォーマット出力するには、分子が0、分母が1、分子が分母より大きく、分子が負の数である場合がいくつかの判断が必要である.
n = int(input())
l = input().split()
#l = ['2/5', '4/15', '1/30', '-2/60', '8/3']
#l = ['4/3', '2/3']
#l = ['1/3', '-1/6', '1/8']
numerators = []
denominators = []
def gcd(n1,n2):#greatest common divisor
return gcd(n2, n1 % n2) if n2 else n1
# if n2:
# return gcd(n2, n1 % n2)
# else:
# return n1
def lcm(n1,n2):#lowest common multiple
return n1*n2//gcd(n1,n2)
def rational_sum(r1, r2):
n1, d1 = map(int,r1.split('/'))
n2, d2 = map(int,r2.split('/'))
d3 = lcm(d1, d2)
n3 = n1*(d3//d1) + n2*(d3//d2)
if n3:
gcd1 = gcd(abs(n3),d3)
d3 = d3//gcd1
n3 = n3//gcd1
return str(n3)+'/'+str(d3)
s = l[0]
for i in range(1,len(l)):
s = rational_sum(s,l[i])
#print(s)
n1, d1 = map(int,s.split('/'))
if d1 == 1:
print(n1)
elif n1 == 0:
print(n1)
elif abs(n1) > d1:
if n1>0:
print('%d %d/%d'%(n1//d1,n1%d1,d1))
else:
print('%d %d/%d'%((n1//d1)+1,abs(n1)%d1,d1))
else:
print(s)