logo标签列表

欧几里得算法（多个数字的最大公约数）？

pythonmathgreatest-common-divisor
35

所以我正在用Python编写一个程序，以获取任意数量数字的最大公约数。

def GCD(numbers):

    if numbers[-1] == 0:
        return numbers[0]


    # i'm stuck here, this is wrong
    for i in range(len(numbers)-1):
        print GCD([numbers[i+1], numbers[i] % numbers[i+1]])


print GCD(30, 40, 36)

该函数接受一个数字列表。这应该打印出2。然而，我不明白如何递归使用算法以处理多个数字。有人可以解释一下吗？

更新后，仍然无法工作：

def GCD(numbers):

    if numbers[-1] == 0:
        return numbers[0]

    gcd = 0

    for i in range(len(numbers)):
        gcd = GCD([numbers[i+1], numbers[i] % numbers[i+1]])
        gcdtemp = GCD([gcd, numbers[i+2]])
        gcd = gcdtemp

    return gcd

好的，问题解决了

def GCD(a, b):

    if b == 0:
        return a
    else:
        return GCD(b, a % b)

然后使用reduce函数，就像这样

reduce(GCD, (30, 40, 36))
你需要注意的第一个问题是，你需要对列表进行排序，使最小的元素在最后面。 - Joran Beasley
不确定是否重复或仅相关：在Python中计算最大公约数 - Oleh Prypin
只是提醒一下，如果您可以使用迭代而不是递归来完成它，那么它可能会更快并且能够处理更大的值...在Python中，未定义深度的递归可能有点棘手。 - Joran Beasley
11个回答
41

由于最大公约数具有结合律，GCD(a,b,c,d)与GCD(GCD(GCD(a,b),c),d)相同。在这种情况下，Python的reduce函数将是将len(numbers) > 2的情况简化为简单的两个数字比较的好选择。代码看起来会像这样：

if len(numbers) > 2:
    return reduce(lambda x,y: GCD([x,y]), numbers)

Reduce对列表中的每个元素应用给定的函数，使得像这样

gcd = reduce(lambda x,y:GCD([x,y]),[a,b,c,d])

等同于做

gcd = GCD(a,b)
gcd = GCD(gcd,c)
gcd = GCD(gcd,d)

现在唯一要做的就是编写当len(numbers) <= 2的代码。 在reduce中仅传递两个参数到GCD可以确保您的函数最多递归一次（因为只有在最初调用时len(numbers) > 2），这样有额外的好处，即永远不会溢出堆栈。

28
您可以使用reduce：
>>> from fractions import gcd
>>> reduce(gcd,(30,40,60))
10

相当于；

>>> lis = (30,40,60,70)
>>> res = gcd(*lis[:2])  #get the gcd of first two numbers
>>> for x in lis[2:]:    #now iterate over the list starting from the 3rd element
...    res = gcd(res,x)

>>> res
10

reduce 函数的 help：

>>> reduce?
Type:       builtin_function_or_method
reduce(function, sequence[, initial]) -> value

Apply a function of two arguments cumulatively to the items of a sequence,
from left to right, so as to reduce the sequence to a single value.
For example, reduce(lambda x, y: x+y, [1, 2, 3, 4, 5]) calculates
((((1+2)+3)+4)+5).  If initial is present, it is placed before the items
of the sequence in the calculation, and serves as a default when the
sequence is empty.
2
虽然从技术上讲是正确的，并且绝对是我更喜欢的版本，但我认为这不会帮助他理解为什么它起作用，因为解决方案“隐藏”在reduce的定义中。 - Femaref
我不打算使用已经存在的gcd函数，我想要学习。 - Tetramputechture
9

Python 3.9 引入了多参数版本的math.gcd，因此您可以使用：

import math
math.gcd(30, 40, 36)

Python版本在3.5及以上，不高于3.8.x：

import functools
import math
functools.reduce(math.gcd, (30, 40, 36))

Python版本在3以上但小于3.5：

import fractions
import functools
functools.reduce(fractions.gcd, (30, 40, 36))
5

在PYTHON中找到两个以上数的LCM的解决方案如下：

#finding LCM (Least Common Multiple) of a series of numbers

def GCD(a, b):
    #Gives greatest common divisor using Euclid's Algorithm.
    while b:      
        a, b = b, a % b
    return a

def LCM(a, b):
    #gives lowest common multiple of two numbers
    return a * b // GCD(a, b)

def LCMM(*args):
    #gives LCM of a list of numbers passed as argument 
    return reduce(LCM, args)

在这里，我在range()函数的最后一个参数中添加了+1，因为该函数本身从零（0）开始到n-1。点击超链接了解有关range()函数的更多信息：

print ("LCM of numbers (1 to 5) : " + str(LCMM(*range(1, 5+1))))
print ("LCM of numbers (1 to 10) : " + str(LCMM(*range(1, 10+1))))
print (reduce(LCMM,(1,2,3,4,5)))

对于刚接触Python的人来说，可以通过以下链接详细了解reduce()函数。

3

GCD操作符是可交换和可结合的。这意味着：

gcd(a,b,c) = gcd(gcd(a,b),c) = gcd(a,gcd(b,c))

如果你知道如何对两个数字进行操作，那么你就可以对任意数量的数字进行操作。

要对两个数字进行操作，只需要实现欧几里得算法即可，该算法如下：

// Ensure a >= b >= 1, flip a and b if necessary
while b > 0
  t = a % b
  a = b
  b = t
end
return a

将该函数定义为euclid(a,b)。然后，您可以将gcd(nums)定义为：

if (len(nums) == 1)
  return nums[1]
else
  return euclid(nums[1], gcd(nums[:2]))

这里使用gcd()的结合律来计算答案。
1
那么为什么不利用这些知识呢？生成一对数的最大公约数，然后按照最大公约数的上述属性逐个处理列表中的数。 - Femaref
1
取第一个数和第二个数的最大公约数，将结果保存到一个变量中。获取列表中的下一个数字，将先前保存的结果与新值一起取得最大公约数。重复此过程直到列表结束。您的变量的值是所有数字的最大公约数。 - Femaref
@Femaref用你的解决方案更新了我的帖子，我不知道如何实现。 - Tetramputechture
0

正如您所说，您需要一个程序，可以接受任意数量的数字并打印出这些数字的最大公约数。

在此代码中，您可以用空格分隔数字，然后点击回车键以获取最大公约数。

num =list(map(int,input().split()))  #TAKES INPUT
def print_factors(x):          #MAKES LIST OF LISTS OF COMMON FACTROS OF INPUT
    list = [ i for i in range(1, x + 1) if x % i == 0 ]
    return list

p = [print_factors(numbers) for numbers in num]
result = set(p[0])        
for s in p[1:]:             #MAKES THE SET OF COMMON VALUES IN LIST OF LISTS
    result.intersection_update(s)

for values in result:
    values = values*values     #MULTIPLY ALL COMMON FACTORS TO FIND GCD
    values = values//(list(result)[-1])  
print('HCF',values)

希望有所帮助。
0

以下是我用Python解决这个问题的方法，希望能对你有所帮助。

def find_gcd(arr):
    if len(arr) <= 1:
        return arr
    else:
        for i in range(len(arr)-1):
            a = arr[i]
            b = arr[i+1]
            while b:
                a, b = b, a%b
            arr[i+1] = a
        return a
def main(array):
    print(find_gcd(array))

main(array=[8, 18, 22, 24]) # 2
main(array=[8, 24]) # 8
main(array=[5]) # [5]
main(array=[]) # []

我理解的一些动态：

例如：[8, 18] -> [18, 8] -> [8, 2] -> [2, 0]

其中18=8x+2=(2y)x+2=2z，其中z=xy+1

例如：[18, 22] -> [22, 18] -> [18, 4] -> [4, 2] -> [2, 0]

其中22=18w+4=(4x+2)w+4=((2y)x+2)w+2=2z

0
尝试按以下方式调用GCD()函数：
i = 0
temp = numbers[i]
for i in range(len(numbers)-1):
        temp = GCD(numbers[i+1], temp)
0

其中一个问题是许多计算只适用于大于1的数字。我修改了在这里找到的解决方案，使其接受小于1的数字。基本上，我们可以使用最小值重新调整数组，然后使用它来计算小于1的数字的GCD。

# GCD of more than two (or array) numbers - alows folating point numbers
# Function implements the Euclidian algorithm to find H.C.F. of two number 
def find_gcd(x, y): 
    while(y): 
        x, y = y, x % y 
    return x 
          
# Driver Code         
l_org = [60e-6, 20e-6, 30e-6]
min_val = min(l_org)
l = [item/min_val for item in l_org]
  
num1 = l[0] 
num2 = l[1] 
gcd = find_gcd(num1, num2) 
  
for i in range(2, len(l)): 
    gcd = find_gcd(gcd, l[i]) 
      
gcd = gcd * min_val
print(gcd)
0

这里是一种简单的方法来找到两个数字的最大公约数

a = int(input("Enter the value of first number:"))
b = int(input("Enter the value of second number:"))
c,d = a,b
while a!=0:
    b,a=a,b%a
print("GCD of ",c,"and",d,"is",b)
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接