De grootste gemene deler (GCD) van a en b is het grootste getal dat beide deelt zonder rest.
Een manier om de GCD van twee getallen te vinden is het algoritme van Euclid, dat gebaseerd is op de waarneming dat als rde rest is wanneer awordt gedeeld door b, dan gcd(a, b) = gcd(b, r). Als basisscenario kunnen we gcd(a, 0) = agebruiken.
Schrijf een functie met de naam ggd die de parameters aen bneemt en hun grootste gemene deler teruggeeft.
Antwoord 1, autoriteit 100%
Het staat in de standaardbibliotheek.
>>> from fractions import gcd
>>> gcd(20,8)
4
Broncode van de module inspectin Python 2.7:
>>> print inspect.getsource(gcd)
def gcd(a, b):
"""Calculate the Greatest Common Divisor of a and b.
Unless b==0, the result will have the same sign as b (so that when
b is divided by it, the result comes out positive).
"""
while b:
a, b = b, a%b
return a
Vanaf Python 3.5 is gcdin de mathmodule; die in fractionsis verouderd. Bovendien retourneert inspect.getsourcegeen verklarende broncode meer voor beide methoden.
Antwoord 2, autoriteit 13%
De algoritmen met m-n kunnen erg lang duren.
Deze presteert veel beter:
def gcd(x, y):
while y != 0:
(x, y) = (y, x % y)
return x
Antwoord 3, autoriteit 6%
Deze versie van de code gebruikt het algoritme van Euclid om GCD te vinden.
def gcd_recursive(a, b):
if b == 0:
return a
else:
return gcd_recursive(b, a % b)
Antwoord 4, autoriteit 5%
gcd = lambda m,n: m if not n else gcd(n,m%n)
Antwoord 5
met behulp van recursie,
def gcd(a,b):
return a if not b else gcd(b, a%b)
met behulp van terwijl,
def gcd(a,b):
while b:
a,b = b, a%b
return a
met behulp van lambda,
gcd = lambda a,b : a if not b else gcd(b, a%b)
>>> gcd(10,20)
>>> 10
Antwoord 6
def gcd(m,n):
return gcd(abs(m-n), min(m, n)) if (m-n) else n
Antwoord 7
Zeer beknopte oplossing met recursie:
def gcd(a, b):
if b == 0:
return a
return gcd(b, a%b)
Antwoord 8
a=int(raw_input('1st no \n'))
b=int(raw_input('2nd no \n'))
def gcd(m,n):
z=abs(m-n)
if (m-n)==0:
return n
else:
return gcd(z,min(m,n))
print gcd(a,b)
Een andere benadering gebaseerd op het algoritme van Euclides.
Antwoord 9
def gcdRecur(a, b):
'''
a, b: positive integers
returns: a positive integer, the greatest common divisor of a & b.
'''
# Base case is when b = 0
if b == 0:
return a
# Recursive case
return gcdRecur(b, a % b)
Antwoord 10
Ik denk dat een andere manier is om recursie te gebruiken. Hier is mijn code:
def gcd(a, b):
if a > b:
c = a - b
gcd(b, c)
elif a < b:
c = b - a
gcd(a, c)
else:
return a
Antwoord 11
in python met recursie:
def gcd(a, b):
if a%b == 0:
return b
return gcd(b, a%b)
Antwoord 12
def gcd(a,b):
if b > a:
return gcd(b,a)
r = a%b
if r == 0:
return b
return gcd(r,b)
Antwoord 13
Voor a>b:
def gcd(a, b):
if(a<b):
a,b=b,a
while(b!=0):
r,b=b,a%r
a=r
return a
Voor a>bof a<b:
def gcd(a, b):
t = min(a, b)
# Keep looping until t divides both a & b evenly
while a % t != 0 or b % t != 0:
t -= 1
return t
Antwoord 14
Ik moest zoiets doen voor een huiswerkopdracht met while-loops. Niet de meest efficiënte manier, maar als je een functie niet wilt gebruiken, werkt dit:
num1 = 20
num1_list = []
num2 = 40
num2_list = []
x = 1
y = 1
while x <= num1:
if num1 % x == 0:
num1_list.append(x)
x += 1
while y <= num2:
if num2 % y == 0:
num2_list.append(y)
y += 1
xy = list(set(num1_list).intersection(num2_list))
print(xy[-1])
Antwoord 15
def _grateest_common_devisor_euclid(p, q):
if q==0 :
return p
else:
reminder = p%q
return _grateest_common_devisor_euclid(q, reminder)
print(_grateest_common_devisor_euclid(8,3))
Antwoord 16
Deze code berekent de ggd van meer dan twee getallen, afhankelijk van de keuze die de gebruiker # heeft gegeven, hier geeft de gebruiker het getal op
numbers = [];
count = input ("HOW MANY NUMBERS YOU WANT TO CALCULATE GCD?\n")
for i in range(0, count):
number = input("ENTER THE NUMBER : \n")
numbers.append(number)
numbers_sorted = sorted(numbers)
print 'NUMBERS SORTED IN INCREASING ORDER\n',numbers_sorted
gcd = numbers_sorted[0]
for i in range(1, count):
divisor = gcd
dividend = numbers_sorted[i]
remainder = dividend % divisor
if remainder == 0 :
gcd = divisor
else :
while not remainder == 0 :
dividend_one = divisor
divisor_one = remainder
remainder = dividend_one % divisor_one
gcd = divisor_one
print 'GCD OF ' ,count,'NUMBERS IS \n', gcd
Antwoord 17
Het wisselen van waarde werkte niet goed voor mij. Dus ik heb zojuist een spiegelachtige situatie opgezet voor getallen die worden ingevoerd in een < b OF a > b:
def gcd(a, b):
if a > b:
r = a % b
if r == 0:
return b
else:
return gcd(b, r)
if a < b:
r = b % a
if r == 0:
return a
else:
return gcd(a, r)
print gcd(18, 2)
Antwoord 18
#This program will find the hcf of a given list of numbers.
A = [65, 20, 100, 85, 125] #creates and initializes the list of numbers
def greatest_common_divisor(_A):
iterator = 1
factor = 1
a_length = len(_A)
smallest = 99999
#get the smallest number
for number in _A: #iterate through array
if number < smallest: #if current not the smallest number
smallest = number #set to highest
while iterator <= smallest: #iterate from 1 ... smallest number
for index in range(0, a_length): #loop through array
if _A[index] % iterator != 0: #if the element is not equally divisible by 0
break #stop and go to next element
if index == (a_length - 1): #if we reach the last element of array
factor = iterator #it means that all of them are divisibe by 0
iterator += 1 #let's increment to check if array divisible by next iterator
#print the factor
print factor
print "The highest common factor of: ",
for element in A:
print element,
print " is: ",
greatest_common_devisor(A)
Antwoord 19
def gcdIter(a, b):
gcd= min (a,b)
for i in range(0,min(a,b)):
if (a%gcd==0 and b%gcd==0):
return gcd
break
gcd-=1
Antwoord 20
Hier is de oplossing die het concept van Iterationimplementeert:
def gcdIter(a, b):
'''
a, b: positive integers
returns: a positive integer, the greatest common divisor of a & b.
'''
if a > b:
result = b
result = a
if result == 1:
return 1
while result > 0:
if a % result == 0 and b % result == 0:
return result
result -= 1