Python 中最大公约数的代码

问题描述

a 和 b 的最大公约数 (GCD) 是将两者相除且无余数的最大数.

找到两个数的 GCD 的一种方法是欧几里德算法，该算法基于以下观察:如果 r 是 a 除以 的余数b，然后 gcd(a, b) = gcd(b, r).作为基本情况，我们可以使用 gcd(a, 0) = a.

编写一个名为 gcd 的函数，它接受参数 a 和 b 并返回它们的最大公约数.

解决方案

在标准库中.

>>>从分数导入 gcd>>>gcd(20,8)4

来自 Python 2.7 中 inspect 模块的源代码:

>>>打印inspect.getsource(gcd)def gcd(a, b):"""计算a和b的最大公约数.除非 b==0，否则结果将与 b 具有相同的符号(因此当b 除以它，结果为正)."""而 b:a, b = b, a%b返回一个

从 Python 3.5 开始，gcd 是在 math 模块中；fractions 中的那个已被弃用.此外，inspect.getsource 不再返回任一方法的解释性源代码.

The greatest common divisor (GCD) of a and b is the largest number that divides both of them with no remainder.

One way to find the GCD of two numbers is Euclid’s algorithm, which is based on the observation that if r is the remainder when a is divided by b, then gcd(a, b) = gcd(b, r). As a base case, we can use gcd(a, 0) = a.

Write a function called gcd that takes parameters a and b and returns their greatest common divisor.

解决方案

It's in the standard library.

>>> from fractions import gcd
>>> gcd(20,8)
4

Source code from the inspect module in Python 2.7:

>>> print inspect.getsource(gcd)
def gcd(a, b):
    """Calculate the Greatest Common Divisor of a and b.

    Unless b==0, the result will have the same sign as b (so that when
    b is divided by it, the result comes out positive).
    """
    while b:
        a, b = b, a%b
    return a

As of Python 3.5, gcd is in the math module; the one in fractions is deprecated. Moreover, inspect.getsource no longer returns explanatory source code for either method.

这篇关于Python 中最大公约数的代码的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！