admin管理员组

文章数量:821225

第三天:最大公因数和最小公倍数(c语言)

😇 😇 今天我们的主要内容是最大公因数和最小公倍数的求解方法

文章目录

  • 一、最大公因数
    • 🌳 (1)更相减损法
    • 🌳 (2)辗转相除法
    • 🌳 (3)穷举法
  • 二、最小公倍数

一、最大公因数

🌳 (1)更相减损法

🍒 🍒 更相减损法:以较大的数减较小的数,接着把所得的差与较小的数比较,并以大数减小数。继续这个操作,直到所得的减数和差相等为止

🌳 (2)辗转相除法

🍒 🍒 辗转相除法:欧几里得算法是用来求两个正整数最大公约数的算法。古希腊数学家欧几里得在其著作《The Elements》中最早描述了这种算法,所以被命名为欧几里得算法

🌻 🌻 假如需要求 1997 和 615 两个正整数的最大公约数,使用欧几里得算法:
1997 / 615 = 3 (余 152)
615 / 152 = 4(余7)
152 / 7 = 21(余5)
7 / 5 = 1 (余2)
5 / 2 = 2 (余1)
2 / 1 = 2 (余0)
则最大公约数为1

✈️ ✈️ 结果: 以除数和余数反复做除法运算,当余数为 0 时,取当前算式除数为最大公约数,所以就得出了 1997 和 615 的最大公约数 1。

🌳 (3)穷举法

🍒 🍒 穷举法:比如求a,b的最大公约数。a和b的最大公约数不可能比a和b中的较小者还大,否则一定不能整除它,因此,先找到a和b中的较小者t,然后从t开始逐次减1尝试每种可能,即检验t到1之间的所有整数,第一个满足公约条件的t,就是a和b的最大公约数。


注意❗️ ❗️

🌱 🌱 更相减损法和辗转相除法的主要区别在于前者所使用的运算是“减”,后者是“除”。从算法思想上看,两者并没有本质上的区别,但是在计算过程中,如果遇到一个数很大,另一个数比较小的情况,可能要进行很多次减法才能达到一次除法的效果,从而使得算法的时间复杂度退化为O(N),其中N是原先的两个数中较大的一个。相比之下,辗转相除法的时间复杂度稳定于O(logN)。

🌵 🌵 代码⬇️ ⬇️ :

#include<stdio.h>
#include<assert.h>//方法一:更相减损法
int modified_subtraction(int num1, int num2)
{assert(num1 > 0 && num2 > 0);while (num1 != num2){	if (num1 > num2){num1 -= num2;}else{num2 -= num1;}}return num1;
}//方法二:辗转相除法
int rolling_division(int num1, int num2)
{assert(num1 > 0 && num2 > 0);int tmp = num2;while (num1 % num2){tmp = num1 % num2;num1 = num2;num2 = tmp;}return tmp;
}//方法三:穷举法
int exhaustive(int num1, int num2)
{assert(num1 > 0 && num2 > 0);int min = 0;//选出较小的那个数字if (num1 > num2){min = num2;}else{min = num1;}for (int i = min; i > 0; i--){if (num1 % i == 0 && num2 % i == 0){return i;}}
}int main()
{int num1 = 0;int num2 = 0;scanf("%d%d", &num1, &num2);//方法一:更相减损法int ret1 = modified_subtraction(num1, num2);//方法二:辗转相除法int ret2 = rolling_division(num1, num2);//方法三:穷举法int ret3 = exhaustive(num1, num2);printf("更相减损法:->%d\n", ret1);printf("辗转相除法:->%d\n", ret2);printf("穷举法    :->%d\n", ret3);return 0;
}

二、最小公倍数

✏️ 在求解最小公倍数时,我们使用穷举法。

🌵 🌵 代码⬇️ ⬇️ :

#include<stdio.h>
#include<assert.h>int exhaustive(int num1, int num2)
{assert(num1 > 0 && num2 > 0);//求出较大值int i = num1;if (num1 > num2){i = num1;}else{i = num2;}//不停的自增,直到增大到取模为0时while (i % num1 != 0 || i % num2 != 0){i++;}return i;
}int main()
{int num1 = 0;int num2 = 0;scanf("%d%d", &num1, &num2);int ret = exhaustive(num1, num2);printf("num1和num2的最小公倍数为:->%d\n", ret);return 0;
}

😎 😎 今天的内容到这里就结束了,希望对小伙伴们能够有所帮助。

本文标签: 第三天最大公因数和最小公倍数(c语言)