V tomto příkladu se naučíte najít GCD dvou čísel pomocí dvou různých metod: funkce a smyčky a, euklidovský algoritmus
Abychom porozuměli tomuto příkladu, měli byste znát následující témata programování v Pythonu:
- Funkce Pythonu
- Rekurze Pythonu
- Argumenty funkce Pythonu
Nejvyšší společný faktor (HCF) nebo největší společný dělitel (GCD) dvou čísel je největší kladné celé číslo, které dokonale dělí dvě uvedená čísla. Například HCF 12 a 14 je 2.
Zdrojový kód: Použití smyček
# 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ýstup
HCF je 6
Zde jsou do compute_hcf()funkce předána dvě celá čísla uložená v proměnných num1 a num2 . Funkce vypočítá HCF tato dvě čísla a vrátí je.
Ve funkci nejprve určíme menší ze dvou čísel, protože HCF může být pouze menší nebo rovno nejmenšímu číslu. Potom použijeme forsmyčku k přechodu z 1 na toto číslo.
V každé iteraci kontrolujeme, zda naše číslo dokonale dělí obě vstupní čísla. Pokud ano, uložíme číslo jako HCF. Po dokončení smyčky skončíme s největším číslem, které obě čísla dokonale rozdělí.
Výše uvedená metoda je snadno pochopitelná a implementovatelná, ale není efektivní. Mnohem efektivnější metodou k nalezení HCF je euklidovský algoritmus.
Euklidovský algoritmus
Tento algoritmus je založen na skutečnosti, že HCF dvou čísel také dělí jejich rozdíl.
V tomto algoritmu rozdělíme větší na menší a vezmeme zbytek. Nyní rozdělte menší tímto zbytkem. Opakujte, dokud není zbytek 0.
Například, pokud chceme najít HCF 54 a 24, rozdělíme 54 na 24. Zbytek je 6. Nyní dělíme 24 o 6 a zbytek je 0. Proto je 6 požadovaný HCF
Zdrojový kód: Použití 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)
Zde smyčkujeme, dokud se y nestane nula. Příkaz x, y = y, x % yzaměňuje hodnoty v Pythonu. Kliknutím sem získáte další informace o výměně proměnných v Pythonu.
V každé iteraci současně umístíme hodnotu y na x a zbytek (x % y)na y. Když se y stane nulovou, máme HCF v x.
