31

所以我正在用 Python 编写一个程序来获取任意数量的数字的 GCD。

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))
4

10 回答 10

40

由于 GCD 是关联GCD(a,b,c,d)的，因此与GCD(GCD(GCD(a,b),c),d). 在这种情况下，Python 的reduce函数将是一个很好的候选者，可以将案例减少为len(numbers) > 2简单的 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)

现在唯一剩下的就是为 when 编写代码len(numbers) <= 2。仅将两个参数传递给GCDinreduce可确保您的函数最多递归一次（因为len(numbers) > 2仅在原始调用中），这具有永远不会溢出堆栈的额外好处。

于 2013-05-18T19:53:10.867 回答
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：_

>>> 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.
于 2013-05-18T19:27:33.797 回答
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()函数的信息。

于 2015-05-28T06:22:18.997 回答
3

GCD 算子是可交换的和结合的。这意味着

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

因此，一旦您知道如何处理 2 个数字，您就可以处理任何数字

要对两个数字执行此操作，您只需要实现欧几里得公式，这很简单：

// 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() 的关联属性来计算答案

于 2013-05-18T19:23:00.003 回答
3

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

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

3.5 <= Python <= 3.8.x：

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

3 <= Python < 3.5：

import fractions
import functools
functools.reduce(fractions.gcd, (30, 40, 36))
于 2020-05-13T16:08:31.857 回答
0

尝试GCD()如下调用，

i = 0
temp = numbers[i]
for i in range(len(numbers)-1):
        temp = GCD(numbers[i+1], temp)
于 2013-05-18T19:28:00.513 回答
0

这是查找 2 个数字的 GCD 的简单方法

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)
于 2020-10-24T05:35:36.170 回答
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

于 2018-07-24T02:06:16.490 回答
0

One of the issues is that many of the calculations only work with numbers greater than 1. I modified the solution found here so that it accepts numbers smaller than 1. Basically, we can re scale the array using the minimum value and then use that to calculate the GCD of numbers smaller than 1.

# 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)
于 2020-08-10T19:04:46.290 回答
0

从 python 3.9 beta 4 开始，它内置了对在数字列表中查找 gcd 的支持。

Python 3.9.0b4 (v3.9.0b4:69dec9c8d2, Jul  2 2020, 18:41:53)
[Clang 6.0 (clang-600.0.57)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> import math
>>> A = [30, 40, 36]
>>> print(math.gcd(*A))
2
于 2020-08-05T02:24:29.637 回答