Thuật toán Euclide (GCD) với nhiều số?

Question

Vì vậy, tôi đang viết một chương trình bằng Python để lấy số GCD của bất kỳ số lượng nào.

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) 

Hàm này có danh sách các số. Điều này sẽ in 2. Tuy nhiên, tôi không hiểu cách sử dụng thuật toán đệ quy để nó có thể xử lý nhiều số. Ai đó có thể giải thích?

cập nhật, vẫn không làm việc:

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 

---

Ok, giải quyết nó

def GCD(a, b): 

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

và sau đó sử dụng giảm, như

reduce(GCD, (30, 40, 36)) 

Answer 1

Kể từ GCD là kết hợp, GCD(a,b,c,d) cũng giống như GCD(GCD(GCD(a,b),c),d). Trong trường hợp này, hàm reduce của Python sẽ là một ứng cử viên tốt cho việc giảm các trường hợp trong đó len(numbers) > 2 thành so sánh 2 số đơn giản.Mã này sẽ giống như thế này:

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

Giảm áp dụng chức năng cho mỗi phần tử trong danh sách, do đó cái gì đó như

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

cũng giống như làm

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

Bây giờ điều duy nhất còn lại là viết mã cho khi len(numbers) <= 2. Chỉ truyền hai đối số cho GCD trong reduce đảm bảo rằng hàm của bạn đệ quy nhiều nhất một lần (kể từ len(numbers) > 2 chỉ trong cuộc gọi ban đầu), có lợi ích bổ sung là không bao giờ làm tràn ngăn xếp.

Answer 2

Nhà điều hành GCD là giao hoán và liên kết. Điều này có nghĩa rằng

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

Vì vậy, một khi bạn biết làm thế nào để làm điều đó cho 2 con số, bạn có thể làm điều đó cho bất kỳ số

---

Để làm điều đó cho hai con số, bạn chỉ cần thực hiện công thức Euclid , chỉ đơn giản là:

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

Xác định chức năng đó như, nói euclid(a,b). Sau đó, bạn có thể xác định gcd(nums) như:

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

này sử dụng thuộc tính kết hợp của gcd() để tính toán câu trả lời

Answer 3

Bạn có thể sử dụng reduce:

>>> from fractions import gcd 
>>> reduce(gcd,(30,40,60)) 
10 

tương đương với;

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

giúp đỡ trên 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. 

Answer 4

Hãy thử gọi GCD() như sau,

i = 0 
temp = numbers[i] 
for i in range(len(numbers)-1): 
     temp = GCD(numbers[i+1], temp) 

Answer 5

Một giải pháp để tìm ra những LCM hơn hai con số trong PYTHON là như sau:

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

Ở đây tôi đã thêm +1 trong đối số cuối cùng của phạm vi() do hàm bắt đầu từ 0 (0) đến n-1. Nhấp vào liên kết để biết về nhiều range() chức năng:

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

những người chưa quen với python có thể đọc thêm về reduce() chức năng bằng cách liên kết nhất định.