再看求最大公约数的算法
再看求最大公约数的算法
由渐入深学习大公约数的算法,从最简单的遍历循环的方法到通过移位运算大幅提高大数情况下的计算效率
实例代码均为kotlin
遍历计算
思路
都用遍历了… 还要什么思路
代码实现
优势
思路简洁
劣势
效率十分低下,和其它方法花费的时间已不在一个数量级中
辗转相除法
辗转相除法:又名欧几里德算法（Euclidean algorithm）,是求最大公约数的一种方法.辗转相除法可以算得上是最早的算法
思路
用较小数除较大数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。
如果我们计算49和21的最大公约数
- 35 / 21 = 1…14 用较大的数除以较小的数,得到的余数为14
- 21 / 14 = 1…7 用上一步中的被除数除以上一步计算中得到的余数为7
- 14 / 7 = 2 重复上述的过程,直到计算的结果中不存在余数.此时除数就是我们需要的最大公约数
代码实现
优势
当数据较小的时候性能最好
劣势
需要用到取余运算.现阶段的硬件中,整形多为64位,如果需要计算的数据多余硬件的整形位数就需要使用类似于多位数除法手算过程中的试商法,过程复杂而且需要消耗更多的时间
更相减损术方法
更相减损术是出自《九章算术》的一种求最大公约数的算法,它原本是为约分而设计的,但它适用于任何需要求最大公约数的场合.
思路
原文是：
可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。
如果是偶数则先减半,不是偶数的话用大数减小数,用得到的差和上一步中较小的数再次相减,知道减数和差相等位置,最后相等的数字就是得到最大公约数.
但是此方法中如果两个数都是偶数的情况下最后的得到的结果需要在加一倍,下面实现中先不涉及取半操作,只进行互减操作
如果我们计算49和21的最大公约数
- 49 - 21 = 28 49和21都不是偶数,直接用较大的数减去较小的数
- 28 - 21 = 7 将上一步中得到的差和上一步中较小的数再次相减(用交大数减去较小数)
- 21 - 7 = 14
- 14 - 7 = 7
- 7 - 7 = 0 重复以上步骤 直至差和较小的数相等,此时相等的数就是需要的最大公约数
代码实现
优势
在计算大数的情况下依旧可以保持较快的速度
劣势
因为要不断互减,在两个数较为接近的时候需要的系统资源较大
Stein算法
Stein算法是一种计算两个数最大公约数的算法，是针对欧几里德算法在对大整数进行运算时，需要试商导致增加运算时间的缺陷而提出的改进算法。
思路
相对于辗转想相除法,相减损术方法和Stein算法更为接近.
如果两个数都是偶数则想将其除以2 最后的结果再乘以2,如果其中的一个是偶数,则将其为偶数的数除以2,如果两个均为奇数,则用较大的数再减去较小的数,得到的差必为偶数,再重复上述过程,直到其中较小的数和查相同,此时相同的数就是需要得到的最大公约数
如果我们计算49和21的最大公约数
- 49 - 21 = 28 49及21均为奇数,则用较大的数减去较小的数
- 28 / 2 = 14 其中得到的差为偶数,将偶数除以2
- 14 / 2 = 7 其中得到的差为偶数,将偶数除以2
- 7 - 7 = 0 重复上述过程 知道差和上一步中的较小数相同 相同的值就是最大公约数
代码实现
优势
只是用了移位运算及加减法
在计算大数的过程中性能最佳
劣势
数据较小的时候,花费的时间相对辗转相除法及更相减损术略多,不适合较小的数据的计算
代码可读性基本没有…
