Tổng quan
Với vô số trứng, tìm kiếm nhị phân tìm tầng tới hạn trong khoảng 7 lần thả. Chỉ với hai quả, bạn phải cân bằng rủi ro mỗi lần thả quả đầu — một bài tối ưu đẹp.
Cách giải Thả Hai Quả Trứng từng bước
- Nếu quả trứng đầu vỡ, quả thứ hai phải kiểm tra tuyến tính mọi tầng bên dưới.
- Vậy hãy để mỗi lần thả quả đầu bao phủ ít hơn lần trước một tầng: 14, rồi +13, +12, ….
- Chọn điểm bắt đầu sao cho các bước giảm dần vẫn tới 100: 14+13+…+1 = 105 ≥ 100.
Mấu chốt
Mỗi lần thả nên giữ trường hợp xấu nhất không đổi. Khi các lần thả quả đầu dùng dần số lượt, số tầng mỗi lần bao phủ phải giảm một — cho chặn theo số tam giác.
Biến thể & liên hệ
- Phiên bản tổng quát k trứng, n tầng là bài quy hoạch động kinh điển.
- Nó mô hình hóa mọi phép thử tốn kém và số 'mẫu vật' giới hạn.
Câu hỏi thường gặp
Sao không dùng tìm kiếm nhị phân?
Tìm kiếm nhị phân có thể làm vỡ quả đầu ở tầng 50, để lại 49 tầng phải thử từng cái với quả cuối — tới 50 lần thả.