求两个数的最大公约数的三种方法及C语言实现方式零、总述一、算法本体二、后言

84 阅读 0 评论 56 点赞

我是靠谱客的博主欢呼蜡烛，最近开发中收集的这篇文章主要介绍求两个数的最大公约数的三种方法及C语言实现方式零、总述一、算法本体二、后言，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

零、总述

本文主要讲述求两个数的最大公约数的三个算法及其C语言实现方式，本文需要了解最大公约数的定义(具体可自行百科或者或者其他途径了解)。

另外本文中C语言实现中使用的Max_sort函数是为了保证a一定是大于b，如果a<b，则将其交换，方便后续编码。代码如下：

int Max_sort(int *a, int *b)
{
	if (a == NULL || b == NULL) return -1;

	if (*a < *b)			//如果比较小则交换	
	{
		*a += *b;
		*b = *a - *b;
		*a -= *b;
	}
	return 0;
}

一、算法本体

1.辗转相除法

流程图如上，需要求的值为a和b的最大公约数，此算法简单来说是：将a和b相除，得到的余数赋值给c，并判断是否为0，如果不为0，则将b赋值给a，将c赋值给a，然后重复上述步骤直到c为0。a%b=c，算法直观来看就是这个数学算式的左移操作。

//辗转相除法
int ZZXC_Function(int a, int b)
{
	int c = 0;
	Max_sort(&a, &b);
	c = b;
	do
	{
		b = c;
		c = a%b;
		a = b;
	} while (c != 0);
	return b;
}

2.更相减损法

流程图如上，需要求的值为a和b的最大公约数，此算法简单来说是：将a和b减，得到的差值赋值给c，并判断是否为0，如果不为0，则将b赋值给a，将c赋值给a，然后重复上述步骤直到c为0。a-b=c，算法直观来看就是这个数学算式的左移操作，和辗转相除法实现方式很是接近，应该本源思路是一样的。

//更相减损法
int GXJS_Function(int a, int b)
{
	int c = 0;
	Max_sort(&a, &b);
	c = b;
	do
	{
		b = c;
		a>b ? c = a - b : c = b - a;
		a = b;
	} while (c != 0);
	return b;
}

3.穷举法

流程图如上，需要求的值为a和b的最大公约数，此算法穷举方式实现，简单粗暴，简单说就是比较a和b，将比较小的数赋值给c，将小于或等于c的每个值依次与a和b取模运算，如果刚好余数为0，即表示次数为a 和b的最大公因数，如果不是，则c值减1，重复上述步骤。如代码中所述，当数值比较大时，需要穷举的数也变多，效率明显下降。

//穷举法 当数值比较大时，明显效率下降
int QJ_Function(int a, int b)
{
	int c;
	Max_sort(&a, &b);
	c = b;

	while (a%c != 0 || b%c != 0)
	{
		c--;
	}
	return c;
}

二、后言

求最大公约数感觉上更多的是数学问题，使用数学模型用 C语言表达出来才得到上述算法，实际上求最大公约数还有质因数分解法和短除法等各种方法，只是在计算机语言实现方面，本文中三个方法更适合计算机的重复性而得以实现。所以算法可以不只上述几个，实现方式也因语言和逻辑而异，重要的是将这种二元的基本思维拓展到多元的思维中，在更加复杂的情况下解决相同的问题。欢迎各位指出谬误或者不足之处，相互学习~