Code voor de grootste gemene deler in Python

De grootste gemene deler (GCD) van a en b is het grootste getal dat beide met geen rest verdeelt.

Een manier om de GCD van twee getallen te vinden is het algoritme van Euclides, dat is gebaseerd op de waarneming dat als r de rest is wanneer a wordt gedeeld door b , dan gcd (a, b) = gcd (b, r) . Als een basisgeval kunnen we gcd (a, 0) = a gebruiken.

Schrijf een functie met de naam gcd die parameters a en b aanneemt en hun grootste gemene deler retourneert.

83
"Schrijf een functie met de naam gcd die parameters a en b opneemt en hun grootste gemene deler retourneert." - zucht, nog een kwestie van de kwestie van het plakken van het huiswerk in Stack Overflow
toegevoegd de auteur Jason S, de bron
@zondo De vraag lijkt mij vrij specifiek bij het bekijken van deze richtlijnen .
toegevoegd de auteur Taryn, de bron
@bluefeet: hoe is dit voor mijn eigen opbouw niet te breed?
toegevoegd de auteur zondo, de bron

16 antwoord

Het is in de standaardbibliotheek .

>>> from fractions import gcd
>>> gcd(20,8)
4

Broncode van de module inspect in 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 gcd in de < code> wiskunde module; die in fracties is verouderd. Bovendien retourneert inspect.getsource niet langer een verklarende broncode voor beide methoden.

@TomKarzes: je zou de link moeten lezen in plaats van alleen maar te skimmen.
toegevoegd de auteur jfs, de bron
@TomKarzes beschouwt het algoritme als de definitie van het concept
toegevoegd de auteur jfs, de bron
@TomKarzes: bekijk de broncode in de link. Vergelijk het met de code in het antwoord.
toegevoegd de auteur jfs, de bron
@TomKarzes: lees de link.
toegevoegd de auteur jfs, de bron
@TomKarzes de fracties.gcd kan werken op invoer die geen begrip van "negatief" heeft. stepanovpapers.com/gcd.pdf
toegevoegd de auteur jfs, de bron
@ A-B-B math.gcd() en fractions.gcd() verschillen van elkaar zoals gezegd in het antwoord en de opmerkingen.
toegevoegd de auteur jfs, de bron
@MarcoBonelli: ja. Het gedraagt ​​zich zoals gedocumenteerd, maar het is niet de definitie van het leerboek waarmee de meeste mensen bekend zijn. Lees de discussie die ik hierboven heb gekoppeld . Persoonlijk vind ik fractions.gcd() zoals het is (het werkt op Euclidean-ringelementen).
toegevoegd de auteur jfs, de bron
Het retourneert niet "het _largest_ getal dat beide met geen rest verdeelt" bijv. fractions.gcd (1, -1) is -1 maar 1> -1 dwz, 1 verdeelt zowel 1 als -1 zonder resten en het is groter dan -1 , zie bugs.python.org/issue22477
toegevoegd de auteur jfs, de bron
@jfs En wie zegt dat het ene algoritme logischer is dan het andere? Stel dat mijn implementatie a en b intern omkeert? Men zal gcd (1, -1) = -1 en de andere gcd (-1, 1) = -1 teruggeven. Er is absoluut geen reden om de voorkeur te geven boven de ander. Het is een intern , nutteloos artefact van de implementatie. Daarom beslissen mensen in plaats daarvan over het gewenste -resultaat en passen ze de implementatie aan. Doe het andersom is achteruit.
toegevoegd de auteur Tom Karzes, de bron
@jfs Sorry, ik keek naar de verkeerde link. Ja, ik ben het ermee eens dat het basisalgoritme a gcd vindt voor een bepaalde euclidische ring, en vereist geen specifieke kennis van die ring. Het probleem is dat de gcd mogelijk niet uniek is. Het externe resultaat afhankelijk maken van de interne onderdelen van de implementatie is een extreem slecht idee. Leuk vinden of niet, de enige manier om een ​​nuttig resultaat te krijgen, is om het aan het eind van het algoritme te "repareren" door de gewenste canonieke versie te kiezen. Voor getekende gehele getallen betekent dit het nemen van de absolute waarde. Voor Gaussische gehele getallen betekent dit vermenigvuldigen met een geheel getal van i.
toegevoegd de auteur Tom Karzes, de bron
@jfs Ze hebben het goed in math.gcd . De versie van fracties kan handig zijn voor sommige toepassingen, maar deze werkt niet goed met negatieve argumenten. In het bijzonder moet gcd altijd commutatief zijn, d.w.z. gcd (a, b) moet altijd gelijk zijn aan gcd (b, a) . Mathematica heeft het ook goed (het is identiek aan math.gcd ). Gezien de niet-algemene functionaliteit zou de versie in fracties beter zijn benoemd als fractions_non_commutative_sometimes_negative_gcd . Een echte gcd mag nooit een negatief resultaat opleveren.
toegevoegd de auteur Tom Karzes, de bron
@jfs Nee, kijk naar de broncode. Er staat expliciet dat het resultaat hetzelfde teken heeft als b als b niet nul is. Ze vertrouwen erop. Dat is waarom ze niet zijn overgeschakeld naar math.gcd toen het werd toegevoegd. Ze hebben een niet-standaard gcd geïmplementeerd, genaamd gcd , en vertrouwen op het niet-standaard gedrag. Het was een fout.
toegevoegd de auteur Tom Karzes, de bron
@jfs Heb net het afgeroomd. Het lijkt erop dat mensen het in het algemeen eens zijn met mijn standpunt, dat gcd altijd positief moet zijn en dat de versie in breuken problematisch is. Het feit dat de breukenversie niet commutatief is, is duidelijk een vergissing. Gcd is niet als een restbewerking, waarbij de twee operanden anders worden behandeld.
toegevoegd de auteur Tom Karzes, de bron
@jfs Ook de opmerking over Eucludean-ringen is een non-issue. Ik heb gcd voor Gaussian-getallen geïmplementeerd en aan het einde vermenigvuldig ik me eenvoudig met de juiste eenheid om een ​​canoniek resultaat te forceren (real> 0, imaginaire> = 0). En natuurlijk is het commutatief. Het creëren van een canoniek resultaat vereist eenvoudigweg kennis van de medewerkers van de gcd. Zonder die stap zou het resultaat afhankelijk zijn van de implementatie en dus onvoorspelbaar.
toegevoegd de auteur Tom Karzes, de bron
@JFSebastian Ik zie dit niet als een probleem ... kijk maar naar de opmerking in de broncode: "Tenzij b == 0, zal het resultaat hetzelfde teken hebben als b" , dus gcd (1, -1) == -1 lijkt mij volkomen legitiem.
toegevoegd de auteur Marco Bonelli, de bron
@ J.F.Sebastian FWIW, vanaf Python 3.5, math.gcd (1, -1) retourneert 1 .
toegevoegd de auteur A-B-B, de bron

De algoritmen met m-n kunnen ontzettend lang werken.

Deze presteert veel beter:

def gcd(x, y):
    while y != 0:
        (x, y) = (y, x % y)
    return x
32
toegevoegd
@hynekcer: je lijkt de context te missen. Ik bespreek het antwoord niet, ik bekritiseerde de opmerking door netom.
toegevoegd de auteur Martijn Pieters, de bron
@netom: wat helemaal niet nodig is bij het gebruik van een tuple-opdracht zoals gedaan in dit antwoord.
toegevoegd de auteur Martijn Pieters, de bron
@netom: nee, de opdracht kan niet zo worden geschreven; de tuple-toewijzing gebruikt x voordat deze wordt toegewezen. U hebt y eerst toegewezen aan x , dus nu wordt y ingesteld op 0 (als y% y is altijd 0).
toegevoegd de auteur Martijn Pieters, de bron
@MartijnPieters: dit algoritme voor de grootste gemene deler was correct. Het is een standaardmanier om in Python twee variabelen om te ruilen met (x, y) = (y, x) . Wat is het probleem voor jou?
toegevoegd de auteur hynekcer, de bron
@MartijnPieters Ja, je hebt gelijk, ik had een tijdelijke variabele moeten gebruiken. zoals dit: x_ = y; y = x% y; x = x_
toegevoegd de auteur netom, de bron
In de kern van de lus kan de opdracht worden geschreven als x = y; y = x% y. De lus loopt totdat y 0 bereikt. Dit is de "goede manier" om gcd-berekeningen uit te voeren. Het resultaat is in x, dat wordt geretourneerd door de functie. Meer informatie is hier te vinden: en.wikipedia.org/wiki/Euclidean_algorithm
toegevoegd de auteur netom, de bron
Dit is ook degene in de standaardbibliotheek.
toegevoegd de auteur sayantankhan, de bron
Hoe werkt dat algoritme zelfs? het is als magie.
toegevoegd de auteur user1311069, de bron
Hoe verschilt deze code van die in de standaard bibliotheek?
toegevoegd de auteur mentatkgs, de bron

Deze codeversie gebruikt het algoritme van Euclid voor het vinden van GCD.

def gcd_recursive(a, b):
    if b == 0:
        return a
    else:
        return gcd_recursive(b, a % b)
16
toegevoegd
U gebruikte iter in de naam maar het is eigenlijk een recursieve versie.
toegevoegd de auteur Shiplu Mokaddim, de bron
def gcd (a, b): als b == 0: retourneer een retour gcd (b, a% b)
toegevoegd de auteur Andyk, de bron
recursie is slecht efficiënt in vergelijking met loop-versies, + je moet het met b> a
toegevoegd de auteur Dr. Goulu, de bron
gcd = lambda m,n: m if not n else gcd(n,m%n)
12
toegevoegd
Wauw! Je blaast me echt! (Weg!) Dit zou het geaccepteerde antwoord moeten zijn. Geen afhankelijkheden, eenvoudige oneliner, fantastisch werk. Bedankt man.
toegevoegd de auteur Jonas Byström, de bron
def gcd(m,n):
    return gcd(abs(m-n), min(m, n)) if (m-n) else n
2
toegevoegd
Gebruik nooit 'is' als u wilt vergelijken voor gelijkheid. De kleine gehele getallen-cache is een CPython-implementatiedetail.
toegevoegd de auteur Marius Gedminas, de bron
#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)

2
toegevoegd
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
1
toegevoegd
Deze code is onvolledig (geen definitieve retourverklaring) en onjuist geformatteerd (geen indentaion). Ik weet niet eens zeker wat die onderbrekings -instructie probeert te bereiken.
toegevoegd de auteur kdopen, de bron
Bedankt voor het verstrekken van code die kan helpen het probleem op te lossen, maar over het algemeen zijn antwoorden veel handiger als ze een uitleg bevatten over wat de code moet doen en waarom dat het probleem oplost.
toegevoegd de auteur Lonely Neuron, de bron
Dit is de gemakkelijkste manier ... Maak het niet moeilijk!
toegevoegd de auteur Par bas, de bron

The value swapping didn't work well for me. So I just set up a mirror-like situation for numbers that are entered in either a < b OR 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)
1
toegevoegd
Dit is geen geldige Python-syntaxis. Inspringen is belangrijk.
toegevoegd de auteur Marius Gedminas, de bron
Hoe zit het met a = b? je zou een initiële IF-conditie moeten hebben om dit op te vangen.
toegevoegd de auteur josh.thomson, de bron

Deze code berekent de gcd van meer dan twee getallen, afhankelijk van de keuze van # de gebruiker, hier geeft de gebruiker het nummer

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
1
toegevoegd
Welkom bij Stack Overflow! Zou je overwegen een verhaal toe te voegen om uit te leggen waarom deze code werkt, en wat maakt het een antwoord op de vraag? Dit zou erg nuttig zijn voor de persoon die de vraag stelt, en voor iedereen die meegaat.
toegevoegd de auteur Andrew Barber, de bron

in python met recursie:

def gcd(a, b):
    if a%b == 0:
        return b
    return gcd(b, a%b)
1
toegevoegd

Zeer beknopte oplossing met recursie:

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a%b)
1
toegevoegd

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
0
toegevoegd
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 op basis van het algoritme van euclides.

0
toegevoegd
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)
0
toegevoegd
def gcd(a,b):
    if b > a:
        return gcd(b,a)
    r = a%b
    if r == 0:
        return b
    return gcd(r,b)
0
toegevoegd

For a>b:

def gcd(a, b):

    if(a

For either a>b or a:

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
0
toegevoegd
swap vars in python is spelende kinderen: b, a = a, b . probeer meer over de taal te lezen
toegevoegd de auteur HuStmpHrrr, de bron
Ik vind het leuk wat je zegt, maar ik hou niet van de manier waarop je het zegt
toegevoegd de auteur JackyZhu, de bron