İçeriğe geç

EBOB ve Öklid

Ders 2 / 5 · 4 dk

EBOB ve Öklid

Adım 1/7

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 a

Mini quiz

1 / 3

Öklid algoritmasında döngüyü ne durdurur?