एकाधिक संख्याओं के साथ यूक्लिडियन एल्गोरिदम (जीसीडी)?

Question

तो मैं किसी भी संख्या की जीसीडी प्राप्त करने के लिए पायथन में एक प्रोग्राम लिख रहा हूं।

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(GCD, (30, 40, 36)) 

Answer 1

GCD के बाद से साहचर्य है, GCD(a,b,c,d)GCD(GCD(GCD(a,b),c),d) रूप में ही है,। इस मामले में, पाइथन का reduce फ़ंक्शन उन मामलों को कम करने के लिए एक अच्छा उम्मीदवार होगा, जिसके लिए len(numbers) > 2 एक साधारण 2-संख्या तुलना में।कोड कुछ इस तरह दिखेगा:

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

कम सूची में प्रत्येक तत्व के लिए लागू होता दिया समारोह, ताकि

की तरह कुछ

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 के लिए कोड करना है। में GCD पर केवल दो तर्कों को पारित करने से यह सुनिश्चित होता है कि आपका फ़ंक्शन सबसे अधिक बार-बार (len(numbers) > 2 केवल मूल कॉल में) के बाद रिक्त हो जाता है, जिसमें स्टैक को कभी भी बहने का अतिरिक्त लाभ नहीं होता है।

Answer 2

को कम करने, का उपयोग 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) का कहना है।

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

यह gcd के साहचर्य संपत्ति() का उपयोग करता है जवाब की गणना करने के

Answer 3

आप उपयोग कर सकते हैं reduce: उसके बाद, आप gcd(nums) के रूप में परिभाषित कर सकते हैं

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

Answer 4

इस प्रकार GCD() कॉल करके देखें

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

Answer 5

अजगर में दो से अधिक संख्या के एलसीएम जानने के लिए एक समाधान के रूप में अनुवर्ती है:

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

यहाँ मैं सीमा के अंतिम बहस में +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))) 

जो लोग अजगर के लिए नए हैं दिए गए लिंक से reduce() समारोह के बारे में अधिक पढ़ सकते हैं।