Største vanlig divisor med Python

En faktor er et tall som kan gå inn i et annet tall uten resten. Et utbytte deler en divisor for å gi kvotienten. Hvis utbyttet og divisoren er et helt tall, og hvis kvotienten har en resten av null (ingen resten), kalles divisoren en faktor for utbyttet. Største vanlig divisor er forkortet, g.C.D eller bare GCD. Et annet navn for største felles divisor er høyest vanlig faktor, forkortet h.C.F.

Finne g.C.F per definisjon

Problemet er å finne den høyeste vanlige faktoren også kalt den største vanlige divisoren for tallene 108 og 240.

Løsning:

Alle faktorene større enn 1 er plassert i følgende tabell:

108: 2 3 4 6 9 12 18 27 36 54 108
240: 2 3 4 5 6 8 10 12 15 16 20 24 30 48 60 120 240

Den første raden har faktorene på 108 i stigende rekkefølge. Den andre raden har faktorene på 240 i stigende rekkefølge.

Vanlige faktorer (divisorer) for 108 og 240 er: 2, 3, 4, 6 og 12.

Ved inspeksjon er den største faktoren (divisor) som er vanlig for tallene 108 og 240 12. Det vil si GCD eller H.C.F for 108 og 240 er 12.

Å skrive et program som vil finne GCD -en, som forklart ovenfor, vil ta for lang tid. To kortere metoder for å finne GCD er: GCD ved subtraksjon og GCD etter divisjon.

GCD ved subtraksjon

Ved inspeksjon fra tabellen ovenfor er GCD for 108 og 240 12. Dette betyr at hvis 12 blir lagt til gjentatte ganger, vil resultatet bli 108 som er det mindre av begge tallene. Hvis tillegget av 12 fortsetter, vil resultatet bli 240 som er det større av begge tallene. Det er:

12 + 12 +12 +12 + 12 + 12 + 12 + 12 + 12 = 108
12 + 12 +12 +12 + 12 + 12 + 12 + 12 + 12 + 12 + 12 +12 +12 + 12 + 12 + 12 + 12 + 12 + 12 + 12 = 240

Det er:

108 + 12 + 12 + 12 + 12 + 12 + 12 +12 +12 + 12 + 12 + 12 = 240

Som betyr:

108 + 132 = 240

Hvis GCD -en kan legges til gjentatte ganger for å gi noen av tallene (108 og 240) som GCD er påkrevd, kan det være mulig å gjøre en slags subtraksjon gjentatte ganger, som begynner med de gitte tallene for å ha GCD. Det er faktisk mulig å gjøre en bestemt type subtraksjon gjentatte ganger og få GCD. Dette begynner med forskjellen på de gitte tallene.

Problem: Finn den største vanlige divisoren (høyest vanlig faktor) for 108 og 240 ved subtraksjon.

Løsning:

240 - 108 = 132
132 - 108 = 24
108 - 24 = 84
84 - 24 = 60
60 - 24 = 36
36 - 24 = 12
24 - 12 = 12
12 - 12 = 0

Mellom 108 og 240, 240 er det større antallet. Etter forskjellen på disse gitte tallene, oppnås forskjellen på den resulterende forskjellen (132 for det første trinnet) og subtrahend (108 for det første trinnet) gjentatte ganger til den endelige forskjellen er null. I trinnene trekkes det mindre antallet fra det større antallet. På det siste trinnet er minuend og subtrahend den samme. Denne samme verdien er den største vanlige divisoren.

La tallene hvis GCD er nødvendig være 'A' og 'B'. Hvis disse tallene ikke har noen GCD større enn 1, betyr det at deres største vanlige divisor er 1. I programmering er tidskompleksiteten for å finne GCD ved subtraksjon O (A+B). Hvis 'A' er 1 og B er 6, vil trinnene uten programmering, være:

6 - 1 = 5
5 - 1 = 4
4 - 1 = 3
3 - 1 = 2
2 - 1 = 1
1 - 1 = 0

GCD -en her er 1. Det er seks trinn her og ikke syv trinn av (A + B). Imidlertid er det maksimalt mulig antall kodeoperasjoner i programmering som tidskompleksiteten som er tatt som tidskompleksiteten.

Koding GCD ved subtraksjon

Funksjonen for den største vanlige divisoren ved subtraksjon, i Python, er:

def gcds (a, b):
Hvis a == B:
returner a
Hvis a> b:
Returner GCD -er (A - B, B)
ellers:
Returner GCD -er (A, B - A)

Den første uttalelsen tar seg av det siste matematikkrinnet. Den neste sammensatte uttalelsen (hvis/annet) gjør subtraksjonen mellom minuend og forskjellen, avhengig av hvilken som er større.

Dyptgående blikk på GCD-matematikkundertraksjonene

240 - 108 = 132
132 = 12 x 11 (132 har 12 som en faktor)
132 - 108 = 24
24 = 12 x 2 (24 har 12 som en faktor)
108 - 24 = 84
84 = 12 x 7 (84 har 12 som faktor)
84 - 24 = 60
60 = 12 x 5 (60 har 12 som en faktor)
60 - 24 = 36
36 = 12 x 3 (36 har 12 som faktor)
24 - 12 = 12
12 = 12 x 1 (12 har en faktor eller 12 - i seg selv)
24 - 12 = 12
12 = 12 x 1 (12 har en faktor eller 12 - i seg selv)

Det siste trinnet har en forskjell på 0. Det markerer slutten på subtraksjonstrinnene og gir GCD som subtrahend eller minuend.

GCD etter divisjon

Mellom 108 og 240 er GCD større enn 1.

12 + 12 +12 +12 + 12 + 12 + 12 + 12 + 12 = 108
12 + 12 +12 +12 + 12 + 12 + 12 + 12 + 12 + 12 + 12 +12 +12 + 12 + 12 + 12 + 12 + 12 + 12 + 12 = 240

Det er:

108 + 12 + 12 + 12 + 12 + 12 + 12 +12 +12 + 12 + 12 + 12 = 240

Som betyr:

108 + 132 = 240

Det er:

12 x 9 + 12 x 11 = 240

Også 108 = 12 x 9 og 240 = 12 x 20.

Nå, hvis GCD kan multipliseres med et helt antall (positivt heltall) for å gi et av tallene (108 eller 240) som GCD er påkrevd, kan det være mulig å gjøre en slags divisjon gjentatte ganger, som begynner med gitt tall for å ha GCD. Det er faktisk mulig å gjøre en bestemt type divisjon gjentatte ganger og få GCD. Denne divisjonen er en spesiell gjentatt modulavdeling. Det begynner med modulavdelingen av de gitte tallene.

I Modulus Division, når utbyttet er delt på divisoren, er resten for kvotienten svaret.

Problem: Finn den største vanlige divisoren (høyest vanlig faktor) for 108 og 240 ved modulavdeling:

Løsning:

240 % 108 = 24 (i.e. 2 r 24)
108 % 24 = 12 (i.e. 4 R 12)
24 % 12 = 0 (i.e. 2 r 0)

På den siste linjen, der resten er null, er divisoren den største vanlige divisoren (høyest vanlig faktor).

Dette problemet er å finne GCD mellom 108 og 240 etter divisjon. Løsningen her tok 3 trinn. Det forrige problemet var likt, men det var å se etter samme GCD ved subtraksjon; Og den hadde 8 trinn. Mens tidskompleksiteten for subtraksjonsmetoden er O (A + B), er tidskompleksiteten for divisjonsmetoden O (log (A + B)).

I Modulus Division spiller det ingen rolle om 'A' er større enn B eller B er større enn 'A'; resten er det samme positive heltallet.

Finn matematisk, den største vanlige divisoren etter divisjon, for tallene, 5 og 2.

Løsning:

5 % 2 = 1
1 % 1 = 0

GCD er 1. Dette trengte to matematiske trinn.

Koding GCD etter divisjon

Ordet "Divisjon" refererer til Modulus Division. Funksjonen er:

def gcdd (a, b):
if (a % b == 0):
Retur b
ellers:
Returner GCDD (B, A % B)

If-delen av IF/ellers-konstruksjonen tar seg av den siste matematiske uttalelsen, for trinnene i Modulus Division. Den andre delen tar seg av den faktiske Modulo -divisjonen (resulterer i resten). I Modulus Division spiller det ingen rolle om 'A' er større enn B eller B er større enn 'A'; resten er det samme positive heltallet.

For å ringe og skrive ut en GCD, kan følgende kode brukes:

Ret = GCDD (240, 108)
print (ret, end = '\ n')

Dyptgående blikk på GCD-matematikkdivisjonene

240 % 108 = 24 (GCD mellom 240 og 108 er 12)
24 = 12 x 2 (24 har 12 som en faktor)
108 % 24 = 12 (GCD mellom 108 og 24 er 12)
12 = 12 x 1 (12 har 12 som en faktor, i seg selv)
24 % 12 = 0 (GCD mellom 24 og 12 er 12)

Det er demonstrert her, at:

GCD (A, B) = GCD (B, R)

hvor 'a' og b er to forskjellige hele tall og 'r' er resten av divisjonen mellom a og b. B kan være større enn 'A' eller 'A' kan være større enn B. Så hvis resten av en divisjon ikke er null, er den største vanlige divisoren mellom de to gitte tallene den samme som den største vanlige divisoren mellom divisoren og resten. Dette går ned i forskjellige trinn til resten er null, selv om GCD er 1.

Det siste trinnet har en resten av 0. Det markerer slutten på modulusdivisjonstrinnene og GCD er divisoren.

Konklusjon

Den største vanlige divisoren kan bestemmes ved gjentatte subtraksjoner eller gjentatte modulo -divisjoner.

Hvis det er ved subtraksjon, er resten av subtraksjonene mellom forskjellen og minuenden etter subtraksjonen av de gitte tallene, avhengig av hvilken som er større. Når forskjellen er null, er subtrahenden lik minuend, og enten er GCD.

Hvis det er etter divisjon, er de gjentatte divisjonene modulavdelinger. I denne situasjonen, etter modulavdelingen av de gitte tallene, er resten av modulavdelingene mellom divisoren og resten, avhengig av hvilken som er større. Når resten er null, er divisoren GCD. Strengt tatt, i Modulus Division, spiller det ingen rolle om 'A' er større enn B eller B er større enn 'A'; resten er det samme positive heltallet.