I dette eksemplet vil du lære å finne GCD av to tall ved hjelp av to forskjellige metoder: funksjon og sløyfer og, euklidisk algoritme
For å forstå dette eksemplet, bør du ha kunnskap om følgende Python-programmeringsemner:
- Python-funksjoner
- Python rekursjon
- Argumenter for Python-funksjon
Den høyeste fellesfaktoren (HCF) eller største fellesdeler (GCD) av to tall er det største positive heltallet som perfekt deler de to gitte tallene. For eksempel er HCF på 12 og 14 2.
Kildekode: Bruke sløyfer
# Python program to find H.C.F of two numbers # define a function def compute_hcf(x, y): # choose the smaller number if x> y: smaller = y else: smaller = x for i in range(1, smaller+1): if((x % i == 0) and (y % i == 0)): hcf = i return hcf num1 = 54 num2 = 24 print("The H.C.F. is", compute_hcf(num1, num2))
Produksjon
HCF er 6
Her blir to heltall lagret i variablene num1 og num2 overført til compute_hcf()funksjonen. Funksjonen beregner HCF disse to tallene og returnerer den.
I funksjonen bestemmer vi først det minste av de to tallene siden HCF bare kan være mindre enn eller lik det minste tallet. Vi bruker deretter en forsløyfe for å gå fra 1 til det tallet.
I hver iterasjon sjekker vi om tallet vårt perfekt deler begge inngangstallene. I så fall lagrer vi nummeret som HCF Ved fullføringen av sløyfen ender vi opp med det største tallet som perfekt deler begge tallene.
Ovennevnte metode er enkel å forstå og implementere, men ikke effektiv. En mye mer effektiv metode for å finne HCF er den euklidiske algoritmen.
Euklidisk algoritme
Denne algoritmen er basert på det faktum at HCF med to tall også deler forskjellen.
I denne algoritmen deler vi større med mindre og tar resten. Del nå det mindre med denne resten. Gjenta til resten er 0.
Hvis vi for eksempel vil finne HCF på 54 og 24, deler vi 54 med 24. Resten er 6. Nå deler vi 24 med 6 og resten er 0. Derfor er 6 den nødvendige HCF
Kildekode: Bruke den euklidiske algoritmen
# Function to find HCF the Using Euclidian algorithm def compute_hcf(x, y): while(y): x, y = y, x % y return x hcf = compute_hcf(300, 400) print("The HCF is", hcf)
Her sløyfer vi til y blir null. Uttalelsen x, y = y, x % ybytter verdier i Python. Klikk her for å lære mer om å bytte variabler i Python.
I hver iterasjon plasserer vi verdien av y i x og resten (x % y)i y, samtidig. Når y blir null, har vi HCF i x.
