、接连算法的方法进称四种,分别是什么,斜有么优缺点?

发布网友发布时间：2022-04-22 19:17

共1个回答

热心网友时间：2023-10-25 23:32

接连算法的方法进称四种如下。
1、辗转相除法（又名欧几里德算法）。简称*，用于计算两个整数的最大公约数。
2、穷举法（也称枚举法）。求两个正整数的最大公约数的解题步骤：从两个数中较小数开始由大到小列举，直到找到公约数立即中断列举，得到的公约数便是最大公约数。
3、更相减损法(又名辗转相减法)。第一步任意给定两个正整数。判断它们是否都是偶数。若是，则用2约简。若不是则执行第二步。第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。其中所说的等数，就是最大公约数。求等数的办法是更相减损法。更相减损法也叫等值算。
4、Stein算法。是计算两个数最大公约数的传统算法，无论从理论还是从实际效率上都是很好的。却有一个致命的缺陷，这个缺陷在素数比较小的时候是感觉不到的，只有在大素数时才会显现出来：实际应用中的整数很少会超过64位（当然现在已经允许128位了），对于这样的整数，计算两个数之间的模是很简单的。