0Pricing
Competitive Programming Academy · Ders

Yanıt Üzerinde İkili Arama

Sonucu tahmin edin ve uygulanabilirliğini denetleyin.

Yanıt Üzerinde İkili Arama, CoddyKit'te ücretsiz bir Competitive Programming Academy dersidir. Bu, 4 dersinin 4. 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.

Tahmin Edin, Sonra Doğrulayın

Bazen yanıtı doğrudan hesaplayamazsınız, ancak bir tahmini kontrol edebilirsiniz. Yanıt üzerinde ikili arama yapmak, zor bir optimizasyonu kolay bir kontrole dönüştürür.

# guess X, ask: is X feasible?

Sihirli Özellik

Bu yöntem, uygulanabilirlik monoton olduğunda çalışır: bir değer işe yarıyorsa, daha büyük veya daha küçük her değer de işe yarar. Aradığınız şey bu sıralamadır.

# feasible(X) true => feasible(X+1) true

Yanıt Aralığını Sınırlayın

Mümkün olan en küçük ve en büyük yanıtları low ve high olarak belirleyin. En küçük kapasite için low bir öğe, high ise toplamdır.

low, high = max(weights), sum(weights)

Uygulanabilirlik Kontrolünü Yazın

Yöntemin özü, X tahmininin gerçekleştirilebilir olması durumunda true döndüren bir can(X) işlevidir. Bu işlev genellikle doğrusal zamanda çalışır.

def can(cap):
    # simulate and return True/False
    ...

Örnek: D Günde Gönderim

Günlük kapasite cap verildiğinde, günleri açgözlü biçimde doldurun ve gün sayısını hesaplayın. Gün sayısı D sınırı içinde kaldığında can(cap) true olur.

def can(cap):
    days, load = 1, 0
    for w in weights:
        if load + w > cap:
            days += 1; load = 0
        load += w
    return days <= D

En Küçük Kapasiteyi Arayın

Koşulu sağlayan en küçük cap değerini istiyorsunuz. Bu, kapasiteler üzerinde yapılan bir ilk-true aramasıdır; high = mid şablonunu yeniden kullanın.

while low < high:
    mid = (low + high) // 2

Uygun Yarısını Koruyun

can(mid) true ise daha küçük bir kapasite de işe yarayabilir; bu nedenle high = mid yapın. Aksi hâlde low = mid + 1 ile alt sınırı yükseltin.

if can(mid):
    high = mid
else:
    low = mid + 1

Zaman Bütçesine Dikkat Edin

Toplam maliyet O(check x log range) olur. Bir milyar genişliğindeki bir aralık üzerinde yapılan doğrusal bir kontrol yalnızca yaklaşık 30 kontroldür; sıkı sınırlar için yeterince hızlıdır.

# log2(1e9) is about 30 iterations

En Küçüğü Değil, En Büyüğü En Üst Düzeye Çıkarın

En büyük uygulanabilir değeri bulmak için mantığı tersine çevirin: son true değerini arayın. Uygun olduğunda low değerini yükseltin, uygun olmadığında high değerini azaltın.

if can(mid):
    low = mid
else:
    high = mid - 1

Gerçek Değerli Yanıtlar

Ondalıklı yanıtlar için integer mid kullanmak yerine 100 kez gibi sabit sayıda döngü çalıştırın. Her tur aralığı ikiye böler ve kısa sürede çok yüksek hassasiyete ulaşırsınız.

for _ in range(100):
    mid = (low + high) / 2

Kalıbı Fark Etmek

En büyük olanın en küçüğü, en küçüğün en büyüğü veya işe yarayan en küçük k gibi ifadeler, yanıt üzerinde ikili arama yapmak için işaretlerdir. Bu ifadeleri fark etmeye alışın.

# 'minimize the maximum' => search answer

Hızlı Kontrol

Yanıt üzerinde ikili aramanın ne zaman uygulanabileceğine karar verin.

Özet: Yanıtı Arayın

Artık yanıtı sınırlayabilir, bir uygulanabilirlik kontrolü yazabilir ve en küçüğü veya en büyüğü bulmak için ikili arama yapabilirsiniz. Zor problemler tahmin etme ve doğrulamaya dönüşür. 🏆

Sıkça Sorulan Sorular

“Yanıt Üzerinde İkili Arama” dersi ücretsiz mi?

Evet — “Yanıt Üzerinde İkili Arama” 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.

“Yanıt Üzerinde İkili Arama” dersinde ne öğreneceğim?

Sonucu tahmin edin ve uygulanabilirliğini denetleyin. 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 4. dersidir.

“Yanıt Üzerinde İkili Arama” 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

  1. Hatasız Klasik İkili Arama
  2. bisect_left ve bisect_right
  3. İlk True: Predicate İkili Araması
  4. Yanıt Üzerinde İkili Arama
← Competitive Programming Academy Sayfasına Dön