Với n = 9 bài toán tìm bi giả cần tối đa bao nhiêu lần cân?

Xem lời giải

Câu hỏi trong đề: Chuyên đề Tin Học 11 KNTT Bài 6. Ý tưởng và kĩ thuật chia để trị có đáp án !!

Bắt đầu thi

Quảng cáo

Trả lời:

Giải bởi Vietjack

Để 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} (n) = \log_{2} (9) = 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.

Hot: Học hè online Toán, Văn, Anh...lớp 1-12 tại Vietjack với hơn 1 triệu bài tập có đáp án. Học ngay

Sách thầy cô Vietjack biên soạn:

Xem thêm »

Bình luận

CÂU HỎI HOT CÙNG CHỦ ĐỀ

Câu 1

Mô tả các bước thực hiện thuật toán tìm kiếm nhị phân khi left = right

Xem đáp án

Lời giải

Khi left = right, nghĩa là chỉ còn một phần tử để xét. Ta so sánh giá trị của phần tử đó với giá trị cần tìm x.

Nếu phần tử đó bằng x thì ta trả về vị trí của phần tử đó (left hoặc right).

Nếu phần tử đó khác x thì ta trả về giá trị -1 để thể hiện không tìm thấy phần tử x trong dãy.

Câu 2

Để 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, người ta đã thiết lập hàm sau với ý tưởng gần tương tự thuật toán tìm kiếm tuần tự như sau

Hãy thiết kế lại thuật toán tìm số nguyên lớn nhất không vượt quá căn bậc hai của n bằng kĩ thuật chia để trị.

Xem đáp án

Lời giải

Thuật toán tìm số nguyên lớn nhất không vượt quá căn bậc hai của n có thể được thiết kế bằng kĩ thuật chia để trị theo các bước sau:

1. Nếu n bằng 0 hoặc 1, trả về n.

2. Đặt a bằng căn bậc hai của n.

3. Nếu a bằng n, trả về a.

4. Ngược lại, tìm số nguyên lớn nhất không vượt quá căn bậc hai của n/2 và số nguyên lớn nhất không vượt quá căn bậc hai của n - 1. So sánh hai số này và trả về số lớn hơn.