社区首页 >专栏 >C语言小游戏——3、寻找大公约和小公倍的多种求法

C语言小游戏——3、寻找大公约和小公倍的多种求法

用户11015888

发布于 2024-03-11 11:53:31

8400

代码可运行

文章被收录于专栏：csdncsdn

运行总次数：0

代码可运行

一、最大公约数有四种求解：

什么是最大公约数呢？定义如下：如果数 a 能被数 b 整除，a 就叫做 b 的倍数，b 就叫做 a 的约数。几个整数中公有的约数，叫做这几个数的公约数；其中最大的一个，叫做这几个数的最大公约数。

例：12、18的公约数有1、2、3、6，其中最大的一个是6，则6是12与18的最大公约数。

法一：暴力求解

从上面举的例子我们可以分析，最大公约数一定不会大于两个数之间的最小数，最大也就是两个数的最小值，如20、40的最大公约数是20。

思路：

所以我们可以令两个数的最小值为最大公约数，然后我们再用两个数分别除去这两个数的最小值，如果都能整除，则就是最大公约数，否则就自减 1 再去除，判断是否能整除，不能就再自减1，一直循环下去直到找到都能被整除的数。（最坏的情况就是找到1停止）

比如上面的12、18这俩个数，这两个数的最小值是12，则定义变量tmp=12，然后判断12、18是否都能整除变量tmp。 tmp=12,不能被整除，自减1 tmp=11,不能被整除，自减1 tmp=10,不能被整除，自减1 tmp=9,不能被整除，自减1 tmp=8,不能被整除，自减1 ········ tmp=6,都能被12、18整除所以找到最大公约数了，12，18的最大公约数是6。

代码实现：

int main()
{
	int a = 0, b = 0;
	printf("请输入数字：");
	scanf("%d %d", &a, &b);
	int tmp = a < b ? a : b;//把两个数的最小值赋给tmp
	{
		while (1)
		{
			if (a % tmp == 0 && b % tmp == 0)
			{
				break;//找到最大公约数了，跳出循环
			}
			tmp--;//两个数都不能整除，自减1
		}
		printf("最大公约数为：%d", tmp);
	}
	return 0;
}

法二：更相减损法

更相减损法：也叫更相减损术，是出自《九章算术》的一种求最大公约数的算法，它原本是为约分而设计的，但它适用于任何需要求最大公约数的场合。

思路：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到它们两个数相等为止。则相等的两个数就是所求的最大公约数。

代码实现：

int main()
{
	int x = 0, y = 0;
	printf("请输入两个数字：");
	scanf("%d%d",&x,&y);
	while (x != y)  //两个数不相等就一直循环
	{
		if (x > y)
		{
			x = x - y;
		}
		else if (x < y)
		{
			y = y - x;
		}
	}
	//到这里则是两个数相等，取其任何一个就是最大公约数
	printf("最大公约数是：%d\n", x);
	return 0;
}

法三：辗转相除法

思路：用辗转相除法求几个数的最大公约数，可以先求出其中任意两个数的最大公约数，再求这个最大公约数与第三个数的最大公约数，依次求下去，直到最后一个数为止。最后所得的那个最大公约数，就是所有这些数的最大公约数。

代码实现：以三个数为例

int main()
 {
    int x = 0, y = 0, z = 0;
    int tmp = 0;
    // 输入三个整数
    printf("请输入三个数字：");
    scanf("%d %d %d", &x, &y, &z);
    // 计算第一个数和第二个数的最大公约数
    while (y != 0) 
    {
        tmp = x % y;
        x = y;
        y = tmp;
    }
    // 计算得到的最大公约数与第三个数的最大公约数作比较
    while (z != 0) 
    {
        tmp = x % z;
        x = z;
        z = tmp;
    }
    // 输出结果
    printf("三个数的最大公约数是：%d\n", x);
    return 0;
}

二、最小公倍数有两种求解：

几个数共有的倍数叫做这几个数的公倍数，其中除0以外最小的一个公倍数，叫做这几个数的最小公倍数。

举几个例子：12、18的最小公倍数是36

法一：暴力求解

通过上面举的例子我们可以发现最小公倍数一定大于或等于两个数的最大值。

思路：所以我们可以先找出两个数的最大值，然后赋值给变量tmp，然后用变量tmp分别除去两个数，如果能整除，则就是最小公倍数，否则变量tmp自加1，再分别除去两个数，判断是否能整除，一直循环下去，直到变量tmp都能够整除两个数。

比如12、18这两个数，这两个数的最大值是18，则定义变量tmp=18，然后判断变量tmp是否都能整除12、18。 tmp=18,不能整除12、18，自加1 tmp=19,不能整除12、18，自加1 tmp=20,不能整除12、18，自加1 tmp=21,不能整除12、18，自加1 tmp=22,不能整除12、18，自加1 ········ tmp=36,都能整除12、18 所以找到最小公倍数了，12，18的最小公倍数是36。

代码实现：

int main()
{
	int a = 0, b = 0;
	printf("请输入两个数字：");
	scanf("%d %d", &a, &b);
	int tmp = a > b ? a : b;
	while (1)
	{
		if (tmp % a == 0 && tmp % b == 0)
		{
			break;
		}
		tmp++;
	}
	printf("最小公倍数：%d", tmp);
	return 0;
}

法二：公式法

由于两个数的乘积等于这两个数的最大公约数与最小公倍数的积。所以，求两个数的最小公倍数，就可以先求出它们的最大公约数，然后用两个数的积除去最大公约数得出它们的最小公倍数。因此我们可以利用上面任何一种求最大公约数的方法来实现，先求最大公约数然后再求最小公倍数。

int Fun(int x, int y)
{
	if (x > y)
	{
		return Fun(y, x - y);  //再开辟一个Fun函数
	}
	else if (x < y)
	{
		return Fun(x, y - x);   //再开辟一个Fun函数
	}
	else   //找到相减到相等
	{
		return x;
	}
}
int main()
{
	int x = 0, y = 0;
	printf("请输入两个数字：");
	scanf("%d%d", &x, &y);
	int ret = Fun(x, y);
	printf("最大公约数是：%d\n", ret);
	printf("最小公倍数是：%d\n", x * y / ret);  //利用公式法，直接求出
	return 0;
}