坑多，坑多
分为几个部分：
加工：将数字化为符合格式要求的形式
化简：使分母始终为正，分子分母化为最简（注意最大公约数为零的情况，否则可能编译无法通过，然后报浮点错误）
求最大公约数：递归利用辗转相除法求最大公约数
加法，减法，除法，乘法运算
辗转相除法
1 long long gcd(long long x, long long y) { 2 long long z = 0; 3 while (x % y) { 4 z = x % y; 5 x = y; 6 y = z; 7 } 8 return z; 9 }
注意：
- 测试点3：
- 用long long类型存储分子分母，题中只是说正确的输出中没有超过整形范围的整数，但乘法可能会出现超过整形范围的整数，以致测试点3报浮点错误
- 记得考虑分子分母绝对值相等的情况，否则会报答案错误
- 还要注意分子分母负负得正（保持分母始终为正数），否则会报答案错误
- 测试点2：注意用空间复杂度小的方法求最大公约数，不可以用枚举法，会超时
C/C++
1 #include<iostream> 2 #include<string> 3 4 using namespace std; 5 6 typedef struct { 7 /*假分数分子*/ 8 long long men; 9 /*真分数分子*/ 10 long long rmen; 11 /*分母*/ 12 long long den; 13 /*真数*/ 14 long long ant; 15 /*最终输出形式*/ 16 string s; 17 }Num; 18 19 long long gcd(long long x, long long y) { //求最大公约数 20 return y == 0 ? x : gcd(y, x % y); 21 } 22 23 int simplify(Num* n) { //化简 24 if (n->den < 0)n->men = -(n->men), n->den = -(n->den); //保持分母始终为正 25 long long rem = gcd(abs(n->men), abs(n->den)); 26 if (rem == 0) return 0; //出现最大公约数为零的情况（没有最大公约数），直接返回 27 n->men /= rem; 28 n->den /= rem; 29 return 0; 30 } 31 32 int process(Num* n) { 33 if (n->den == 0) { //分母为零的情况 34 n->s = "Inf"; 35 return 0; 36 } 37 simplify(n); 38 n->ant = 0; 39 if ((long long)abs(n->men) >= n->den) { //假分数(注意分子分母相等的情况，否则测试点3过不了) 40 if (n->men % n->den == 0) { //可以除尽，化为整数 41 n->ant = n->men / n->den; 42 n->s = to_string(n->ant); 43 } 44 else{ //化为带分数 45 n->ant = n->men / n->den; 46 n->rmen = (long long)abs(n->men) - ((long long)abs(n->ant) * n->den); 47 n->s = to_string(n->ant) + ' ' + to_string(n->rmen) + '/' + to_string(n->den); 48 } 49 } 50 else if (n->men == 0) { //分子为零 51 n->s = "0"; 52 } 53 else { //真分数 54 n->s = to_string(n->men) + '/' + to_string(n->den); 55 } //负数带符号 56 if (n->men < 0 || n->ant < 0)n->s = '(' + n->s + ')'; 57 return 0; 58 } 59 60 void plusnum(Num* x, Num* y, Num* z) { //加法 61 z->den = x->den * y->den; 62 z->men = x->men * y->den + y->men * x->den; 63 process(z); 64 } 65 66 void minusnum(Num* x, Num* y, Num* z) { //减法 67 z->den = x->den * y->den; 68 z->men = x->men * y->den - y->men * x->den; 69 process(z); 70 } 71 72 void multiplynum(Num* x, Num* y, Num* z) { //乘法 73 z->men = x->men * y->men; 74 z->den = x->den * y->den; 75 process(z); 76 } 77 78 void dividenum(Num* x, Num* y, Num* z) { //除法 79 z->men = x->men * y->den; 80 z->den = x->den * y->men; 81 process(z); 82 } 83 84 int main() { 85 Num a, b, ret; 86 scanf_s("%lld/%lld %lld/%lld", &a.men, &a.den, &b.men, &b.den); //vs为scanf_s 87 process(&a); 88 process(&b); 89 plusnum(&a, &b, &ret); 90 cout << a.s << " + " << b.s << " = " << ret.s << endl; 91 minusnum(&a, &b, &ret); 92 cout << a.s << " - " << b.s << " = " << ret.s << endl; 93 multiplynum(&a, &b, &ret); 94 cout << a.s << " * " << b.s << " = " << ret.s << endl; 95 dividenum(&a, &b, &ret); 96 cout << a.s << " / " << b.s << " = " << ret.s << endl; 97 return 0; 98 }
哈哈，还蛮快的
原文链接: https://www.cnblogs.com/Godsheep/p/13363914.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/369590
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
