भवन से अंडे फेंकना

Question

यह रॉबर्ट सेडगेविक के एल्गोरिदम 4 वें संस्करण से व्यायाम समस्या 1.4.24 है।

Suppose that you have an N-story building and plenty of eggs. Suppose also that 
an egg is broken if it is thrown off floor F or higher, and unhurt otherwise. 
First, devise a strategy to determine the value of F such that the number of 
broken eggs is ~lgN when using ~lgN throws, then find a way to reduce the cost to 
~2lgF. 

जबकि lgN समाधान ऊपर सोचने के लिए आसान है, मैं पूरी तरह 2lgF समाधान के बारे में पता नहीं है। वैसे भी, हमें F का मूल्य नहीं दिया गया है, तो 2lgF समाधान का आधार कहाँ है?

क्या कोई इस प्रश्न पर कुछ प्रकाश दे सकता है? धन्यवाद।

Answer 1

logn: ऊपर, छमाही में हमेशा कटौती खोज अंतरिक्ष में शुरू -> द्विआधारी खोज

2 * 1 पर शुरू logF, अगले 2, 4, 8 (यानी, 2^i), एक बार अंडा टूटता (के बाद एफ चरणों लॉग इन करें) छोटे खोज अंतरिक्ष में द्विआधारी खोज (रेंज < एफ और < लॉग एफ खोजों की इसलिए संख्या) कर -> घातीय खोज

Answer 2

lg(F) समाधान 2^(k+1) पर पहले अंडा टूटता है जब तक 1, 2, 4, 8, ... करना है , फिर श्रेणी 2^K से 2^(k+1) में बाइनरी खोज करें।

एक और विकल्प एक ही प्रक्रिया को पूरा करना है जब तक कि पहले अंडे 2^(k+1) पर ब्रेक न हो जाए, तब प्रत्येक ऊंचाई पर 2^k जोड़ने के अलावा शुरू करें: 2^k + 1, 2^k + 2, 2^k + 4, 2^k + 8, ...। आप इस प्रक्रिया को दोहराते हुए रेंज के आकार को कम करने के लिए दोहरा सकते हैं।