İki Yumurta Problemi (The Two Egg Problem)
İki Yumurta Problemi (The Two Egg Problem)
n Katlı bir binadayız ve elimizde iki adet yumurtamız bulunuyor. Yumurtalar binanın x. katından atıldığı zaman kırılmıyor, x ve üzeri katlarınan atılınca kırılıyor. Yumurta kırılmadığı sürece tekrar tekrar kullanılabiliyor. En az kaç atışta yumurtanın kırılmaya başladığı katı bulabiliriz?
Çözüm Yöntemleri
Çözüm Yöntemi 1
1. Kattan başlarız ve ilk nerede kırıldıysa x o olur.
En durumda ilk katta kırılırsa tek atışta bulunur, en kötü durumda ise en üst katta bulunuyorsa n-1 atışta bulunur.
Çözüm Yöntemi 2
İlk yumurtayı orta kattan atarız, kırıldıysa 2. yumurtayı 1. kattan başlayıp yukarı doğru kırılana kadar atarız.
Yumurta kırılmadıysa n/2 ile n arasındaki katlarda kırılıyor demektir. Bu katların ortasından atış yapıyoruz (3* n / 4) ve böyle devam ediyoruz. (Bu mantığa Binary Search deniyor.)
Bu yöntemin en kötü durumu ise yumurtanın n/2-1 katta kırılmasıdır.
İdeal Çözüm Yöntemi
Yukarıdaki çözüm yöntemleri ile çok kısa hamlelerde bulabilme imkanımız olmasın rağmen çok uzun süren bir süreçte çok fazla deneme ile de bulma ihtimalimiz bulunuyor. Ancak 100 katlı bir binada 14 hamlede (Atışta) nerede kırıldığı bulunabiliyor.
Gelin bunun nasıl yapıldığını açıklayalım.
14. kattan yumurtamızı atalım, ilk atış hakkını kullanmış olduk. (13 Hamle Kaldı)
Kırılırsa 1. kattan 13. kata kadar tek tek deniyoruz.
Kırılmazsa 14 + 13 yapıp 27. kattan yumurtamızı atıyoruz. (12 Hamle Kaldı)
Kırılırsa 15. kattan 26. kata kadar tek tek deniyoruz.
Kırılmazsa 14+13+12 yapıp 39. kattan yumurtamızı atıyoruz. (11 Hamle Kaldı)
Kırılırsa 28. kattan 38. kata kadar tek tek deniyoruz.
Kırılmazsa aynı şekilde hamle sayımıza bağlı kalarak denemeler yapıyoruz.
14+13+12+11+...+4 = 99 yapıyor,
Kırılırsa 96. kattan 98. kata kadar tek tek deniyoruz.
Kırılmazsa ilk 99 katta kırılmadığı için 100. kattan attığımız zaman kırılacaktır.
Matematiksel olarak bunu formül ile göstermemiz gerekir ise
n : Binanın kat sayısı
q : Yapılabilecek atış sayısı
q + (q-1) + (q-2) + (q-3) + ... + 1 >= nveyaq*(q+1)/2 >= n
Yorum Gönder