「算法笔记」(一) 算法初步

本文最后更新于:2022年8月17日 上午

1 | 最大公约数和最小公倍数

1-1 | 求最大公约数(gcd)

方法: 辗转相除法

基本公式:

gcd(a, b) = gcd(b, a % b)

递归实现:

1
2
3
4
5
6
// 递归gcd
// 递归式: gcd(a, b) = gcd(b, a % b)
// 边界: gcd(a, 0) = a
int gcd (int a, int b) {
return !b ? a : gcd(b, a % b);
}

迭代实现:

1
2
3
4
5
6
7
8
9
10
// 迭代gcd
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; // 为了防止溢出, 先a / d再*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;
}
// 分子为0则分母为1
if (up == 0) {
down = 1;
}
// 分子不为0, 约分, 分子分母同时除以gcd
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
/**
* author: roccoshi
* created: 2021-01-19 15:06:03
*/
#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;
/*
-1 1/4
3/4
-1/2
-15/16
-1 2/3
-2
*/
return 0;
}

「算法笔记」(一) 算法初步
https://blog.roccoshi.top/posts/19514/
作者
RoccoShi
发布于
2021年1月19日
许可协议