我正在尝试使用欧几里得算法来计算两个数字的GCD。我正在关注此资源。
欧几里得算法说，我们必须继续从大数减去小数，直到两个数变为相同。而不是减去它们，而是在此资源中使用mod。
第一版
def gcd(a, b):
if a == 0 :
return b
return gcd(b%a, a)
第二版
def gcd(a, b):
if (b == 0):
return a
return gcd(b, (a % b))
在两个版本中，代码都不同，但结果却相同。我不知道这是如何工作的。有人可以向我解释吗？
的每个实现gcd都是另一个的镜像。
在第二个示例中，如果将a和b交换了变量，则将获得第一个版本。因此，这些gcd实现是等效的。唯一改变的事情，是秩序a和b。
该算法称为欧几里得除法。从维基百科：
在每一个步骤k，欧几里德算法计算一个商q ķ和余数r ķ从两个数r k-1个和r K-2
r k-2 = q k r k-1 + r k
其中r k为非负且严格小于r k-1的绝对值。作为欧几里得除法定义基础的定理可确保这样的商和余数始终存在并且是唯一的。
在欧几里得算法的原始版本中，商和余数通过重复减法找到；即r K-1是从r减去K-2 ，直到出现余数r ķ是小于r k-1个。之后，将r k和r k-1交换并重复该过程。欧几里得除法将两次交换之间的所有步骤减少为一个步骤，因此效率更高。而且，不需要商，因此可以通过取模运算来代替欧几里得除法，该运算仅给出余数。因此，欧几里得算法的迭代变得简单
r k = r k-2 mod r k-1
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句