Hãy trình bày cách giải bài toán tìm bi giả với 5 viên bi

Lời giải Hoạt động 1 trang 28 Chuyên đề Tin học 11 sách Chuyên đề học tập Tin học lớp 11 Kết nối tri thức hay nhất, chi tiết sẽ giúp học sinh dễ dàng trả lời các câu hỏi & làm bài tập.

1 166 20/08/2023

Trang trước

Trang sau

Giải Chuyên đề Tin học 11 Kết nối tri thức Bài 6: Ý tưởng và kĩ thuật chia để trị

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

2. Trường hợp tổng quát có n viên bi cách làm như thế nào?

3. Ý tưởng chia để trị để giải bài toán tìm bi giả được thể hiện như thế nào?

Lời giải:

1. Cách giải bài toán tìm bi giả với 5 viên bi.

Với 5 viên bi, lần cân đầu tiên chúng ta lấy 4 viên bi, đặt 2 viên bi ở hai bên cân.

Trường họp 1. Nếu cân thăng bằng thì xác định được viên bi còn lại chưa cân là bi giả.

Như vậy, sau lần cần thứ nhất ta tìm được bi giả.

Trường hợp 2. Nếu cân bị lệch, ta sẽ xác định bên nặng hơn chứa bi giả. Lấy hai viên bi ở bên nặng hơn và cân mỗi bên một viên, ta sẽ xác định được viên bi giả. Như vậy, sau lần cân thứ hai ta tìm được bi giả.

2. Trường hợp tổng quát có n viên bi cách làm như sau:

- Nếu n lẻ, n = 2k + 1, sau lần cân thứ nhất với mỗi bên k viên, hoặc tìm thấy ngay viên bi giả, hoặc biết bên nào có chứa bi giả và tiếp tục cân với k viên bi đó.
- Nếu n chẵn, n = 2k, sau lần cân thứ nhất, ta tìm được k viên bi chữa viên bi giả. Tổng quát, sau một lần cân, từ bài toán với n viên bi sẽ dẫn đến bài toán với [n/21 viên bi ([x] là phần nguyên của x). Khi bài toán dẫn đến còn hai hoặc ba viên bi thì chỉ cần một lần cân nữa sẽ tìm được viên bi giả.

3. Ý tưởng chia để trị để giải bài toán tìm bi giả được thể hiện như thế nào?

Ý tưởng chia để trị để giải bài toán tìm bi giả: Từ bài toán gốc luôn chia thành các bài toán có kích thước nhỏ hơn, ở đây là [n/2]. Khi số bi còn lại là 2 thì bài toán rất đơn giản có thể giải quyết ngay, đó là trị. Sau khi trị xong, kết hợp lại cả quá trình để tổng hợp kết quả chung sẽ giải quyết được bài toán gốc.

Xem thêm các bài giải Chuyên đề Tin học 11 sách Kết nối tri thức 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: 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ử đã sắp xếp

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 left = right

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 với tìm kiếm

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 nếu dãy gốc chỉ có 1 phần tử

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 trên nếu dãy có 2 phần tử

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ự tăng dần của điểm thi