Problem
Tòa nhà chọc trời có n tầng. Biết rằng nếu bạn thả một quả bóng thủy tinh từ tầng p và quả bóng bị vỡ, thì nếu bạn thả một quả bóng từ tầng p+1, nó cũng sẽ vỡ. . Biết rằng khi ném từ tầng cuối cùng xuống, quả bóng luôn bị vỡ.
Bạn muốn xác định số tầng tối thiểu sẽ khiến quả bóng bị vỡ khi rơi xuống. Đối với các thí nghiệm, bạn có hai quả bóng. Bạn có thể chia nhỏ tất cả, nhưng bạn phải hoàn toàn chắc chắn về con số đó trong kết quả cuối cùng.
Xác định số lần ném là đủ để giải quyết vấn đề này.
Đầu vào
Chương trình nhận đầu vào là số tầng của tòa nhà chọc trời n.
Đầu ra
Cần in ra số lần ném nhỏ nhất để luôn có thể giải được bài toán.
Lưu ý
Nhận xét về ví dụ đầu tiên. Bạn cần ném bóng từ tầng 2. Nếu nó bị vỡ thì chúng ta sẽ ném quả bóng thứ hai từ tầng 1 xuống, còn nếu nó không bị vỡ thì chúng ta sẽ ném quả bóng từ tầng 3 xuống.
Gợi ý
1. Bạn nên làm gì nếu chỉ có một quả bóng?
2. Giả sử có hai quả bóng và chúng ta đã ném một quả bóng từ tầng số k. Chúng ta sẽ hành động như thế nào tùy thuộc vào việc quả bóng có vỡ hay không?
3. Đặt
f(n) là số lần ném tối thiểu cần thiết để xác định tầng mong muốn nếu tòa nhà chọc trời có
n tầng. Thể hiện
f(n) dưới dạng các giá trị
f(a) cho các giá trị
a.
nhỏ hơn
Ví dụ
<đầu>
| # |
Đầu vào |
Đầu ra |
| 1 |
4 |
2 |
| 2 |
7 |
3 |
Запрещенные операторы: for; while; until