Ném trứng từ một tòa nhà

Question

Đây là bài tập thể dục 1.4.24 từ thuật toán của Robert Sedgewick Phiên bản thứ 4.

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. 

Trong khi các giải pháp lgN rất dễ dàng để nghĩ ra, tôi hoàn toàn không có ý tưởng về giải pháp 2lgF. Dù sao, chúng tôi không được đưa ra giá trị F, vì vậy, nơi mà mặt đất của giải pháp 2lgF là?

Có ai có thể đưa ra ánh sáng về câu hỏi này không? Cảm ơn.

Answer 1

logN: bắt đầu ở phía trên cùng, không gian tìm kiếm luôn giảm đi một nửa -> tìm kiếm nhị phân

2 * logF bắt đầu từ 1, tiếp theo 2, 4, 8 (tức là 2^i), một khi phá vỡ trứng (sau khi đăng nhập F bước) làm tìm kiếm nhị phân trong không gian tìm kiếm nhỏ hơn (khoảng < F và do đó số lượng tìm kiếm < log F) -> tìm kiếm mũ

Answer 2

giải pháp lg(F) là để làm 1, 2, 4, 8, ... cho đến khi phá vỡ trứng đầu tiên tại 2^(k+1) , sau đó thực hiện tìm kiếm nhị phân trong phạm vi 2^K đến 2^(k+1).

Một giải pháp thay thế khác là thực hiện quy trình tương tự cho đến khi quả trứng thứ nhất nghỉ tại 2^(k+1) sau đó bắt đầu lại, ngoại trừ việc thêm 2^k vào mỗi chiều cao: 2^k + 1, 2^k + 2, 2^k + 4, 2^k + 8, .... Bạn có thể tiếp tục lặp lại quy trình này để tiếp tục giảm kích thước của phạm vi mà bạn thực hiện tìm kiếm theo hàm mũ.