本文最后更新于：2023年4月15日 晚上
1 | 最大公约数和最小公倍数
1-1 | 求最大公约数(gcd)
方法: 辗转相除法
基本公式:
gcd(a, b) = gcd(b, a % b)
递归实现:
1
2
3
4
5
6
|
int gcd (int a, int b) {
return !b ? a : gcd(b, a % b);
}
|
迭代实现:
1
2
3
4
5
6
7
8
9
10
|
int gcd(int a, int b) {
int t;
while(b > 0) {
t = a % b;
a = b;
b = t;
}
return a;
}
|
1-2 | 求最小公倍数(lcm)
在求得d = gcd(a, b)后, lcm的表示很简单, 为:
ab / d
因为最小公倍数即
由于公因子在axb时乘了两次, 将重复的除一次即可
1
2
3
| int lcm (int a, int b) {
return a / gcd(a, b) * b;
}
|
2 | 分数的表示
利用一个结构体表示分数的分子和分母
1
2
3
| struct Fraction {
int up, down;
};
|
2-1 | 分数的化简
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| Fraction& reduction() {
if (down < 0) {
up = -up;
down = -down;
}
if (up == 0) {
down = 1;
}
else {
int d = gcd(abs(up), abs(down));
up /= d;
down /= d;
}
return *this;
}
|
2-2 | 分数的加减乘除
就硬算, 这里其实不严谨, 最好使用long long, 防止int在乘法时溢出
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| Fraction operator + (Fraction& b) {
Fraction ans;
ans.up = up * b.down + b.up * down;
ans.down = down * b.down;
return ans.reduction();
}
Fraction operator - (Fraction& b) {
Fraction ans;
ans.up = up * b.down - b.up * down;
ans.down = down * b.down;
return ans.reduction();
}
Fraction operator * (Fraction& b) {
Fraction ans;
ans.up = up * b.up;
ans.down = down * b.down;
return ans.reduction();
}
Fraction operator / (Fraction& b) {
Fraction ans;
ans.up = up * b.down;
ans.down = down * b.up;
return ans.reduction();
}
|
2-3 | 输出
规则如下
- 如果分母为1, 输出分子(一个整数)
- 如果是假分数, 以带分数的形式输出, 整数部分
up/down, 分子abs(up) % down, 分母down
- 如果是真分数, 直接输出
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| friend ostream & operator << (ostream& os, Fraction const& fr) {
Fraction r = fr;
r.reduction();
if (r.down == 1) os << r.up << endl;
else if (abs(r.up) > r.down) {
os << r.up / r.down << " " << abs(r.up) % r.down << "/" << r.down << endl;
}
else {
os << r.up << "/" << r.down << endl;
}
return os;
}
|
3 | 完整代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
|
#pragma GCC diagnostic ignored "-Wsign-conversion"
#pragma GCC diagnostic ignored "-Wsign-compare"
#include<bits/stdc++.h>
using namespace std;
int gcd(int a, int b) {
int t;
while(b > 0) {
t = a % b;
a = b;
b = t;
}
return a;
}
struct Fraction {
int up, down;
Fraction(int a, int b): up(a), down(b) {}
Fraction(){}
Fraction& reduction() {
if (down < 0) {
up = -up;
down = -down;
}
if (up == 0) {
down = 1;
} else {
int d = gcd(abs(up), abs(down));
up /= d;
down /= d;
}
return *this;
}
friend ostream & operator << (ostream& os, Fraction const& fr) {
Fraction r = fr;
r.reduction();
if (r.down == 1) os << r.up << endl;
else if (abs(r.up) > r.down) {
os << r.up / r.down << " " << abs(r.up) % r.down << "/" << r.down << endl;
}
else {
os << r.up << "/" << r.down << endl;
}
return os;
}
Fraction operator + (Fraction& b) {
Fraction ans;
ans.up = up * b.down + b.up * down;
ans.down = down * b.down;
return ans.reduction();
}
Fraction operator - (Fraction& b) {
Fraction ans;
ans.up = up * b.down - b.up * down;
ans.down = down * b.down;
return ans.reduction();
}
Fraction operator * (Fraction& b) {
Fraction ans;
ans.up = up * b.up;
ans.down = down * b.down;
return ans.reduction();
}
Fraction operator / (Fraction& b) {
Fraction ans;
ans.up = up * b.down;
ans.down = down * b.up;
return ans.reduction();
}
};
int main() {
Fraction f1(15, -12);
Fraction f2(3, 4);
cout << f1 << f2 << f1 + f2 << f1 * f2 << f1 / f2 << f1 - f2 << endl;
return 0;
}
|