I dette eksempel lærer du at finde GCD af to tal ved hjælp af to forskellige metoder: funktion og sløjfer og euklidisk algoritme
For at forstå dette eksempel skal du have kendskab til følgende Python-programmeringsemner:
- Python-funktioner
- Python rekursion
- Argumenter for Python-funktion
Den højeste fælles faktor (HCF) eller største fælles divisor (GCD) på to tal er det største positive heltal, der perfekt deler de to givne tal. For eksempel er HCF på 12 og 14 2.
Kildekode: Brug af sløjfer
# 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))
Produktion
HCF er 6
Her overføres to heltal, der er gemt i variablerne num1 og num2, til compute_hcf()funktionen. Funktionen beregner HCF disse to tal og returnerer den.
I funktionen bestemmer vi først det mindste af de to tal, da HCF kun kan være mindre end eller lig med det mindste tal. Vi bruger derefter en forløkke til at gå fra 1 til det tal.
I hver iteration kontrollerer vi, om vores nummer perfekt deler begge inputnumrene. I så fald gemmer vi antallet som HCF Ved afslutningen af sløjfen ender vi med det største tal, der perfekt deler begge numrene.
Ovenstående metode er let at forstå og implementere, men ikke effektiv. En meget mere effektiv metode til at finde HCF er den euklidiske algoritme.
Euklidisk algoritme
Denne algoritme er baseret på, at HCF med to tal også deler deres forskel.
I denne algoritme dividerer vi større med mindre og tager resten. Del nu den mindre med denne rest. Gentag, indtil resten er 0.
For eksempel, hvis vi ønsker at finde HCF på 54 og 24, dividerer vi 54 med 24. Resten er 6. Nu deler vi 24 med 6, og resten er 0. Derfor er 6 den krævede HCF
Kildekode: Brug af den euklidiske algoritme
# 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øjfer vi, indtil y bliver nul. Erklæringen x, y = y, x % ybytter værdier i Python. Klik her for at lære mere om at bytte variabler i Python.
I hver iteration placerer vi værdien af y i x og resten (x % y)i y samtidigt. Når y bliver nul, har vi HCF i x.
