【C语言】辗转相除法求最大公约数(详解)

辗转相除法求最大公约数

在这里插入图片描述

辗转相除法(又称欧几里德算法)是一种用于求解两个整数的最大公约数的方法。本文将使用C语言来实现辗转相除法,并对其原理进行解释。

辗转相除法的原理

辗转相除法的原理非常简单。假设有两个整数a和b,其中a > b。通过对a除以b求余数,得到余数r1。然后把b除以r1求余数,得到余数r2。如此重复,直到得到余数为0。那么这一系列的余数中的最后一个非零余数,就是a和b的最大公约数。即:

gcd(a, b) = gcd(b, r1) = gcd(r1, r2) = gcd(r2, r3) = … = gcd(r(n-1), rn) = gcd(rn, 0)

C语言实现

普通方法:

#include<stdio.h>
int main()
{
	int a = 0;
	int b = 0;
	int x = 0;

	scanf("%d %d", &a, &b);
	if (a < b)
	{
		//交换两个元素
		x = a;
		a = b;
		b = x;
	}
	else
	{
		//如果进入else,就是a>b,x就会为0,循环就会结束
		x = a % b;
		while (x != 0)
		{
			x = a % b;
			a = b;
			b = x;
		}
		printf("%d", a);
	}

	return 0;
}

下面是使用C语言实现辗转相除法求最大公约数的代码示例:

#include <stdio.h>

// 辗转相除法求最大公约数
int gcd(int a, int b) 
{
	if (b == 0)
	{
		return a;
	}
	else
	{
		return gcd(b, a % b);
	}
}

int main() {
	int a = 0;
	int b = 0;
	printf("请输入两个整数:");
	scanf("%d %d", &a, &b);
	int result = gcd(a, b);
	printf("最大公约数为:%d", result);
	return 0;
}

在上述代码中,我们使用递归的方式来实现辗转相除法。函数gcd接受两个整数a和b作为参数,如果b等于0,则返回a,否则递归调用自身,将b和a除以b取余数后的结果作为新的参数传入。直到b为0时,递归结束,返回a作为最大公约数。

main函数中,我们从用户输入获取两个整数a和b,然后调用gcd函数求得最大公约数,最后将结果输出。

运行结果

假设我们输入两个整数12和18,运行上述代码后,将得到如下输出:

请输入两个整数:12 18
最大公约数为:6

这说明12和18的最大公约数是6,验证了辗转相除法的正确性。

总结

辗转相除法是求解两个整数的最大公约数的一种常见算法。本文中,我们使用C语言实现了辗转相除法,并简要说明了其原理。通过实际的代码演示和运行结果,我们验证了辗转相除法的正确性。希望能够帮助到你理解该算法的实现过程。

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
分享
二维码
< <上一篇
下一篇>>