forked from luox78/go-algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
/
divisor_test.go
78 lines (68 loc) · 1.28 KB
/
divisor_test.go
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
package recursion_test
import "testing"
func TestCommonDivisor(t *testing.T) {
// 找出最大公约数
// 5
t.Log(commonDivisor(25, 10))
// 5
t.Log(commonDivisor1(25, 10))
// 5
t.Log(commonDivisor2(25, 10))
}
// 辗转相除法, 最大公约数等于 min 和 max%min 余数之间的最大公约数
func commonDivisor(a, b int) int {
max := a
min := a
if b > max {
max = b
}
if b < min {
min = b
}
if max%min == 0 {
return min
}
return commonDivisor(min, max%min)
}
// 更相减损法, 最大公约数等于 max-min 和较小数 min 的最大公约数
func commonDivisor1(a, b int) int {
max := a
min := a
if b > max {
max = b
}
if b < min {
min = b
}
if max%min == 0 {
return min
}
return commonDivisor1(max-min, min)
}
func commonDivisor2(a, b int) int {
if a == b {
return a
}
// 当 a,b 为偶数时
if a&1 == 0 && b&1 == 0 {
return 2 * commonDivisor2(a>>1, b>>1)
}
// 当 a 为偶数, b 为奇数
if a&1 == 0 && b&1 != 0 {
return commonDivisor2(a>>1, b)
}
// 当 a 为奇数, b 为偶数
if a&1 != 0 && b&1 == 0 {
return commonDivisor2(a, b>>1)
}
// 当 a, b 为奇数, 先利用更相减损法运算, 此时 a-b 必然为偶数
max := a
min := a
if b > max {
max = b
}
if b < min {
min = b
}
return commonDivisor2(max-min, min)
}