Với n = 9 bài toán tìm bi giả cần tối đa bao nhiêu lần cân?
Với n = 9 bài toán tìm bi giả cần tối đa bao nhiêu lần cân?
Giải Chuyên đề Tin 11 Bài 6: Ý tưởng và kĩ thuật chia để trị - Kết nối tri thức
Câu hỏi 1 trang 30 Chuyên đề Tin học 11: Với n = 9 bài toán tìm bi giả cần tối đa bao nhiêu lần cân?
Lời giải:
Để giải bài toán tìm bi giả với n = 9, ta có thể sử dụng trọng lượng của cân để tìm ra bi giả. Ta có thể áp dụng phương pháp chia đôi để tìm ra bi giả trong tối đa lần cân.
Cụ thể, ta sẽ thực hiện như sau:
1. Đặt ba viên bi vào mỗi bên của cân và để lại ba viên bi còn lại bên ngoài.
2. So sánh hai bên của cân:
- Nếu hai bên bằng nhau, thì ba viên bi còn lại sẽ là bi giả.
- Nếu hai bên không bằng nhau, thì bi giả phải nằm ở bên nặng hơn. Vì vậy, ta bỏ ba viên bi ở bên nhẹ đi và chia ba viên còn lại thành hai phần bằng nhau.
3. Đặt hai viên bi lên cân và để lại một viên bi bên ngoài.
4. So sánh hai bên của cân:
- Nếu hai bên bằng nhau, thì viên bi còn lại sẽ là bi giả.
- Nếu hai bên không bằng nhau, thì bi giả phải nằm ở bên nặng hơn. Vì vậy, ta bỏ viên bi ở bên nhẹ đi và chia viên bi còn lại thành hai phần bằng nhau.
5. Đặt một viên bi lên cân và để lại một viên bi bên ngoài.
6. So sánh hai bên của cân:
- Nếu hai bên bằng nhau, thì viên bi còn lại sẽ là bi giả.
- Nếu hai bên không bằng nhau, thì bi giả phải nằm ở bên nặng hơn.
Vì vậy, để tìm ra bi giả với n = 9, ta cần tối đa 3 lần cân.
Lời giải bài tập Chuyên đề Tin 11 Bài 6: Ý tưởng và kĩ thuật chia để trị hay, chi tiết khác:
Khởi động trang 28 Chuyên đề Tin học 11: Trò chơi tìm bi giả ....
Câu hỏi 2 trang 30 Chuyên đề Tin học 11: Mô tả bước "kết hợp" của bài toán 9 viên bi trên ....