- 浏览: 21239 次
- 性别:
- 来自: 南京
最新评论
最大公因数,又称最大公约数。是指 [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 640在C/C++语言编程过程中,一般的字符串搜索操作都是通过标准库 ... -
堆排序(Heap Sort)算法学习
2011-08-25 19:26 1057在程序设计相关领域, ... -
整数拆分问题的动态规划解法
2011-08-25 19:26 3034输入n,和k,问将n用1到k这k个数字进行拆分,有多少种拆分方 ... -
背包问题介绍与分析
2011-08-25 19:24 1001背包问题是在1978年由Merkel和Hellman提出的。它 ... -
求平方根sqrt()函数的底层算法效率问题
2011-08-25 19:23 1264我们平时经常会有一些数据运算的操作,需要调用sqrt,exp, ... -
面试中常见的一些算法问题
2011-08-25 19:22 672Problem 1 : Is it a loop ? ( ... -
各种排序算法的C++实现与性能比较
2011-08-25 19:21 890排序是计算机算法中非常重要的一项,而排序算法又有不少实现方法, ... -
背包问题之硬币找零问题
2011-08-25 19:19 1129设有6 种不同面值的硬 ... -
求能被1到20的数整除的最小正整数
2011-08-25 19:18 1337求能被1到20的数整除的最小正整数。最直觉的方法是求1到20这 ... -
买书折扣最优惠问题解法
2011-08-25 19:17 720题目:在节假日的时候 ... -
二叉树中的最近公共祖先问题
2011-08-25 19:16 1293题目:要求寻找二叉树中两个节点的最近的公共祖先,并将其返回。 ... -
判断一个整数是否是2的N次方
2011-08-25 19:04 1789题目:给定一个整数num,判断这个整数是否是2的N次方。比如, ... -
字符串逆序的算法汇总
2011-08-25 19:01 1034很早就准备写一个字符串系列的面试题,本来已经写好了,大概有十几 ... -
计算从1到N中1的出现次数
2011-08-25 18:59 573给定一个十进制整数N, ... -
KMP快速字符串查找算法
2011-08-25 18:57 938在C/C++语言编程过程中,一般的字符串搜索操作都是通过标准库 ... -
快速排序的递归实现
2011-08-25 18:54 728快速排序是对冒泡排序的一种改进。它的基本思想是:通过一次排序将 ... -
数字1亿里面有多少个1呢
2011-08-25 18:52 710乍看这题真够唬人的,群里看到这个题目后争先恐后的说看法。最简单 ... -
最大子序列、最长公共子串、最长公共子序列
2011-08-25 18:33 754最大子序列 最大子序列是要找出由数组成的一维数组中和最大的连续 ... -
一道关于男女比例的面试题
2011-08-25 16:56 1016阿里巴巴的一道面试题:说澳大利亚的父母喜欢女孩,如果生出来的第 ...
相关推荐
c语言编写分解质因数实现求解两个数的最大公约数
:给出不同方案求两个整数的最大公约数,并分析其时间性能
这是初学C语言时经常遇到的一个基础题,求解最大公约数,对于初学者来说,对于语法的掌握能够运用到实际问题中的一个很好的实例。
VB求最大公约数和最小公倍数,并进行简单的绘图。程序的其它功能:生成随机数组、生成红、绿、蓝可选的颜色渐变,并可选择是否是横纵切换,随机数组和曲线绘图是这个演示代码的重要部分,建议下载参考。
包含了:1.辗转相除法函数嵌套流程图2.辗转相除法函数递归流程图3.穷举法求最小公倍数流程图4.穷举法求最大公约数流程图5.更相减损术流程图
这是我自己做的ppt,关于递归法求解两数最大公约数的
本文实例讲述了Python基于辗转相除法求解最大公约数的方法。分享给大家供大家参考,具体如下: 之前总结过一次高德纳TAOCP中的最大公约数求解,其实课后题中的算法修改要求实现的是辗转相除法求解最大公约数。 这个...
求解多个数的最大公约数,其中in.txt放入要计算的n个数,并将n也放在最前方,随后,存放这n个整数,最后结果放在out.txt中。
本文实例讲述了Python实现的求解最大公约数算法。分享给大家供大家参考,具体如下: 使用Python求解两个数的最大公约数的时候用到了前面介绍的分解质因式。其实,我写分解质因式程序的时候就是因为发现在实现最大公...
此程序可以实现对两个整数求最大公约数,所用得法为递归算法。
主要介绍了使用Python求解最大公约数的实现方法,包括用Python表示欧几里得算法和Stein算法的求解原理,需要的朋友可以参考下
主要介绍了Java求解两个非负整数最大公约数算法,结合实例形式分析了java求解最大公约数的实现方法,并附带了循环法与递归法算法思路,需要的朋友可以参考下
求解最大公约数和最小公倍数的方法有很多种,如质因数分解法、短除法、辗转相除法(欧几里得算法)等。 在实际应用中,这两个概念广泛应用于数学各个分支以及日常生活中,如分数化简、时间与速度问题、工程设计等...
主要介绍了Python基于更相减损术实现求解最大公约数的方法,简单说明了更相减损术的概念、原理并结合Python实例形式分析了基于更相减损术实现求解最大公约数的相关操作技巧与注意事项,需要的朋友可以参考下
编一程序,求两个正整数m、n的最大公约数。 要求程序中有两个方法,分别使用循环和递归, 最后在主方法中两次求解并输出最大公约数。
今天在课堂上,老师讲解了如何求两个正整数c1和c2的最大公约数和最小公倍数。现在Hankson认为自己已经熟练地掌握了这些知识,他开始思考一个“求公约数”和“求公倍数”之类问题的“逆问题”,这个问题是这样的:已知...
c++例程:任意输入两个数,求此两个数的最大公约数