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

Để tìm viên bi giả, ta cần xác định được viên bi nặng hơn. Sau đó, ta tiếp tục cân các cặp bi bao gồm bi nặng hơn và bi còn lại cho đến khi tìm được viên bi giả.

        Cách thực hiện là chia 5 viên bi thành 3 phần gồm 2, 2 và 1 viên. Ta cân 2 phần gồm 2 viên đầu tiên. Nếu cân bằng, tức là viên bi giả không nằm trong 2 viên đó, nên ta cân viên bi còn lại trong phần chưa được cân. Nếu không cân bằng, ta xác định được phía nào có viên bi nặng hơn và ta tiếp tục thực hiện như trên với 2 viên nặng hơn và 1 viên còn lại.

Số lần cân ít nhất để tìm được viên bi giả là 2.

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.

Để 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.

Bước "kết hợp" là bước cuối cùng của bài toán 9 viên bi, khi em đã tìm được viên bi có trọng lượng khác nhau và biết được nó nặng hơn hay nhẹ hơn. Bước này giúp xác định trọng lượng chính xác của viên bi khác nhau bằng cách sử dụng một cân cân đôi.

        Để thực hiện bước này, em cần chuẩn bị hai tập hợp bằng nhau của các viên bi, mỗi tập hợp chứa 3 viên bi. Trong đó, em biết chắc rằng viên bi khác nhau sẽ nằm trong một trong hai tập hợp đó. Em đặt 3 viên bi từ tập hợp thứ nhất lên một bên của cân, và đặt 3 viên bi từ tập hợp thứ hai lên bên còn lại của cân. Nếu hai bên cân bằng nhau, thì viên bi khác nhau nằm trong tập hợp còn lại, và em cần tiếp tục chia đôi tập hợp đó và tiếp tục thực hiện bước này cho đến khi tìm ra viên bi khác nhau.

        Nếu hai bên cân không bằng nhau, em sẽ biết được viên bi khác nhau nằm ở tập hợp nào và nó nặng hơn hay nhẹ hơn so với các viên bi khác trong tập hợp đó. Khi đó, em tiếp tục chia đôi tập hợp đó và lặp lại bước "kết hợp" cho đến khi tìm ra viên bi khác nhau và xác định được trọng lượng chính xác của nó.

Thuật toán này hoạt động dựa trên phương pháp chia để trị, tức là tách mảng thành các phần nhỏ hơn và giải quyết từng phần nhỏ đó một cách độc lập.