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 ${\log }_2\left(n\right)={\log }_2\left(9\right)=3$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ả ....

• Hoạt động 1 trang 28 Chuyên đề Tin học 11: 1. Hãy trình bày cách giải bài toán tìm bi giả với 5 viên bi ....

• 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 ....

• Hoạt động 2 trang 30 Chuyên đề Tin học 11: Quan sát lại một lần nữa thuật toán tìm kiếm nhị phân trên dãy các phần tử ....

• Câu hỏi 1 trang 31 Chuyên đề Tin học 11: Trong thuật toán tìm kiếm nhị phân trên, phần cơ sở là các lệnh nào? ....

• Câu hỏi 2 trang 31 Chuyên đề Tin học 11: Mô tả các bước thực hiện thuật toán tìm kiếm nhị phân khi ....

• Hoạt động 3 trang 31 Chuyên đề Tin học 11: Đọc, quan sát phân tích sau để biết được tính vượt trội của tìm kiếm nhị phân ....

• Câu hỏi 1 trang 32 Chuyên đề Tin học 11: Tìm chính xác số phép toán đơn cần thực hiện trong thuật toán tìm kiếm nhị phân ....

• Câu hỏi 2 trang 32 Chuyên đề Tin học 11: Tìm số phép toán đơn cần thực hiện trong thuật toán ....

• Luyện tập 1 trang 32 Chuyên đề Tin học 11: Viết chương trình hoàn chỉnh nhập một dãy số đơn điệu tăng từ bàn phím ....

• Luyện tập 2 trang 32 Chuyên đề Tin học 11: Cho trước danh sách gồm có tên, điểm thi và được sắp xếp theo thứ tự ....

• Vận dụng 1 trang 32 Chuyên đề Tin học 11: Phương án không đệ quy của thuật toán tìm kiếm nhị phân có phải là ....

• Vận dụng 2 trang 32 Chuyên đề Tin học 11: Em hãy viết chương trình cài đặt các thuật toán tìm kiếm tuần tự và nhị phân ....

• Vận dụng 3 trang 32 Chuyên đề Tin học 11: Để tính giá trị (số nguyên) gần đúng căn bậc hai của số tự nhiên n cho trước ....

Xem thêm lời giải bài tập Chuyên đề học tập Tin học 11 Kết nối tri thức hay, chi tiết khác:

• Chuyên đề Tin học 11 Bài 7: Thiết kế thuật toán theo kĩ thuật chia để trị

• Chuyên đề Tin học 11 Bài 8: Thực hành thiết thuật toán tìm kiếm theo kĩ thuật chia để trị

• Chuyên đề Tin học 11 Bài 9: Sắp xếp trộn

• Chuyên đề Tin học 11 Bài 10: Thực hành giải toán bằng kĩ thuật chia để trị

• Chuyên đề Tin học 11 Bài 11: Bài toán tìm kiếm theo kĩ thuật duyệt

Săn SALE shopee Tết:

• Mỹ phẩm SACE LADY giảm tới 200k
• SRM Simple tặng tẩy trang 50k
• Combo Dầu Gội, Dầu Xả TRESEMME 80k

---