ünite 5 · Klasik Algoritmalar
·
ders 5.2
EBOB: Öklid algoritması
İki bin yıllık algoritma: büyüğü küçüğe böl, kalanla devam et.
8 dk
17 / 22
tamamlandı
48 ve 18'in en büyük ortak böleni? Bölenleri listelemek yerine Öklid'in yolu: büyüğü küçüğe böl, kalan 0 olana kadar (küçük, kalan) ile devam et. Son sıfır olmayan kalan… değil, son bölen cevaptır.
48 mod 18 = 12
18 mod 12 = 6
12 mod 6 = 0 → EBOB = 6
Neden çalışır?
a ve b'yi bölen her sayı, a − b'yi ve kalanı da böler. Kalanla devam etmek problemi küçültür ama cevabı değiştirmez.
EKOK
En küçük ortak kat: a × b / EBOB(a, b). Bu yüzden EBOB'u bilen EKOK'u da bilir.
Bu algoritma iki sayıyı takas ederek ilerler: (a, b) → (b, a mod b). "Değişken ve atama" dersindeki takas kalıbı yine karşında.
akış şeması
elips: başla/bitir · dikdörtgen: işlem · paralelkenar: girdi/çıktı · baklava: karar
flowchart TD
A[/a, b oku/] --> B{b != 0 ?}
B -- Evet --> C[kalan = a mod b]
C --> D[a = b]
D --> E[b = kalan]
E --> B
B -- Hayır --> F[/a yaz/]
sözde kod
adımlar
1OKU a, b2İKEN b ≠ 03 kalan ← a MOD b4 a ← b5 b ← kalan6DÖNGÜ SONU7YAZ a
aynısı C# ile
C#
1int a = 48, b = 18;2while (b != 0)3{4 int kalan = a % b;5 a = b;6 b = kalan;7}8Console.WriteLine("EBOB: " + a);
adım adım izleme
Kutuların her adımdaki değeri. Kağıtta izleme tablosu tutarken tam bunu yaparsın.
| # | satır | a | b | not |
|---|---|---|---|---|
| 1 | a=48, b=18 → kalan 12 | 18 | 12 | (48,18) → (18,12) |
| 2 | a=18, b=12 → kalan 6 | 12 | 6 | (18,12) → (12,6) |
| 3 | a=12, b=6 → kalan 0 | 6 | 0 | (12,6) → (6,0) |
| 4 | b = 0 → YAZ a | 6 | · | EBOB = 6 |
senin sıran
EBOB(1071, 462)'yi elle izleme tablosuyla bul. Sonra iki kesri sadeleştiren algoritmayı yaz (pay ve paydayı EBOB'a böl).
kendini sına EBOB(a, 0) kaçtır?
a. Döngü hiç dönmez (b = 0), a yazılır. 0'ı her sayı böler, dolayısıyla en büyük ortak bölen a'nın kendisi.
tamamlandı
İşaret bu tarayıcıda kalır. XP için
giriş yap — her ders +15 XP.