Çatıdan Yumurta Atmak Zorunda Kaldığınızda: Günlük Kodlama Problemi

Günlük Kodlama Problemi 24

Çözülmesi gereken başka bir sorunla tekrar hoş geldiniz! Bugün, çatılardan düşen yumurtalarla uğraşıyoruz ve bu gerçekten güzel sorunla uğraşıyoruz ve bu sorun iki olası çözümü içeriyor: biri oldukça naif, diğeri daha zekice. Bu sonuncusu bize oldukça ünlü bir algoritmadan bahsetme fırsatı da verecek.

Her zaman olduğu gibi, bugünün sorunu harika haber bülteni tarafından sağlanıyor Günlük Kodlama Sorunu Günlük kodlama meydan okumanıza da katılmak için ücretsiz olarak abone olabileceğiniz. Bir göz atın ve sorunlarınızı da çözmeye çalışın!

O halde bu kadar konuşma yeter; soruna bakalım!

Sorun

Bu sorun Goldman Sachs tarafından bir iş görüşmesinde soruldu. Sorunu görelim.

Size N adet özdeş yumurta ve k katlı bir binaya erişim hakkı veriliyor . Göreviniz, bir yumurtanın o kattan düşmesi durumunda kırılmasına neden olacak en alt katı bulmaktır. Yumurta kırıldıktan sonra bir daha bırakılamaz. Eğer bir yumurta xth kattan bırakıldığında kırılıyorsa, x büyük herhangi bir kattan bırakıldığında da kırılacağını varsayabilirsiniz.

En kötü durumda bu katı belirlemek için gereken minimum deneme düşüşü sayısını bulan bir algoritma yazın.

Örneğin, N = 1 ve k = 5 ise, birinci kattan başlayarak beşinci kata ulaşana kadar her kata yumurta bırakmayı denememiz gerekecek, dolayısıyla çözümümüz 5 olacaktır.

Yani bize bir binanın farklı katlarından atmamız için bazı yumurtalar veriliyor. Belirli bir kattan (ki buna targetFloor diyeceğiz) dışarı atılan yumurtaların yere düştüğünde kırılmaması bizi üzüyor.

O kattan altındaki her kata kadar yumurtalar pencereden dışarı atıldığında kırılmaz. Bizden yapmamız istenen, targetFloor bulmak için etkili bir yöntem bulmamızdır.

Beklendiği gibi, bunu çözmek için iki yöntem göreceğiz: gerçekten basit bir yöntem, çözümü kaba kuvvetle ortadan kaldıracak, ancak verimli olmayacak. İkincisi çok daha verimli olacak ve sorunu en az sayıda adımı atarak çözmeye çalışacaktır.

Ayrıca bize gerçekten ünlü ve önemli bir algoritmadan bahsetme şansı da verecek; Yapmanız gerekenlerden biri… temelde her şey!

Ortamın Ayarlanması

Başlamak için, bina ve targetFloor gibi bir miktar ortam oluşturmamız gerekiyor. Binayı oluşturmak için, zemin kattan son kata kadar kat numaralarını içeren bir dizi oluşturmamız yeterlidir. Daha sonra targetFloor olacak rastgele bir sayı üretiyoruz.

Bu problemi Go'da bir kez daha yazacağız: okunabilecek kadar basit, ancak iç mekaniğini anlayacak kadar karmaşık.

Öncelikle binamız olarak hizmet verecek diziyi oluşturuyoruz: ona istediğimiz boyutu verebiliriz, boyut ne kadar büyük olursa bina o kadar yüksek olur. Bundan sonra Go'da yerleşik math/rand modülünü kullanarak targetFlor bir örneğini oluşturuyoruz.

Temel olarak, kaynak olarak geçerli zamanı kullanarak 0 ile binanın yüksekliği (… dizinin uzunluğu :D) arasında yeni bir rastgele tam sayı yaratırız.

Kaba Kuvvet Çözümü

Elbette mümkün olan en basit çözüm, her kattaki yumurtaları dışarı atmak, böylece yumurtaların hangi katta kırılmaya başladığını görmek olacaktır. Bu bilgiyi içeren bir değişkenimiz olduğundan, sorunu çözmek için basitçe for döngüsü yapılabilir:

Bu en basit çözüm olsa da ne yazık ki son derece verimsizdir. Sağ katın en üst kat olduğunu hayal edin: Sorunu çözmek için 100.000 yumurtanın kırılması gerekiyor: bu çok büyük bir omlet olur ama büyük bir israf olur!

Genel olarak konuşursak, bu çözümün zaman karmaşıklığı O(n)'dir çünkü çözümün karmaşıklığı girdi probleminin karmaşıklığına doğru doğrusal olarak artar. Ancak bu aklımıza gelen en etkili çözüm değil.

Etkili Bir Çözüm

O halde etkili bir çözüm düşünelim. Kat kat yürümek yerine her kattaki yumurtaları kırmak yerine bir tahminde bulunabilir ve bu tahminin sonucuna göre bir sonraki tahminimizi ayarlayabiliriz.

İşte bir örnek: Diyelim ki 10 katlı bir binamız var ve targetFloor kat 7. kat (bunu elbette bilmiyoruz). Şu tahminleri yapabiliriz:

Temel olarak targetFloor binanın orta katı olduğunu tahmin ediyoruz. Yumurtayı oradan atıyoruz ve olası sonuçlar iki:

• yumurta kırılır, bu da çok yüksekte olduğumuz anlamına gelir. Bundan daha üstteki katı da dahil edip, tahminlerimize devam edebiliriz.

• Yumurta kırılmaz, bu da çok alçakta olduğumuz veya doğru katta olduğumuz anlamına gelir. Bundan daha alttaki her katı atıyoruz, buna dahil, ve

Bunu göz önünde bulundurarak, şimdi orta kat veya "kalan" bina hakkında başka bir bilinçli tahminde bulunuyoruz ve yukarıda görülen stratejinin aynısını uyguluyoruz. Bir kat kalana kadar bu yaklaşımı sürdürebiliriz.

Bu yaklaşımın farkındaysanız tamamen haklısınız: Bu sadece "gerçek dünya" problemine uygulanan ikili bir aramadır . İkili arama, basit ve düzgün bir böl ve yönet algoritmasıdır; bu, çözümü bulana kadar her adımda sorunun boyutunun yarıya indirilmesi anlamına gelir.

Bu, öncekiyle karşılaştırıldığında bu algoritmanın çok daha hızlı olduğu anlamına gelir. Kodu görelim!

Daha derinlemesine bir göz atalım. İkili arama işlevi 4 bağımsız değişken alır:

• overArray , üzerinde döngü yaptığımız bina olan bir tamsayı dizisi;

• bottom , binanın alt endeksi;

• top , binanın en üst kat indeksi;

• breakFloor , onu binada bulup bulamayacağımızı kontrol etmek için targetFloor tutan değişken.

Bundan sonra, bottom top kısımdan aşağıdayken binanın üzerinde döngü yaparız: ikili aramada, iki konumsal argüman iç içe geçtiğinde ve yer değiştirdiğinde, aranan öğenin bulunmadığı anlamına gelir.

Dolayısıyla algoritma bu duruma düşerse döngü biter ve -1 değerini döndürürüz, yani aradığımız eleman dizide yoktu. Eğer hala eleman arıyorsak yukarıdaki resimde gösterileni uyguluyoruz.

middlePoint elemanını bottom ve top arasındaki zemin olarak hesaplıyoruz ve middlePoint == breakFloor olup olmadığını kontrol ediyoruz. Eğer öyleyse, sonuç olarak middlePoint döndürürüz.

Değilse, bottom veya top buna göre ayarlıyoruz: Eğer middlePoint breakFloor büyükse, bu, binada çok yüksekte olduğumuz anlamına gelir, dolayısıyla mümkün olan top katı middlePoint — 1 olarak ayarlayarak tahminimizi düşürürüz.

Eğer middlePoint breakFloor küçükse is middlePoint+1 olarak ayarlayarak bottom ayarlıyoruz.

Şimdi her şeyi kontrol etmek için, main fonksiyonda, daha önce olduğu gibi ortamı oluşturuyoruz ve sonucumuzu tutacak bsFloor adında yeni bir değişken yaratıyoruz.

Algoritmamızın bizi doğru sonuca getirdiğini doğrulamak için hem bsFloor hem de daha önce rastgele oluşturulmuş olan targetFloor çıktısını alıyoruz.

Zaman Karmaşıklığı

Daha önce de tahmin ettiğimiz gibi bu algoritma doğrusal olandan çok daha hızlıdır. Her adımda binayı yarıya indirdiğimiz için, n'nin len(building) ya eşit olduğu log₂(n) cinsinden doğru katı bulabiliriz.

Bu, bu algoritmanın zaman karmaşıklığının O(log(n)) olduğu anlamına gelir. Doğrusal çözüm ile bu sonuncusu arasında bir karşılaştırma yapmak gerekirse, eğer bina 100 katlıysa, doğrusal algoritma en kötü durumda 100 yineleme alırken, ikili arama algoritması log₂100 = 6,64, yani 7 yineleme alır.

Ayrıca bu sonuncusu doğrusal olandan giderek daha verimli hale geliyor çünkü bina ne kadar büyürse ikili arama da o kadar verimli oluyor. 1.000.000.000 katlı bir bina için doğrusal olan 1.000.000.000 adım alırken ikili olan log₂1.000.000.000 = 29,9 yani 30 adım alır. Çok büyük bir gelişme!

Çözüm

Budur! Umarım benim bu sorunu çözmeye çalışırken eğlendiğim kadar siz de makaleden keyif aldınız! Eğer öyleyse, lütfen bir veya iki alkış bırakın, bu harika bir destek olur! Bu tür yazıları seviyorsanız ve daha fazlasını görmek istiyorsanız, elimden geldiğince bu tür içerikleri yayınladığım sayfayı takip edin.

Son olarak, eğer bu makaleyi ilginç veya faydalı bulduysanız ve bir kahve ikram ederek katkıda bulunmak istiyorsanız, bunu benim adresimden yapabilirsiniz. Ko-fi sayfa!

Ve her zamanki gibi okuduğunuz için teşekkürler!

Nicola

Burada da yayınlandı