最大公约数算法 最大公约数最优算法

1、查找约数法. 先分别找出每个数的所有约数, 再从两个数的约数中找出公有的约数, 其中最大的一个就是 最大公约数. 例如,求 12 和 30 的最大公约数. 12 的约数有:1、2、3、4、6、12; 30 的约数有:1、2、3、5、6、10、15、30. 12 和 30 的公约数有:1、2、3、6,其中 6 就是 12 和 30 的最大公约数. 2 更相减损术 《九章算术》是中国古代的数学专著,其中的“更相减损术”可以用来求 两个数的最大公约数,即“可半者半之,不可半者,副置分母、子之数, 以少减多,更相减损,求其等也。以等数约之。” 翻译成现代语言如下: 第一步:任意给定两个正整数;判断它们是否都是偶数。若是,则用 2 约简;若不是则执行第二步。 第二步:以较大的数减较小的数,接着把所得的差与较小的数比较, 并以大数减小数。继续这个操作,直到所得的减数和差相等为止。 则第一步中约掉的若干个
最大公约数算法 最大公约数最优算法

2 与第二步中等数的乘积就是所求的最大公 约数。 其中所说的“等数”,就是最大公约数。求“等数”的办法是“更相 减损”法。

3、辗转相除法. 当两个数都较大时,采用辗转相除法比较方便.其方法是: 以小数除大数,如果能整除,那么小数就是所求的最大公约数.否则就用余数来除刚才 的除数;再用这新除法的余数去除刚才的余数.依此类推,直到一个除法能够整除,这时作 为除数的数就是所求的最大公约数. 例如:求 4453 和 5767 的最大公约数时,可作如下除法. 5767÷4453=1 余 1314 4453÷1314=3 余 511 1314÷511=2 余 292 511÷292=1 余 219 292÷219=1 余 73 219÷73=3 于是得知,5767 和 4453 的最大公约数是 73. 辗转相除法适用比较广,比短除法要好得多,它能保证求出任意两个数的最大公约数.

4、求差判定法. 如果两个数相差不大, 可以用大数减去小数, 所得的差与小数的最大公约数就是原来两 个数的最大公约数.例如:求 78 和 60 的最大公约数.78-60=18,18 和 60 的最大公约 数是 6,所以 78 和 60 的最大公约数是 6. 如果两个数相差较大,可以用大数减去小数的若干倍,一直减到差比小数小为止,差和小数 的最大公约数就是原来两数的最大公约数.例如:求 92 和 16 的最大公约数.92-16=76, 76-16=60,60-16=44,44-16=28,28-16=12,12 和 16 的最大公约数是 4,所 以 92 和 16 的最大公约数就是 4.

5、分解因式法. 先分别把两个数分解质因数, 再找出它们全部公有的质因数, 然后把这些公有质因数相 乘,得到的积就是这两个数的最大公约数. 例如:求 125 和 300 的最大公约数.因为 125=5×5×5,300=2×2×3×5×5,所以 125 和 300 的最大公约数是 5×5=25.

6、短除法. 为了简便, 将两个数的分解过程用同一个短除法来表示, 那么最大公约数就是所有除数 的乘积. 例如:求 180 和 324 的最大公约数. 因为: 5 和 9 互质,所以 180 和 324 的最大公约数是 4×9=36. 7、除法法. 当两个数中较小的数是质数时,可采用除法求解.即用较大的数除以较小的数,如果能 够整除,则较小的数是这两个数的最大公约数. 例如:求 19 和 152,13 和 273 的最大公约数.因为 152÷19=8,273÷13=21.(19 和 13 都是质数.)所以 19 和 152 的最大公约数是 19,13 和 273 的最大公约数是 13. 8、缩倍法. 如果两个数没有之间没有倍数关系,可以把较小的数依次除以 2、3、4……直到求得的 商是较大数的约数为止,这时的商就是两个数的最大公约数.例如:求 30 和 24 的最大公 约数.24÷4=6,6 是 30 的约数,所以 30 和 24 的最大公约数是 6.

  

爱华网本文地址 » http://www.413yy.cn/a/25101013/147333.html

更多阅读

哈夫曼树--带权最优二叉树 最优二叉树

最优二叉树概念1.树的路径长度 树的路径长度是从树根到树中每一结点的路径长度之和。在结点数目相同的二叉树中,完全二叉树的路径长度最短。2.树的带权路径长度(Weighted Path Length of Tree,简记为WPL)  结点的权:在一些应用中,赋予

2010年。狐狸版——最优护肤大赏,出炉喽 日本护肤品大赏

年年败新,年年更新。在护肤的道路上,狐狸喜欢追求新意。用过太多之后,每年的护肤品排行榜,新旧交替。2010年。狐狸版——最优护肤大赏,出炉喽一分钱一分货,是不变的硬道理但是却不是适合所有狐狸这样老百姓的护肤守则。每次出手昂

帕累托最优原则王燕秋 帕累托最优原则

帕累托改进是指一种变化,在没有使任何人境况变坏的前提下,使得至少一个人变得更好。而帕累托最优的状态就是不可能再有更多的帕累托改进的余地;换句话说,帕累托改进是达到帕累托最优的路径和方法。一方面,帕累托最优是指没有进行帕累托改

为什么选择改革开放 和平开放改革是日本的最优选择

     从长远看,和平开放改革是日本国家发展战略的最优选择,除此以外,都是次优选择。  首先,日本的资源缺乏决定了日本没有发动战争的坚实资本。一个国家在没有资源或资源匮乏的情况下,发动战争,要么是一开始就失败,要么是一开始可能

声明:《最大公约数算法 最大公约数最优算法》为网友扬尐分享!如侵犯到您的合法权益请联系我们删除