c语言实现求最大公约数的三种方法是什么,C语言四种方法求最大公约数

c语言实现求最大公约数的三种方法是什么,C语言四种方法求最大公约数,C语言实现求最大公约数的三种方法

最大公因数,又称最大公约数和最大公约数,是指两个或两个以上整数的最大公约数。本文将介绍三种求两个正整数的最大公约数的方法,有需要的可以参考。

目录

题目描述问题解析代码实现方法1:穷举法2:辗转除法3:多相减损法

题目描述

求任意两个正整数的最大公约数

问题分析

最大公因数,又称最大公约数和最大公约数,是指两个或两个以上整数的最大公约数。A,B的最大公约数记为(A,B)。同样,A,B,C的最大公约数记为(A,B,C),多个整数的最大公约数有相同的标记。求最大公约数的方法有很多,如质因数分解法、短除法、倒除法、多相损法等。最大公约数对应的概念是最小公倍数,A和B的最小公倍数记为[a,b]。

3354百度百科

有很多方法可以找到最大公约数。本文我将用穷举法、逐次除法、多相损法三种方法求两个正整数的最大公因式(最大公因式)。

代码实现

方法一:穷举法

穷举法(枚举法)是最简单、最直观的方法。

具体步骤如下:首先求两个数的最小值min(最大公约数必须小于等于最小值min),然后从最小值min开始遍历(循环结束条件为i 0)。如果一个数是两个整数的因子,使用break退出遍历(退出循环)。此时遍历值I就是两个正整数的最大公约数。

#包含stdio.h

/**

* @brief求两个正整数的最大公因数(穷举法)

* @param num1第一个正整数

* @param num2秒正整数

* @返回最大公因数

*/

int Get _ Max _ Comm _ Divisor(int num 1,int num2)

{

int I=0;

//获取两个整数的最小值

int min=num1 num2?num 1:num 2;

//以降序从两个数字中的最小值开始遍历。

for(I=min;I 0;我-)

{

//i是num1和num2的公倍数。

if(num1 % i==0 num2 % i==0)

打破;

}

返回I;

}

int main()

{

int num1=0,num 2=0;

Puts('请输入两个正整数。');

scanf('%d%d ',num1,num 2);

Printf('最大公约数为% d. \ n ',get _ max _ comm _ divider (num1,num 2));

返回0;

}

运行结果

方法二:辗转相除法

相除,又称欧几里德算法,是指用来计算两个非负整数A,b的最大公约数,应用领域包括数学和计算机。公式gcd(a,b)=gcd(b,a mod b)。

欧几里德算法用于求两个正整数的最大公约数。古希腊数学家欧几里德在他的著作《The Elements》中首次描述了这种算法,因此将其命名为欧几里德算法。

扩展欧几里德算法可用于RSA加密等领域。

示例:

如果需要两个正整数1997和615的最大公约数,则使用欧几里德算法,具体如下:

1997/615=3(剩余152人)

65/152=4(剩余7)

12/7=21(剩余5)

7/5=1(剩余2)

5/2=2(剩余1)

2/1=2(剩余0)

到目前为止,最大公约数是1。

用除数和余数重复除法运算。余数为0时,取当前公式的除数为最大公约数,则1997和615的最大公约数为1。

3354百度百科

我觉得这个小算法特别神奇,但是不想深入研究(为什么翻来覆去的除法能找到最大公因式?).如果你想证明的话,你可以简单的自己证明,那我就选择背下来好了,呵呵。

虽然算法不太好理解,但是实现过程并不难。根据分而治之的概念,可以转化为代码。

具体步骤:首先求两个数num1和num2的余数余数。然后将num2赋给num1,设上一个余数的除数num2为下一个余数的被除数。同时将当前余数余数作为下一个余数的除数。这样做直到余数为0,此时除数num2是我们需要的最大公因数。

一开始两个数不需要大小不同,因为如果num1小于num2,那么余数结果还是num1,这样下次余数就变成num2% num1,也就是左边大的值作为被除数)。

#包含stdio.h

/**

* @brief求两个正整数的最大公因数(辗转除法)

* @param num1第一个正整数

* @param num2秒正整数

* @返回最大公因数

*/

int Get _ Max _ Comm _ Divisor(int num 1,int num2)

{

int remainder=num 1% num 2;//余数

而(余数!=0)

{

num1=num2//更新股息

num2=余数;//更新除数

余数=num 1% num 2;//更新余数

}

返回num2//最后的除数是最大公因数。

}

int main()

{

int num1=0,num 2=0;

Puts('请输入两个正整数。');

scanf('%d%d ',num1,num 2);

Printf('最大公约数为% d. \ n ',get _ max _ comm _ divider (num1,num 2));

返回0;

}

运行结果

方法三:更相减损法

055-79000是我国古代的数学专著,其中的“多相损”可以用来求两个数的最大公约数。原文是:

可以对半分,不可以对半分,设定分母,孩子的数量,才能以少减多,甚至更多的互相减损。让我们以相等的数量预约。

白话文翻译:

(如果需要近似分数,那么)如果能减半,就减半(就是用2近似分数)。如果不能减半,那就把分母和分子比较,把小数从大数中减去,互相相减,直到相减等于差,用这个相等的数来近似分数。

3354百度百科

还有一种方法叫折腾减法,好像和多相减法一样,至少原理是一样的。

减法(求最大公约数),即尼各马科斯法,其特点是通过一系列减法来求最大公约数。比如:两个自然数,35和14,从大数中减去小数,(35,14)-(21,14)-(7,14)。此时7小于14。你要把14换成被减数,也就是(14,7)-(7,7),再相减。

3354百度百科

我对刚才的分裂感到惊讶。没想到是减法。不过还是老规矩,只是用代码实现这个方法而不是证明。

与逆序除法不同,多相损法需要考虑两个数的大小。只有大的数可以作为被减数,小的数可以作为被减数。

实现步骤:先求两个正整数num1和num2的差diff,然后将num2赋给num1,让上一次减法中num2的减法为下一次减法的被减数。同时将当前差diff作为下一次减法的减数。这样做直到差值为0,此时除数num2是我们需要的最大公因数。

#包含stdio.h

/**

* @brief求两个正整数的最大公因数(多相损法)

* @param num1第一个正整数

* @param num2秒正整数

* @返回最大公因数

*/

int Get _ Max _ Comm _ Divisor(int num 1,int num2)

{

//两个数相减的结果(取正值)

int diff=num1 num2?num 1-num 2:num 2-num 1;

while(diff!=0)

{

num1=num2//更新被减数

num2=diff//更新减数分裂

diff=num1 num2?num1 - num2\

:num 2-num 1;//更新两个数相减的结果(取正值)

}

返回num2//最后还原是最大公因数。

}

int main()

{

int num1=0,num 2=0;

Puts('请输入两个正整数。');

scanf('%d%d ',num1,num 2);

Printf('最大公约数为% d. \ n ',get _ max _ comm _ divider (num1,num 2));

返回0;

}

运行结果

至于哪种方法效率更高,有兴趣的朋友可以计算一下。我只知道穷举是效率最低的。

以上是C语言中求最大公约数的三种方法的细节。更多关于C语言求最大公约数的信息,请关注我们的其他相关文章!

郑重声明:本文由网友发布,不代表盛行IT的观点,版权归原作者所有,仅为传播更多信息之目的,如有侵权请联系,我们将第一时间修改或删除,多谢。

相关文章阅读

  • c语言调用退出函数 c语言退出整个程序怎么写
  • c语言中怎么给函数初始化 c语言的初始化语句
  • c语言编写函数计算平均值 c语言求平均函数
  • 详解c语言中的字符串数组是什么,详解c语言中的字符串数组结构,详解C语言中的字符串数组
  • 表达式求值c++实现,c语言实现表达式求值
  • 看懂c语言基本语法,C语言详解,C语言的基本语法详解
  • 用c语言实现快速排序算法,排序算法设计与实现快速排序C语言,C语言实现快速排序算法实例
  • 深入解析c语言中函数指针的定义与使用方法,深入解析c语言中函数指针的定义与使用情况,深入解析C语言中函数指针的定义与使用
  • 描述E-R图,E-R图举例,关于C语言中E-R图的详解
  • 折半查找法C语言,折半查找算法(算法设计题)
  • 折半查找法C语言,c语言折半法查找数据,C语言实现折半查找法(二分法)
  • 扫雷小游戏c++代码设计,c语言扫雷游戏源代码,C语言实现扫雷小游戏详细代码
  • 怎样统计程序代码行数,C语言统计行数,C#程序员统计自己的代码行数
  • 基于c语言的贪吃蛇游戏程序设计,用c语言编写贪吃蛇游戏程序,C语言实现简单的贪吃蛇游戏
  • 图的两种遍历算法,图的遍历算法代码c语言,Python算法之图的遍历
  • 留言与评论(共有 条评论)
       
    验证码: