Nasleduje opis výpočtu a získania najväčšieho spoločného deliteľa a najmenšieho spoločného násobku v jazyku Python.
- Najväčší spoločný deliteľ a najmenší spoločný násobok dvoch celých čísel
- Najväčší spoločný deliteľ a najmenší spoločný násobok troch alebo viacerých celých čísel
Všimnite si, že špecifikácie funkcií poskytovaných v štandardnej knižnici sa líšia v závislosti od verzie jazyka Python. V tomto článku je uvedený aj príklad implementácie funkcie, ktorá nie je v štandardnej knižnici.
- Python 3.4 alebo starší
- GCD:
fractions.gcd()(iba dva argumenty)
- GCD:
- Python 3.5 alebo novší
- GCD:
math.gcd()(iba dva argumenty)
- GCD:
- Python 3.9 alebo novší
- GCD:
math.gcd()(podporuje viac ako tri argumenty) - najmenší spoločný menovateľ:
math.lcm()(podporuje viac ako tri argumenty)
- GCD:
Tu vysvetlíme metódu pomocou štandardnej knižnice Pythonu; NumPy možno ľahko použiť na výpočet najväčšieho spoločného deliteľa a najmenšieho spoločného násobku pre každý prvok viacerých polí.
Najväčší spoločný deliteľ a najmenší spoločný násobok dvoch celých čísel
GCD
Od verzie Python 3.5 je v matematickom module funkcia gcd(). gcd() je skratka pre
- greatest common divisor
Vráti najväčší spoločný deliteľ celého čísla zadaného v argumente.
import math
print(math.gcd(6, 4))
# 2
Všimnite si, že v Pythone 3.4 a starších verziách sa funkcia gcd() nachádza v module fractions, nie v module math. fractions musí byť importovaná a fractions.gcd().
najmenší spoločný menovateľ
Funkcia lcm(), ktorá vracia najmenší spoločný násobok, bola pridaná do matematického modulu v jazyku Python 3.9. lcm je skratka pre
- least common multiple
Vráti najmenší spoločný násobok celého čísla zadaného v argumente.
print(math.lcm(6, 4))
# 12
Pred verziou Python 3.8 funkcia lcm() nie je k dispozícii, ale možno ju ľahko vypočítať pomocou funkcie gcd().
lcm(a, b) = a * b / gcd(a, b)
Príklad implementácie.
def my_lcm(x, y):
return (x * y) // math.gcd(x, y)
print(my_lcm(6, 4))
# 12
/Keďže výsledkom je desatinné číslo typu float, na skrátenie desatinnej čiarky a vrátenie celočíselného výsledku delenia sa použijú dve spätné lomítka. Všimnite si, že sa nevykonáva žiadne spracovanie na určenie, či je argument celé číslo alebo nie.
Najväčší spoločný deliteľ a najmenší spoločný násobok troch alebo viacerých celých čísel
Python 3.9 alebo novší
Počnúc verziou Python 3.9 všetky nasledujúce funkcie podporujú viac ako tri argumenty.
math.gcd()math.lcm()
print(math.gcd(27, 18, 9))
# 9
print(math.gcd(27, 18, 9, 3))
# 3
print(math.lcm(27, 9, 3))
# 27
print(math.lcm(27, 18, 9, 3))
# 54
*Ak chcete vypočítať najväčší spoločný deliteľ alebo najmenší spoločný násobok prvkov zoznamu, zadajte tento argument.
l = [27, 18, 9, 3]
print(math.gcd(*l))
# 3
print(math.lcm(*l))
# 54
Python 3.8 alebo starší
Pred verziou 3.8 podporovala funkcia gcd() iba dva argumenty.
Na nájdenie najväčšieho spoločného deliteľa alebo najmenšieho spoločného násobku troch alebo viacerých celých čísel nie je potrebný nijako zvlášť zložitý algoritmus; stačí postupne vypočítať najväčší spoločný deliteľ alebo najmenší spoločný násobok pre každú z hodnôt násobku pomocou funkcie vyššieho rádu reduce().
GCD
from functools import reduce
def my_gcd(*numbers):
return reduce(math.gcd, numbers)
print(my_gcd(27, 18, 9))
# 9
print(my_gcd(27, 18, 9, 3))
# 3
l = [27, 18, 9, 3]
print(my_gcd(*l))
# 3
Opäť upozorňujeme, že pred verziou Python 3.4 sa funkcia gcd() nachádzala v module fraction, nie v module math.
najmenší spoločný menovateľ
def my_lcm_base(x, y):
return (x * y) // math.gcd(x, y)
def my_lcm(*numbers):
return reduce(my_lcm_base, numbers, 1)
print(my_lcm(27, 9, 3))
# 27
print(my_lcm(27, 18, 9, 3))
# 54
l = [27, 18, 9, 3]
print(my_lcm(*l))
# 54
