1.题目要求求一串分数相加的结果。
2.每次读取一个数时,对其进行因式化简,再累加,需要用到欧几里德算法。
3.每次直接进行相加,分子先不对分母取模,在最后才进行取模,才把整数部分提取出来。
4.注意在计算gcd时,取bot和top的绝对值,避免算出来的gcd为-1,使得top和bot的符号翻转。
5.刚开始尝试使用scanf(“%d/%d”,&a,&b)进行分式的读取,结果在读取负数分式的时候出错,所以改为读取string,然后再进行解析。
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
AC代码:
//#include<string> //#include <iomanip> //#include<stack> //#include<unordered_set> //#include <sstream> //#include "func.h" //#include <list> #include<unordered_map> #include<set> #include<queue> #include<map> #include<vector> #include <algorithm> #include<stdio.h> #include<iostream> #include<string> #include<memory.h> #include<limits.h> #include<stack> using namespace std; /* 3 1/3 -1/6 1/8 3 0/1 0/2 0/3 3 -1/2 -3/2 -1/3 4 -1/2 -3/2 -1/3 1/3 4 1/2 3/2 -1/3 1/3 4 1/2 3/2 -1/2 -3/2 */ long long gcd(long long a, long long b) { return (b == 0 ? a : gcd(b, a%b)); } struct ratNode{ long long top; long long bot; ratNode(int a, int b) :top(a), bot(b){}; ratNode() :top(0), bot(1){}; }; void add2Num(long long&nowTop, long long&nowBot, long long nextTop, long long nextBot) { long long botGCD = gcd(nowBot, nextBot); long long a = nextBot / botGCD; long long b = nowBot / botGCD; long long top = nowTop*a + nextTop*b; long long bot = a*nowBot; long long GCD = gcd(labs(top), labs(bot));//注意取绝对值,避免算出来的gcd为-1,使得top和bot的符号翻转 nowTop = top / GCD; nowBot = bot / GCD; } void str2num(string str, long long&top, long long&bot) { bool sign = true; bool first = true; top = 0; bot = 0; for (int i = 0; i < str.size(); i++) { if (str[i] == '-') sign = false; else if (str[i] == '/') first = false; else if (first) top = top * 10 + str[i] - '0'; else if (!first) bot = bot * 10 + str[i] - '0'; } if (!sign) top = -top; } int main(void) { int n; cin >> n; vector<ratNode> rat(n); long long nowTop = 0; long long nowBot = 1; for (int i = 0; i < n; i++) { string str; cin >> str; str2num(str, rat[i].top, rat[i].bot); if (rat[i].top == 0) rat[i].bot = 1; int GCD = gcd(labs(rat[i].top), labs(rat[i].bot));//注意取绝对值,避免算出来的gcd为-1,使得top和bot的符号翻转 rat[i].top /= GCD; rat[i].bot /= GCD; add2Num(nowTop, nowBot, rat[i].top, rat[i].bot); } long long nowInt = nowTop / nowBot; nowTop = nowTop - (nowInt*nowBot); if (nowTop < 0 && nowInt!=0 ) nowTop = -nowTop; if (nowTop == 0 && nowInt==0) cout << "0" << endl; else if (nowTop == 0) cout << nowInt << endl; else if (nowInt == 0) cout << nowTop << "/" << nowBot << endl; else cout << nowInt << " " << nowTop << "/" << nowBot << endl; return 0; }