题目描述:
Problem Description
给你2个分数,求他们的和,并要求和为最简形式。
Input
输入首先包含一个正整数T(T<=1000),表示有T组测试数据,然后是T行数据,每行包含四个正整数a,b,c,d(0<a,b,c,d<1000),表示两个分数a/b 和 c/d。
Output
对于每组测试数据,输出两个整数e和f,表示a/b + c/d的最简化结果是e/f,每组输出占一行。
Sample Input
2
1 2 1 3
4 3 2 3
Sample Output
5 6
2 1
看到此题,我的第一反应就是小学五年级的分母加减法,其中通分需要用两个分母的最小公倍数,而约分需要用分子和分母的最大公约数。此题就是模拟分母加减法的运算过程。一说到最大公约数,当然就得用辗转相除法了。
参考代码:
#include <iostream>
using namespace std;
int gcd(int b,int d) {
if (d == 0) {
return b;
}
else {
return gcd(d,b%d);
}
}
int lcm(int b,int d) {
int g = gcd(b,d);
int l = (b * d) / g;
return l;
}
void result(int a,int b,int c,int d) {
int fenmu,fenzi;
int g;
if (b == d) {
fenzi = a + c;
fenmu = b;
g = gcd(fenzi,fenmu);
fenzi /= g;
fenmu /= g;
}
else {
fenmu = lcm(b,d);
int fenzi1 = a * (fenmu / b);
int fenzi2 = c * (fenmu / d);
fenzi = fenzi1 + fenzi2;
g = gcd(fenzi,fenmu);
fenzi /= g;
fenmu /= g;
}
cout << fenzi << " " << fenmu << endl;
}
int main() {
int t;
int a,b,c,d;
cin >> t;
while (t--) {
cin >> a >> b >> c >> d;
result(a,b,c,d);
}
return 0;
}
分析完毕,欢迎交流。