Giải Chuyên đề Tin học 11 Bài 6: Ý tưởng và kĩ thuật chia để trị
Khởi động trang 28 Chuyên đề Tin học 11: Trò chơi tìm bi giả
Có 5 viên bi giống hệt nhau, biết rằng trong các viên bi này có một viên bi giả và viên bi giả này nặng hơn các viên bi còn lại.
Chỉ với một cái cân thăng bằng, em hãy tìm ra viên bi giả đó. Cần ít nhất bao nhiêu lần cân để tìm ra viên bi giả?
Hình 6.1. Cân thăng bằng
Lời giải:
Để 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. Ý tưởng 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.
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
Lời giải:
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ó.
2. Thuật toán tìm kiếm nhị phân
Lời giải:
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.
Lời giải:
Phần cơ sở là việc kiểm tra điều kiện kết thúc đệ quy, nếu left > right thì trả về giá trị -1. Nếu không, tiếp tục tìm kiếm bằng cách tính giá trị mid ở giữa low và high, kiểm tra nó có bằng x hay không, nếu có thì trả về mid, nếu không thì tiếp tục tìm kiếm trong phần bên trái nếu x nhỏ hơn giá trị ở vị trí mid, hoặc phía bên phải nếu x lớn hơn giá trị ở vị trí mid. Quá trình đệ quy này sẽ tiếp tục cho đến khi tìm thấy giá trị x hoặc không tìm thấy và trả về -1
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.
Lời giải:
Thuật toán tìm kiếm nhị phân có độ phức tạp thời gian O(logn), tốt hơn hẳn so với tìm kiếm tuần tự với thời gian chạy là O(n)
Lời giải:
Nếu n = 1, tức là left = right. Nếu A[left] = K thì sẽ thực hiện ngay các lệnh tại dòng 5 và dừng chương trình. Nếu A[left] ≠ K thì sẽ gọi tiếp đệ quy tới các dòng 7 hoặc 9 nhưng sẽ trả về ngay –1. Vậy trong mọi trường hợp tổng số phép toán thực hiện khi n = 1 chỉ là hằng số, ta có T(1) = O(1).
Lời giải:
Ta có công thức: T(n) = T(n/2) + O(1) và T(1) = O(1) = 1
Với n = 2 ta có T(2) = T(2/2) + O(1) = T(1) + O(1) = 1 + 1 = 2
Luyện tập
Lời giải:
Em sẽ thực hiện các bước sau:
1. Nhập dãy số đơn điệu tăng từ bàn phím, các số cách nhau bởi dấu cách.
2. Nhập số K cần tìm kiếm từ bàn phím.
3. Thiết lập biến low là 0 và biến high là độ dài của dãy trừ 1.
4. Trong khi low <= high, thực hiện các bước sau:
- Thiết lập biến mid là phần tử ở giữa của dãy từ low đến high.
- Nếu arr[mid] == k, trả về mid.
- Nếu arr[mid] > k, thực hiện tìm kiếm trên nửa đầu của dãy bằng cách đặt high bằng mid-- Nếu arr[mid] < k, thực hiện tìm kiếm trên nửa sau của dãy bằng cách đặt low bằng mid+1.
5. Nếu không tìm thấy k trong dãy, trả về -1.
Lời giải:
- Đầu tiên, ta khai báo danh sách danh_sach chứa thông tin về tên học sinh và điểm số của họ. Chú ý rằng danh sách này đã được sắp xếp theo thứ tự tăng dần của điểm thi.
- Tiếp theo, ta sử dụng hàm input() để cho phép người dùng nhập vào một điểm số cần tìm.
- Sau đó, ta sử dụng một vòng lặp for để duyệt qua từng học sinh trong danh sách danh_sach. Với mỗi học sinh, nếu điểm số của họ bằng với điểm số cần tìm thì ta in ra tên của họ và kết thúc vòng lặp bằng lệnh break. Nếu không tìm thấy học sinh nào có điểm số bằng với điểm số cần tìm thì cuối cùng ta in ra thông báo "Không có học sinh có điểm số ..." bằng lệnh print() ở ngoài vòng lặp và sử dụng cú pháp else để xác định rằng chương trình đã duyệt qua toàn bộ danh sách mà không tìm thấy học sinh nào phù hợp.
Vận dụng
Lời giải:
Không, phương án không đệ quy của thuật toán tìm kiếm nhị phân không phải là chia để trị.
Thuật toán tìm kiếm nhị phân thực hiện tìm kiếm một phần tử trong một mảng đã được sắp xếp theo thứ tự tăng dần (hoặc giảm dần) bằng cách chia mảng thành hai phần và so sánh giá trị cần tìm với phần tử ở giữa mảng. Nếu giá trị cần tìm nhỏ hơn phần tử ở giữa, ta tìm kiếm trong nửa đầu tiên của mảng. Ngược lại, nếu giá trị cần tìm lớn hơn phần tử ở giữa, ta tìm kiếm trong nửa sau của mảng. Tiếp tục lặp lại quá trình này cho đến khi tìm thấy phần tử cần tìm hoặc không tìm thấy phần tử đó trong mảng.
Phương án chia để trị là một kỹ thuật giải quyết bài toán bằng cách chia bài toán thành các bài toán con, giải quyết các bài toán con đó đệ quy và kết hợp kết quả của các bài toán con để giải quyết bài toán ban đầu. Phương án chia để trị thường được sử dụng cho các bài toán mà có thể chia thành các bài toán con độc lập với nhau, ví dụ như thuật toán sắp xếp chia để trị Merge Sort.
Lời giải:
Chương trình có thể được viết ra như sau:
Chương trình trên sẽ đo thời gian thực hiện của hai thuật toán tìm kiếm tuần tự và nhị phân trên các bộ dữ liệu với giá trị n là 10, 20, 50 và 100. Kết quả đo thời gian sẽ được in ra màn hình.
Sau khi thực hiện, em sẽ thu được kết quả tương tự như sau:
Như vậy, khi n tăng lên, thời gian thực hiện của thuật toán tìm kiếm tuần tự tăng nhanh hơn so với thuật toán tìm kiếm nhị phân.
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ị.
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.
Xem thêm lời giải bài tập Chuyên đề học tập Tin học lớp 11 Kết nối tri thức hay, chi tiết khác:
Bài 5: Thực hành thiết kế thuật toán theo kĩ thuật đệ quy
Bài 7: Thiết kế thuật toán theo kĩ thuật chia để trị
Bài 8: Thực hành thiết thuật toán tìm kiếm theo kĩ thuật chia để trị
