EBOB ve Öklid
Adım 1/7
a48b18
a48
b18
En büyük ortak bölen, yani EBOB (GCD), iki uzunluğu da tam ölçen en uzun cetvel.
Fikir
EBOB (GCD), yani en büyük ortak bölen, iki sayıyı da tam ölçen en uzun cetveldir.
Kısa uzunluğu uzun olanın üzerine yatır. Taşan kısım da aynı cetvelle ölçülebilmeli; bu yüzden gcd(a, b), gcd(b, a % b) olur. Çift birkaç bölmede çöker ve kalan sıfır olduğunda cevap ortadadır.
Gerçek hayattan örnek
Video araçları en-boy oranlarını sadeleştirmek için bunu kullanır: 1920×1080'in EBOB'u 120'dir; "16:9" etiketi de böyle ortaya çıkar. Aynı sadeleştirme, kayan noktalı sayıların sapacağı yerlerde, yani yerleşim motorlarında ve faturalama kodunda kesirleri düzenli tutar.
Kod
Sıra sende
Boşluğu doldur.
def gcd(a, b):
while b:
a, b = b, ___
return aMini quiz
1 / 3