所以我正在用 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))
由于 GCD 具有结合性，因此
GCD(a,b,c,d)GCD(GCD(GCD(a,b),c),d)reducelen(numbers) > 2if 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) <= 2GCDreducelen(numbers) > 2您可以使用
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.
Python 3.9 引入了多参数版本的
math.gcdimport 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))
在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() 函数的更多信息。
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() 的关联属性来计算答案
尝试按如下方式调用
GCD()i = 0
temp = numbers[i]
for i in range(len(numbers)-1):
temp = GCD(numbers[i+1], temp)
我用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
从 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
问题之一是许多计算仅适用于大于 1 的数字。我修改了here找到的解决方案，以便它接受小于 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)
这是求 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)
正如您所说，您需要一个可以接受任意数量数字的程序 并打印这些数字的 HCF。
在此代码中，您给出用空格分隔的数字，然后单击 Enter 以获得 GCD
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)
希望有帮助
欧几里得算法扩展到多个数字。它收敛得很快，因为在每个循环中，剩下的值都变得小于最小初始值
def gcd(vals : list[int]):
while len(vals) > 1:
m = min(vals)
vals = list(x % m for x in vals if x % m) + [m]
return vals[0]