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 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!   Günlük Kodlama Sorunu  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   adet özdeş yumurta ve   katlı bir binaya erişim hakkı   . 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   kattan bırakıldığında kırılıyorsa,   büyük herhangi bir kattan bırakıldığında da kırılacağını varsayabilirsiniz. N k veriliyor xth x   En kötü durumda bu katı belirlemek için gereken minimum deneme düşüşü sayısını bulan bir algoritma yazın.      ve   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   olacaktır. Örneğin, N = 1 k = 5 5  Yani bize bir binanın farklı katlarından atmamız için bazı yumurtalar veriliyor. Belirli bir kattan (ki buna   diyeceğiz) dışarı atılan yumurtaların yere düştüğünde kırılmaması bizi üzüyor. targetFloor  O kattan altındaki her kata kadar yumurtalar pencereden dışarı atıldığında kırılmaz. Bizden yapmamız istenen,   bulmak için etkili bir yöntem bulmamızdır. targetFloor  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   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   olacak rastgele bir sayı üretiyoruz. targetFloor targetFloor  Bu problemi Go'da bir kez daha yazacağız: okunabilecek kadar basit, ancak iç mekaniğini anlayacak kadar karmaşık.   https://Gist.github.com/NicolaM94/85ae34f01e7de8cd00264276b385e137?embedable=true#file-main-go  Ö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   modülünü kullanarak   bir örneğini oluşturuyoruz. math/rand targetFlor  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:   https://Gist.github.com/NicolaM94/dd49b3b44a8938c40d0539512fd613cb?embedable=true#file-main-go  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   kat 7. kat (bunu elbette bilmiyoruz). Şu tahminleri yapabiliriz:  targetFloor  Temel olarak   binanın orta katı olduğunu tahmin ediyoruz. Yumurtayı oradan atıyoruz ve olası sonuçlar iki: targetFloor  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   . İkili arama, basit ve düzgün bir   algoritmasıdır; bu, çözümü bulana kadar her adımda sorunun boyutunun yarıya indirilmesi anlamına gelir. ikili bir aramadır böl ve yönet  Bu, öncekiyle karşılaştırıldığında bu algoritmanın çok daha hızlı olduğu anlamına gelir. Kodu görelim!   https://Gist.github.com/NicolaM94/79d625ecef07cb26a7a8d9bcdb6143fd?embedable=true#file-main-go  Daha derinlemesine bir göz atalım. İkili arama işlevi 4 bağımsız değişken alır:    , üzerinde döngü yaptığımız bina olan bir tamsayı dizisi; overArray    , binanın alt endeksi; bottom    , binanın en üst kat indeksi; top    , onu binada bulup bulamayacağımızı kontrol etmek için   tutan değişken. breakFloor targetFloor  Bundan sonra,     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. bottom top  Dolayısıyla algoritma bu duruma düşerse döngü biter ve   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. -1    elemanını   ve   arasındaki zemin olarak hesaplıyoruz ve   olup olmadığını kontrol ediyoruz. Eğer öyleyse, sonuç olarak   döndürürüz. middlePoint bottom top middlePoint == breakFloor middlePoint  Değilse,   veya   buna göre ayarlıyoruz: Eğer     büyükse, bu, binada çok yüksekte olduğumuz anlamına gelir, dolayısıyla mümkün olan   katı   olarak ayarlayarak tahminimizi düşürürüz. bottom top middlePoint breakFloor top middlePoint — 1  Eğer     küçükse is   olarak ayarlayarak   ayarlıyoruz. middlePoint breakFloor middlePoint+1 bottom  Şimdi her şeyi kontrol etmek için,   fonksiyonda, daha önce olduğu gibi ortamı oluşturuyoruz ve sonucumuzu tutacak   adında yeni bir değişken yaratıyoruz. main bsFloor  Algoritmamızın bizi doğru sonuca getirdiğini doğrulamak için hem   hem de daha önce rastgele oluşturulmuş olan   çıktısını alıyoruz. bsFloor targetFloor  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   ya eşit olduğu log₂(n) cinsinden doğru katı bulabiliriz. len(building)  Bu, bu algoritmanın zaman karmaşıklığını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. O(log(n))  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.  sayfa!   Ko-fi  Ve her zamanki gibi okuduğunuz için teşekkürler!   Nicola    da yayınlandı Burada

Read My Stories

Bu ses hikayenin orijinal dilinde üretilmiştir!

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

About Author

YORUMLAR

ETİKETLERİ ASIN

BU YAZI

Related Stories

Kullanıcı Odaklı Kripto Ürünleri Oluşturma: Müşteri Geri Bildiriminin Önemi

Bu 18 Geliştirici Aracıyla Üretkenliğinizi Artırın 🚀🔥

Floki'den Valhalla Hindistan'ın Sri Lanka Turuna Yardımcı Sponsor Olarak Katıldı

AI/ML Datalake için Referans Mimarisi Oluşturmaya Yönelik Mimar Kılavuzu

Kullanıcı Odaklı Kripto Ürünleri Oluşturma: Müşteri Geri Bildiriminin Önemi

Bu 18 Geliştirici Aracıyla Üretkenliğinizi Artırın 🚀🔥

Floki'den Valhalla Hindistan'ın Sri Lanka Turuna Yardımcı Sponsor Olarak Katıldı

AI/ML Datalake için Referans Mimarisi Oluşturmaya Yönelik Mimar Kılavuzu

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps