En Küçük Ortak Kat (EKOK) Algoritması

Matematiksel problemlerde iki veya daha fazla sayının En Küçük Ortak Katı (EKOK)‘unu bulmak, sık karşılaşılan bir durumdur. Bu yazıda, EKOK’un ne olduğunu, nasıl hesaplandığını ve farklı yöntemlerle EKOK bulma algoritmalarını inceleyeceğiz. Ayrıca örneklerle EKOK hesaplamasını detaylandıracağız.

EKOK Nedir?

En Küçük Ortak Kat (EKOK), iki ya da daha fazla sayının her ikisinin de tam olarak bölünebildiği en küçük sayıdır. Diğer bir ifadeyle, iki sayının ortak katlarının en küçüğüdür. Örneğin, 12 ve 15 sayılarının EKOK’u 60’tır, çünkü her iki sayı da 60’a tam bölünebilir ve bu, onların ortak katları arasında en küçük olanıdır.

12’nin katları: 12, 24, 36, 48, 60, 72, 84, …
15’in katları: 15, 30, 45, 60, 75, 90, 105, …

Ortak katlar: 60, 120, 180, …
Bu durumda en küçük ortak kat 60’tır.

EKOK Hesaplama Algoritmaları

EKOK’u bulmak için kullanılan birkaç yöntem vardır. Şimdi bu yöntemlere ve algoritmalarına göz atalım.

1. Yöntem: Çarpanlara Ayırma Yöntemi

Bu yöntemde, iki sayıyı asal çarpanlarına ayırırız ve her iki sayının da tüm asal çarpanlarının en büyük kuvvetlerini alırız. Bu çarpanları birbiriyle çarptığımızda EKOK elde edilir.

Örneğin, 12 ve 15 sayılarının EKOK’unu bulalım:

• 12 = 2² * 3
• 15 = 3 * 5

EKOK’u bulmak için her asal çarpanın en büyük kuvvetlerini alıyoruz:

• 2²
• 3¹
• 5¹

EKOK = 2² * 3¹ * 5¹ = 60.

Bu yöntem, küçük sayılar için işe yarasa da, büyük sayılar için zaman alıcı olabilir.

2. Yöntem: EBOB Kullanarak EKOK Hesaplama

EKOK’u bulmanın en etkili yollarından biri, EBOB (En Büyük Ortak Bölen) kullanarak hesaplama yapmaktır. Bu yöntemin temel formülü şu şekildedir:

 

$EKOK(a, b) = \frac{a \times b}{EBOB(a, b)}$

​

Bu formüle göre önce EBOB’u buluruz ve ardından bu formülü kullanarak EKOK’u hesaplarız. EBOB’u bulmak için daha önce öğrendiğimiz Öklid Algoritması kullanılabilir.

def ebob(a, b):
while b != 0:
a, b = b, a % b
return a

def ekok(a, b):
return (a * b) // ebob(a, b)

Bu algoritma, önce EBOB’u bulur, ardından verilen iki sayının çarpımını EBOB’a bölerek EKOK’u hesaplar.

Zaman Karmaşıklığı: Bu yöntemin zaman karmaşıklığı, EBOB hesaplamasına bağlıdır ve genellikle O(log min(a, b))‘dir.

3. Yöntem: Döngü Kullanarak EKOK Bulma

Bir diğer yöntem de, iki sayının ortak katlarını kontrol eden bir döngü kullanmaktır. Bu yöntemde, küçük sayıdan başlayarak her iki sayıya da tam bölünen ilk sayıyı bulduğumuzda EKOK’a ulaşmış oluruz.

def ekok_dongu(a, b):
max_val = max(a, b)
while True:
if max_val % a == 0 and max_val % b == 0:
return max_val
max_val += 1

Bu yöntem, sayılar arasındaki ortak katları taradığı için basit bir yaklaşımdır ancak büyük sayılar için çok verimli değildir.

Zaman Karmaşıklığı: Bu yöntem en kötü durumda O(a * b) zaman karmaşıklığına sahiptir, bu da büyük sayılar için verimsiz olabilir.

Örneklerle EKOK Hesaplama

Örnek 1: 12 ve 15 Sayılarının EKOK’u

12 ve 15 sayılarının EKOK’unu EBOB kullanarak bulalım:

1. EBOB(12, 15):
   • 12 % 15 = 12.
   • 15 % 12 = 3.
   • 12 % 3 = 0.

Sonuç: EBOB(12, 15) = 3.

2. EKOK(12, 15) = (12 * 15) / 3 = 180 / 3 = 60.

Sonuç: EKOK(12, 15) = 60.

Örnek 2: 18 ve 24 Sayılarının EKOK’u

ekok(18, 24)

1. EBOB(18, 24):
   • 18 % 24 = 18.
   • 24 % 18 = 6.
   • 18 % 6 = 0.

Sonuç: EBOB(18, 24) = 6.

2. EKOK(18, 24) = (18 * 24) / 6 = 432 / 6 = 72.

Sonuç: EKOK(18, 24) = 72.

Zaman Karmaşıklığı Karşılaştırması

Yöntem	Zaman Karmaşıklığı	Bellek Kullanımı
Çarpanlara Ayırma Yöntemi	O(√n)	O(1)
EBOB Kullanarak EKOK	O(log min(a, b))	O(1)
Döngü Kullanarak EKOK	O(a * b)	O(1)

• Çarpanlara ayırma yöntemi, küçük sayılar için uygundur ancak büyük sayılar için hesaplamalar zorlaşır.
• EBOB kullanarak EKOK bulma yöntemi en etkili yoldur ve büyük sayılarla çalışırken hızlı sonuçlar verir.
• Döngü yöntemi, basit bir yaklaşım olmasına rağmen büyük sayılar için yavaş çalışabilir.

EKOK’un Gerçek Hayattaki Kullanım Alanları

1. Zamanlama ve Programlama: İki farklı olayın ne zaman birlikte gerçekleşeceğini hesaplamak için EKOK kullanılır. Örneğin, biri 12 saniyede, diğeri 15 saniyede bir gerçekleşen iki olayın aynı anda ne zaman gerçekleşeceğini bulmak için EKOK kullanılır.
2. Elektronik Devreler: Elektrik devrelerinde iki farklı frekansta çalışan sistemlerin senkronizasyonu için EKOK kullanılır.
3. Matematiksel Modelleme: Sayı teorisinde ve cebirsel problemlerle uğraşırken EKOK önemli bir rol oynar.

Sonuç

EKOK, iki veya daha fazla sayının en küçük ortak katını bulmak için kullanılan temel matematiksel bir kavramdır. Farklı algoritmalarla hesaplanabilen EKOK, özellikle EBOB kullanarak hesaplama yöntemi sayesinde büyük sayılar için bile hızlı ve etkili bir şekilde bulunabilir. EKOK, matematiksel modelleme, zamanlama problemleri ve elektronik sistemlerde sıkça kullanılan bir araçtır.