V tomto príklade sa naučíte nájsť GCD dvoch čísel pomocou dvoch rôznych metód: funkcie a slučky a, euklidovský algoritmus
Aby ste pochopili tento príklad, mali by ste mať znalosti nasledujúcich tém programovania v jazyku Python:
- Pythonove funkcie
- Pythonova rekurzia
- Argumenty funkcie Python
Najvyšší spoločný faktor (HCF) alebo najväčší spoločný deliteľ (GCD) dvoch čísel je najväčšie kladné celé číslo, ktoré dokonale rozdeľuje dve dané čísla. Napríklad HCF 12 a 14 je 2.
Zdrojový kód: Použitie slučiek
# 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))
Výkon
HCF je 6
Tu sa compute_hcf()funkcii odovzdajú dve celé čísla uložené v premenných num1 a num2 . Funkcia vypočíta HCF tieto dve čísla a vráti ich.
Vo funkcii najskôr určíme menšie z dvoch čísel, pretože HCF môže byť iba menšie alebo rovnaké ako najmenšie číslo. Potom pomocou forslučky prejdeme z 1 na toto číslo.
V každej iterácii kontrolujeme, či naše číslo dokonale rozdeľuje obe vstupné čísla. Ak je to tak, uložíme číslo ako HCF. Po dokončení cyklu skončíme s najväčším číslom, ktoré dokonale rozdelí obe čísla.
Vyššie uvedená metóda je ľahko pochopiteľná a implementovateľná, ale nie efektívna. Oveľa efektívnejšou metódou na vyhľadanie HCF je euklidovský algoritmus.
Euklidovský algoritmus
Tento algoritmus je založený na skutočnosti, že HCF dvoch čísel tiež rozdeľuje ich rozdiel.
V tomto algoritme vydelíme väčšie a menšie a vezmeme zvyšok. Teraz vydelte menšie týmto zvyškom. Opakujte, kým zvyšok nie je 0.
Napríklad, ak chceme nájsť HCF 54 a 24, vydelíme 54 24. Zvyšok je 6. Teraz vydelíme 24 6 a zvyšok 0. Preto je 6 požadovaný HCF
Zdrojový kód: Použitie euklidovského algoritmu
# 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)
Tu prechádzame slučkou, kým sa y nestane nulovým. Príkaz x, y = y, x % yzamieňa hodnoty v Pythone. Kliknite sem a dozviete sa viac o zámene premenných v Pythone.
V každej iterácii umiestnime hodnotu y na x a zvyšok (x % y)na y súčasne. Keď sa y stane nulou, máme HCF v x.
