- 浏览: 21914 次
- 性别:
- 来自: 南京
最新评论
最大公因数,又称最大公约数。是指 [n(≧2)个自然数 a1, a2, ..., an] 的最大公因数。通常有两种表示方式:
它们的所有公因数中最大的那一个;
如果自然数 m 是这 n 个自然数的公因数,且这 n 个数的任意公因数都是 m 的因数,就称 m 是这 n 个数的最大用因数。通常国内的记述方式为 [(a1, a2, ..., an)] ,国际通用的记号为 [g.c.d.(a1, a2, ..., an)]。
欧几里得算法(Euclidean Algorithm)(Euclid‘s 算法)就是通常所说的求最大公因数的辗转相除法。算法描述如下:
如果 a 除以 b 能整除,则最大公约数是 b;
否则,最大公约数等于 b 和 a % b的公约数。
代码实现如下:
#include <stdio.h>
int Euclidean(int parA, int parB)
{
if (parB == 0) {
return parA;
} else {
return Euclidean(parB, parA % parB);
}
}
int main(void)
{
int intA, intB;
printf("Enter two number to calculate its GCD:\n");
scanf("%d %d", &intA, &intB);
printf("The GCD of %d and %d is %d\n", intA, intB, Euclidean(intA, intB));
return 0;
}
或者
#include <stdio.h>
int Euclidean(int parA, int parB)
{
return (!parB)?parA : Euclidean(parB, parA % parB);
}
int main(void)
{
int intA, intB;
printf("Enter two number to calculate its GCD:\n");
scanf("%d %d", &intA, &intB);
printf("The GCD of %d and %d is %d\n", intA, intB, Euclidean(intA, intB));
return 0;
}
它们的所有公因数中最大的那一个;
如果自然数 m 是这 n 个自然数的公因数,且这 n 个数的任意公因数都是 m 的因数,就称 m 是这 n 个数的最大用因数。通常国内的记述方式为 [(a1, a2, ..., an)] ,国际通用的记号为 [g.c.d.(a1, a2, ..., an)]。
欧几里得算法(Euclidean Algorithm)(Euclid‘s 算法)就是通常所说的求最大公因数的辗转相除法。算法描述如下:
如果 a 除以 b 能整除,则最大公约数是 b;
否则,最大公约数等于 b 和 a % b的公约数。
代码实现如下:
#include <stdio.h>
int Euclidean(int parA, int parB)
{
if (parB == 0) {
return parA;
} else {
return Euclidean(parB, parA % parB);
}
}
int main(void)
{
int intA, intB;
printf("Enter two number to calculate its GCD:\n");
scanf("%d %d", &intA, &intB);
printf("The GCD of %d and %d is %d\n", intA, intB, Euclidean(intA, intB));
return 0;
}
或者
#include <stdio.h>
int Euclidean(int parA, int parB)
{
return (!parB)?parA : Euclidean(parB, parA % parB);
}
int main(void)
{
int intA, intB;
printf("Enter two number to calculate its GCD:\n");
scanf("%d %d", &intA, &intB);
printf("The GCD of %d and %d is %d\n", intA, intB, Euclidean(intA, intB));
return 0;
}
发表评论
-
KMP快速字符串查找算法
2011-08-25 19:29 673在C/C++语言编程过程中,一般的字符串搜索操作都是通过标准库 ... -
堆排序(Heap Sort)算法学习
2011-08-25 19:26 1087在程序设计相关领域, ... -
整数拆分问题的动态规划解法
2011-08-25 19:26 3074输入n,和k,问将n用1到k这k个数字进行拆分,有多少种拆分方 ... -
背包问题介绍与分析
2011-08-25 19:24 1033背包问题是在1978年由Merkel和Hellman提出的。它 ... -
求平方根sqrt()函数的底层算法效率问题
2011-08-25 19:23 1293我们平时经常会有一些数据运算的操作,需要调用sqrt,exp, ... -
面试中常见的一些算法问题
2011-08-25 19:22 699Problem 1 : Is it a loop ? ( ... -
各种排序算法的C++实现与性能比较
2011-08-25 19:21 927排序是计算机算法中非常重要的一项,而排序算法又有不少实现方法, ... -
背包问题之硬币找零问题
2011-08-25 19:19 1177设有6 种不同面值的硬 ... -
求能被1到20的数整除的最小正整数
2011-08-25 19:18 1374求能被1到20的数整除的最小正整数。最直觉的方法是求1到20这 ... -
买书折扣最优惠问题解法
2011-08-25 19:17 756题目:在节假日的时候 ... -
二叉树中的最近公共祖先问题
2011-08-25 19:16 1325题目:要求寻找二叉树中两个节点的最近的公共祖先,并将其返回。 ... -
判断一个整数是否是2的N次方
2011-08-25 19:04 1827题目:给定一个整数num,判断这个整数是否是2的N次方。比如, ... -
字符串逆序的算法汇总
2011-08-25 19:01 1061很早就准备写一个字符串系列的面试题,本来已经写好了,大概有十几 ... -
计算从1到N中1的出现次数
2011-08-25 18:59 602给定一个十进制整数N, ... -
KMP快速字符串查找算法
2011-08-25 18:57 967在C/C++语言编程过程中,一般的字符串搜索操作都是通过标准库 ... -
快速排序的递归实现
2011-08-25 18:54 760快速排序是对冒泡排序的一种改进。它的基本思想是:通过一次排序将 ... -
数字1亿里面有多少个1呢
2011-08-25 18:52 745乍看这题真够唬人的,群里看到这个题目后争先恐后的说看法。最简单 ... -
最大子序列、最长公共子串、最长公共子序列
2011-08-25 18:33 794最大子序列 最大子序列是要找出由数组成的一维数组中和最大的连续 ... -
一道关于男女比例的面试题
2011-08-25 16:56 1042阿里巴巴的一道面试题:说澳大利亚的父母喜欢女孩,如果生出来的第 ...
相关推荐
c语言编写分解质因数实现求解两个数的最大公约数
在学习C语言的过程中,求解最大公约数(Greatest Common Divisor, GCD)是一个经典的入门级问题,它能帮助初学者更好地理解和应用C语言的基本语法。 最大公约数是指两个或多个非零整数的最大公共因数,它是这些整数...
在数学和程序设计领域,计算两个整数的最大公约数(Greatest Common Divisor, GCD)是一个常见且...通过本文的介绍和分析,相信读者能够更好地理解不同求解最大公约数的算法及其时间复杂度,并在实践中作出明智的选择。
在这个“VB源码:求解最大公约数和最小公倍数并绘图.rar”压缩包中,包含了一个VB程序,它不仅实现了计算两个或多个整数的最大公约数(Greatest Common Divisor, GCD)和最小公倍数(Least Common Multiple, LCM)的...
辗转相除法,又称欧几里得算法,是最古老的求解最大公约数的方法之一。其基本思想是:对于任意两个正整数a和b(a>b),它们的最大公约数等于a除以b的余数c与b之间的最大公约数。可以表示为GCD(a, b) = GCD(b, a % b)...
在计算机科学和编程领域,求解最大公约数(Greatest Common Divisor,GCD)是一项基本的任务,它在数学和算法设计中具有广泛的应用。本文将深入探讨三种不同的方法来计算两个整数的最大公约数:分解质因数法、连续...
对于多个数的最大公约数问题,我们可以采用扩展欧几里得算法或者递归的方法来解决。扩展欧几里得算法不仅能找到两个数的最大公约数,还能找到它们的一个线性组合,使得这个组合的结果等于最大公约数。对于三个或更...
此外,除了欧几里得算法,还有其他方法可以求解最大公约数,如辗转相除法(也叫更相减损法)、质因数分解法等。每种方法都有其适用场景和效率差异,理解这些算法的原理有助于我们在实际问题中做出最佳选择。 在实际...
最大公约数(Greatest Common ...通过理解这些知识点,你可以熟练地在C语言中实现最大公约数算法,并在实际问题中灵活运用。无论是基础的数据结构课程,还是高级的算法设计,最大公约数都是一个重要的基础知识点。
以下将详细介绍三种常见的求解最大公约数的算法:欧几里得法、循环测试法和质因数分解法。 1. **欧几里得法**: 欧几里得算法,又称为辗转相除法,是由古希腊数学家欧几里得提出的一种高效求解最大公约数的方法。...
求解最大公约数有多种方法,其中包括欧几里得算法,也被称为辗转相除法。这个算法基于这样一个原理:对于任何两个正整数a和b(假设a>b),它们的最大公约数等于a除以b的余数c和b之间的最大公约数。如果余数为0,则b...
在给定的C语言代码中,虽然实现了求解最大公约数和最小公倍数的基本功能,但采用的方法较为原始且效率较低。代码首先通过循环从大到小查找最大公约数,再从小到大查找最小公倍数。这种遍历的方式对于大数而言效率极...
通过上述分析,我们可以看到递归算法在解决数学问题,特别是最大公约数计算上的应用。递归不仅简化了代码,还体现了算法设计中的“分而治之”策略,使得原本复杂的问题得以优雅地解决。然而,递归算法也有其局限性,...
求解最大公约数的方法有很多,其中最常用的是辗转相除法(欧几里得算法)和更相减损法。 ##### 1. 辗转相除法(欧几里得算法) 辗转相除法是一种非常高效的求解最大公约数的方法。该算法的基本思想如下: - 设两...
压缩包中的"最大公约数(子VI).vi"可能是一个LabVIEW程序,利用了辗转相除法或其他方法实现求解最大公约数的功能。LabVIEW是一种图形化编程语言,它通过虚拟仪器(VI)来表示各种功能和算法。这个子VI可能作为模块...
除了辗转相除法之外,还可以使用更相减损法、质因数分解等方法求解最大公约数。 #### 4.2 C语言中的其他数学函数 C语言提供了丰富的数学函数,如求绝对值的`abs`、求平方根的`sqrt`等,这些函数可以帮助我们解决更...
在计算机科学领域,尤其是编程实践中,我们经常需要处理数学问题,其中包括初等数论中的概念,如最大公约数(Greatest Common Divisor, GCD)和最小公倍数(Least Common Multiple, LCM)。这两个概念在算法设计和...
无论是正数还是负数,甚至是非整数类型,只要能够进行取模运算,就可以采用这种方法求解最大公约数问题。在实际开发过程中,这种方法被广泛应用于各种数学计算、数据处理等场景,具有很高的实用价值。
本文将详细探讨N-S盒图在表示辗转相除法和穷举法求解最大公约数与最小公倍数中的应用。 首先,我们来看“辗转相除法”,也称为欧几里得算法。这是一种古老的计算最大公约数的方法,基于两个整数的最大公约数等于...