GCD, LCM ve Öklid Algoritması
Bölenleri hızlı ve doğru biçimde hesaplayın.
GCD, LCM ve Öklid Algoritması, CoddyKit'te ücretsiz bir Competitive Programming Academy dersidir. Bu, 4 dersinin 1. dersidir. Aşağıdan dersin tamamını ücretsiz okuyabilir, sonra tarayıcıda yerleşik kod editörü ve 7/24 yapay zeka koçu ile uygulamalı olarak pratik yapabilirsin. Bu, Competitive Programming Academy öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. Competitive Programming Academy kursu toplamda 4 dersten oluşur.
Bölenler Neden Önemlidir
Yarışma sorularının çoğu iki sayının ortak çarpanlarına dayanır. Buradaki en yararlı araç, en büyük ortak bölen olan GCD'dir. 🔢
GCD Ne Anlama Gelir
İki tam sayının GCD'si, her ikisini de kalan bırakmadan bölen en büyük sayıdır. 12 ve 18 için bu sayı 6'dır; çünkü 6, ikisini de kalansız böler.
Yavaş Yöntem
Küçük olan değerden başlayarak aşağı doğru her sayıyı, ikisini de bölene kadar sınayabilirsiniz. Bu yöntem çalışır; ancak büyük girdiler için fazlasıyla yavaştır.
Öklidci Bakış Açısı
Öklid algoritması hızlı yöntemdir. Temel fikir şudur: a ve b'nin GCD'si, b ile a'nın b'ye bölümünden kalanın GCD'sine eşittir.
Yineleme
Kalan sıfıra ulaşana kadar değiştirme ve mod adımını tekrarlayın. Geriye kalan son sıfır olmayan değer yanıtınızdır; yani GCD'nin kendisidir.
gcd(a, b) = gcd(b, a % b)
gcd(a, 0) = aKodu Kendiniz Yazın
Kısa bir döngü, b sıfıra ulaşana kadar çifti sürekli değiştirir. Bu işlem yaklaşık log adımda tamamlanır; çok büyük sayılarda bile son derece hızlıdır.
def gcd(a, b):
while b:
a, b = b, a % b
return aStandart Kütüphaneyi Kullanın
Bunu nadiren kendiniz yazmanız gerekir. Python, doğru ve hızlı olan, ayrıca sıfır bağımsız değişkenlerini sizin için ele alan math.gcd işlevini sağlar.
from math import gcd
print(gcd(12, 18))GCD'den LCM'ye
LCM, yani en küçük ortak kat, her iki değerin de böldüğü en küçük sayıdır. Az önce hesapladığınız GCD ile doğrudan bağlantılıdır.
LCM Formülü
İki sayıyı çarpın, ardından GCD'lerine bölün. Çok büyük çarpımlarda taşmayı önlemek için her zaman önce bölme işlemini yapın.
def lcm(a, b):
return a // gcd(a, b) * bBütün Bir Listenin GCD'si
Birçok sayı üzerinde GCD işlemini uygulamak için sayıları ikişerli olarak zincirleyin. Python'daki katlama işlevi, math.gcd'yi liste üzerinde soldan sağa uygular.
from functools import reduce
from math import gcd
g = reduce(gcd, nums)Sıfır Durumunu Ele Alın
Tanım gereği gcd(a, 0), a'ya eşittir ve gcd(0, 0) 0'dır. Bu sınır durumunu bilmek, döngülerinizin boş girdide hatalı çalışmasını önler.
Hızlı Kontrol
Temel Öklid adımını doğrulama zamanı.
Özet
Artık Öklid algoritmasıyla GCD'yi log adımda hesaplayabilir, buradan LCM'yi türetebilir ve her ikisini de bir liste üzerinde uygulayabilirsiniz. ✅
Sıkça Sorulan Sorular
“GCD, LCM ve Öklid Algoritması” dersi ücretsiz mi?
Evet — “GCD, LCM ve Öklid Algoritması” dersin tüm metni burada web'de ücretsiz olarak okunabilir. Etkileşimli olarak pratik yapmak (yerleşik kod editörü ve 7/24 yapay zeka koçu) ve Competitive Programming Academy kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. Competitive Programming Academy kursu toplamda 4 dersten oluşur.
“GCD, LCM ve Öklid Algoritması” dersinde ne öğreneceğim?
Bölenleri hızlı ve doğru biçimde hesaplayın. Competitive Programming Academy ile uygulamalı kodu tarayıcıda doğrudan çalıştırarak pratik yaparsın ve 7/24 yapay zeka koçu dersi çalışırken sorularını yanıtlar.
Competitive Programming Academy öğrenmeye başlamak için deneyim gerekli mi?
Önceden deneyim gerekmez. CoddyKit'te Competitive Programming Academy, başlangıçtan ileri seviyeye kadar yapılandırıldığı için buradan başlayabilir veya başından başlayıp kendi hızında ilerleme yapabilirsin. Bu, 4 dersinin 1. dersidir.
“GCD, LCM ve Öklid Algoritması” dersi ne kadar sürer?
Çoğu CoddyKit dersi yaklaşık 5–10 dakika sürer. Her biri kısa ve etkileşimli olduğu için sabit ilerleme yaparsın ve web ile uygulama arasında tam olarak bıraktığın yerden devam edebilirsin.
Bu Competitive Programming Academy dersinde kod yazıp çalıştırabilir miyim?
Evet. Her Competitive Programming Academy dersi yerleşik bir kod editörü içerir, bu sayede tarayıcıda gerçek kod yazıp çalıştırabilir ve anlık yapay zeka geri bildirimi alırsın — yerel kurulum gerekli değildir.
Bu kursun tüm dersleri
- GCD, LCM ve Öklid Algoritması
- sqrt(n)'ye Kadar Asallık Testi
- Eratosthenes Eleği
- Asal Çarpanlara Ayırma ve Bölenler