October 23, 2023 1 min to read

椋鸟C语言笔记#9

辗转相除法与更相减损法求公约数

萌新的学习笔记,写错了恳请斧正。

辗转相除法求最大公约数

辗转相除法,又称欧几里得算法(Euclidean algorithm),是求取最大公约数的一种算法。辗转相除法首次出现于欧几里得的《几何原本》中的第 VII 卷,书中的命题 i 和命题 ii 所描述的就是辗转相除法,而在中国,辗转相除法最早出现在《九章算法》中。

其原理为:两个数的最大公约数等于其中较小的数字和二者之间余数的最大公约数

计算方式

要求 a、b 两数的最大公约数,先将其中较大的数除以较小的数,得到的余数再与除数比较大小。随后再用较大的数除以较小的数,得到的余数依旧与本次的除数比大小…… 直到某次的余数为 0,此时的除数即为最大公约数。

实现

int CommonDivisor(int a, int b)
{
	int c = 0;
 
	do
	{
		c = a % b;
		a = b;
		b = c;
	} while (c != 0);
 
	return a;
}

更相减损法求最大公约数

在《九章算术》里记载了更相减损法这种求最大公约数的算法,它原本是为约分而设计的,但它适用于任何需要求最大公约数的场合。

计算方式

要求 a、b 两数的最大公约数,先把公约数 2 提干净(同时除 2 直到不都是偶数)。然后用较大的数减去较小的数。再将减数与差比较,继续用较大的数减去较小的数…… 直到减数与差相等,这个数再乘上之前约去的 2(所有)就是最大公约数。

实现

int CommonDivisor(int a, int b)
{
	int c = 0;//余数
	int c2 = 0;//第一步除2的次数
	int r = 0;//交换数过渡区
	int cd = 0;//结果
 
	while (0 == a % 2 && 0 == b % 2)
	{
		a /= 2;
		b /= 2;
		c2++;
	}
 
	while (a != b)
	{
		if (a < b)
		{
			r = a;
			a = b;
			b = r;
		}
 
		c = a - b;
		a = b;
		b = c;
		c = 0;
	}
 
	cd = (int)pow(2, c2) * a;
 
	return cd;
}