Polar Snow Documentation

花有重开日 人无再少年

go语言实现最大公约数算法

发表于 分类于 ， Disqus：

最大公约数简介

最大公约数(GCD/Greatest Common Divisor)指几个整数中共有约数中最大的一个

欧几里德算法

欧几里德算法又称辗转相除法, 该算法用于计算两个整数的最大公约数. 定理如下:

1
gcd(a,b) = gcd(b,a mod b)

意思就是说: a和b的最大公约数 = b和a➗b的余数的最大公约数

  • 当a➗b的余数为0时, 最大公约数为b
  • 当a➗b的余数不为0时, 则将a=b, b=a➗b的余数, 递归运算, 直到余数为0

具体证明的过程在此不再赘述, 如有兴趣可以自行谷歌一下, 下面直接给出基于go语言的实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
package main

import "fmt"

func gcd(a,b int) int {
	if b == 0 {
		return a
	}
	return gcd(b, a % b)
}

func main() {
	fmt.Println(gcd(5, 10))
}

运行结果: 

1
5

解析:

第一次调用:

调用gcd(5, 10)则a=5, b=10, 进入函数后判断if b == 0, 此时b=10, 判断条件为假, 递归调用gcd(b, a % b), 此时实际值为 gcd(10, 5 % 10), 5与10计算取余商0, 余5, 则实际调用参数为gcd(10, 5)

第二次调用:
调用gcd(10, 5)则a=10, b=5, 进入函数后判断if b == 0, 此时b=5, 判断条件为假, 递归调用gcd(b, a % b), 此时实际值为 gcd(5, 10 % 5), 10与5计算取余商2, 余0, 则实际调用参数为gcd(5, 0)

第三次调用:
调用gcd(5, 0)则a=5, b=0, 进入函数后判断if b == 0, 此时b=0, 判断条件为真, 直接返回a 此时a即为两个数的最大公约数

多个数求最大公约数

实现思路: 先求出头两个数的最大公约数, 再拿计算出的最大公约数依次与后面所有的数求最大公约数

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
package main

import "fmt"

func gcd(a,b int) int {
	if b == 0 {
		return a
	}
	return gcd(b, a % b)
}

func GetGcd(n []int) int {
	// 先取得Slice中的第一个数, 并假设第一个数为最大公约数
	g := n[0]
	// 依次与Slice中的每个数字求最大公约数
	// 这里i=1, 因为第0个数字已经取出并假设为最大公约数
	for i:=1; i<len(n)-1; i++ {
		oldGcd := g
		// 使用两个数字比较的最大公约数函数进行计算, 得出当前两个数字的最大公约数
		// 循环开始后, 依次将当前最大公约数与后面的数字一一进行运算, 求最大公约数
		g = gcd(g, n[i])
		fmt.Printf("第%d次运算, 当前最大公约数为%d, 与%d运算得出的新最大公约数为: %d \n", i, oldGcd, n[i], g)
	}
	return g
}

func main() {
	nums := []int{4,4,6,2,8,10}
	fmt.Printf("运算结果: \n\t数列: %v 的最大公约数为: %d", nums, GetGcd(nums))
}

运行结果:

1
2
3
4
5
6
第1次运算, 当前最大公约数为4, 与4运算得出的新最大公约数为: 4 
第2次运算, 当前最大公约数为4, 与6运算得出的新最大公约数为: 2 
第3次运算, 当前最大公约数为2, 与2运算得出的新最大公约数为: 2 
第4次运算, 当前最大公约数为2, 与8运算得出的新最大公约数为: 2 
运算结果: 
        数列: [4 4 6 2 8 10] 的最大公约数为: 2
相关文章