Έστω ένα ορθογώνιο διαστάσεων x=30cm, y=12cm. Να βρεθεί ο μικρότερος αριθμός από τετράγωνα (ακέραιας πλευράς) που το καλύπτει.
Απάντηση: ΜΚΔ(30,12) = 6
# μια απλοϊκή υλοποίηση
def gcd_naive(x, y):
z = min(x, y)
for i in range(z, 0, -1):
if x % i == 0 and y % i == 0:
return i
# τυχαίες ακέραιες τιμές σε ένα διάστημα
import random
random.randrange(5000, 20000)
13495
%%timeit
# χρονομέτρηση απλοϊκού αλγορίθμου εύρεσης ΜΚΔ
a = random.randrange(50000, 200000)
b = random.randrange(50000, 200000)
x = gcd_naive(a,b)
7.64 ms ± 176 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
# ταχύτερος αλγόριθμος (αλγόριθμος του Ευκλείδη)
def gcd(x, y):
while y:
x, y = y, x % y
return x
%%timeit
a = random.randrange(50000, 200000)
b = random.randrange(50000, 200000)
x = gcd(a,b)
2.9 µs ± 105 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
Πολυπλοκότητα: $\mathcal{O}(\log{(min(x,y))})$
# Ελάχιστο κοινό πολλαπλάσιο
def lcm(x, y):
return x * y / gcd(x, y)
a, b = 30, 12
print(gcd(a, b), lcm(a, b))
6 60.0