Komik: Klasik Google röportaj sorusu "yumurta fırlat", bakalım yapabilecek misin?
sonraki gün
Konu: Yumurta fırlatma sorunu
Yumurtaların sertliğini test etmek için 100. kattan atılmış 2 yumurta vardır. Örneğin yumurta 9. katmanda kırılmamış ancak 10. katmanda kırılmışsa yumurtanın kırılmayacağı kritik nokta 9. katmandır.
Soru: Yumurtanın kırılmayacağı kritik noktayı test etmek için en az sayıda deneme nasıl kullanılır?
Örneğin, en aptalca test yöntemi nedir? İlk katmandaki yumurtalardan birini aşağı atın. Birinci katmanda kırılmamışsa, ikinci katmanı değiştirip at, ikinci katmanda kırılmamışsa üçüncü katmanı değiştir ve at ... 59. kat kırık değilse 60. katmana geç ve at; 60. kat kırılırsa kırılmayacak kritik nokta 59. kattır.
En kötü durumda, bu yöntem 100 atış gerektirir.
Yöntem 1: İkili
İkili aramaya benzer bir yöntem kullanarak, yumurtaları zeminin yarısından (50. kat) aşağıya atın.
İlk yumurta 50. katta kırılırsa, ikinci yumurta birinci tabakadan fırlatılır ve 49. tabakaya ulaşana kadar tabaka tabaka büyür.
İlk yumurta 50. katta kırılmazsa, ikilemi kullanmaya devam edin ve kalan katların yarısına (75. kat) atın ...
En kötü durumda bu yöntemin 50 defa denenmesi gerekir.
Yöntem 2: Karekök Yöntemi
İlk yumurtanın ve ikinci yumurtanın deneme sayısı olabildiğince dengeli nasıl yapılır?
Çok basit, bir karekök işlemi yapın, 100'ün karekökü 10'dur.
Bu nedenle, her 10 katta bir, ilk kez 10. kattan, ikinci kez 20. kattan, üçüncü kez 30. kattan 100. kata kadar atmaya çalışıyoruz.
Bunun gibi en iyi durum 10. katta bozulur ve deneme sayısı 1 + 9 = 10 katıdır.
En kötü durum 100. katta bozulur, deneme sayısı 10 + 9 = 19 kezdir.
Ancak burada ufak bir optimizasyon noktası var .. 15. kattan başlayıp sonra 25. ve 35. katlardan 95. kata kadar ... atmaya başlayabiliriz.
Bu durumda en kötü durum 95. katta bozulur ve deneme sayısı 9 + 9 = 18 kezdir.
Optimal deneme sayısının x katı olduğunu varsayarsak, neden ilk atış için x'inci katman seçilsin?
Buradaki açıklama biraz beyin yakacak, bu yüzden lütfen oturun ve onunla ilgilenin:
İlk atışın x + 1. katmanda olduğunu varsayalım:
İlk yumurta kırılırsa, ikinci yumurta ancak birinci tabakadan başlayarak x. Tabakaya kadar atılabilir.
Bu şekilde toplamda x + 1 kez denedik ki bu x kez denediğimiz varsayımına aykırı. İlk defa atılan katın x + 1 kattan az olması gerektiği görülebilir.
İlk atışın x-1. Katmanda olduğunu varsayalım:
İlk yumurta kırılırsa, ikinci yumurta ancak birinci katmandan x-2 katmanına kadar katman katman atılabilir.
Bu şekilde toplamda x-2 + 1 = x-1 kez denedik, varsayım sayısını aşmasa da biraz fazla muhafazakar göründü.
İlk atışın x. Katmanda olduğunu varsayalım:
İlk yumurta kırılırsa, ikinci yumurta sadece birinci katmandan x-1 katmanına kadar katman katman atılabilir.
Bu şekilde, toplamda x-1 + 1 = x kez denedik, bu sadece varsayımların sayısını aşmadı.
Bu nedenle, taban aralığını olabildiğince genişletmek ve x deneme sayısının aşılmamasını sağlamak istiyorsanız, o zaman ilk yumurta atışı için en iyi seçenek x'inci kattır.
Yöntem 3: Denklem yöntemi çözme
x + (x-1) + (x-2) + ... + 1 = 100
Bu denklemi anlamak zor değil:
Soldaki polinom, her bir yumurta atışının taban açıklığının toplamıdır. X kez denendiği varsayıldığından, bu polinomun toplamda x terimi vardır.
Sağdaki toplam kat sayısı 100'dür.
Bu denklemi aşağıdaki çözelim:
x + (x-1) + (x-2) + ... + 1 = 100,
(x + 1) * x / 2 = 100
Sonunda x, x = 14 elde etmek için yukarı yuvarlanır
Dolayısıyla en kötü durumda optimal çözüm için deneme sayısı 14 kat, ilk yumurtanın atıldığı kat da 14 kattır.
Son olarak, ilk yumurta kırılmadığında denenen kat sayısını sıralayalım:
14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100
Bir kestane doğrulaması yapın:
Yumurtanın kırılmadığı kritik nokta 65. kat ise ilk yumurtanın atıldığı kat 14, 27, 50, 60, 69'dur. Bu sefer bir çırpıda kırıldı.
İkinci yumurta 61, 61, 62, 63, 64, 65, 66. tabakadan başlayarak devam etti ve bir çırpıda kırıldı.
Böylelikle kritik noktanın kırılmayacak 65 katı elde edilmiş olup, toplam deneme sayısı 6 + 6 = 12'dir. < 14.
Sorumluluk Reddi: Bu makale yazar "Programcı Xiaohui" tarafından sunulmuştur ve telif hakkı orijinal yazara aittir.
Belgeler için arayın!
CSDN kamu hesabı, "on milyonlarca teknik insanla büyüme" kavramını destekler. Teknik insanların ilk kez ilgilendiği endüstri odak olaylarını teknik insanların benzersiz bakış açılarından açıklamak için yalnızca "inek başlıkları" ve "konuşma" sütunlarını kullanmakla kalmaz, aynı zamanda "Teknik Başlıklar" sütunu, sektördeki popüler teknolojilerin ve uygulamaların derinlemesine bir yorumunu sunarak, tüm geliştiricilerin teknolojik trendlere ayak uydurmasına, uyanık bir teknolojik anlayışı sürdürmesine ve sektör eğilimleri ve teknolojileri hakkında daha kapsamlı bir anlayışa sahip olmasına olanak tanır.
Yüksek kaliteli makaleleriniz veya endüstrinin sıcak olayları, teknoloji trendleri hakkında içgörüler veya derinlemesine uygulama uygulamaları, senaryolar vb. Hakkında yeni içgörüleriniz varsa, lütfen gönderimler için CSDN ile iletişime geçin. İletişim: WeChat (guorui_1118, lütfen gönderim + ad + şirket pozisyonunu not edin), e-posta (guorui@csdn.net).
