HOẠT ĐỘNG CỦA GV - HS

DỰ KIẾN SẢN PHẨM

Bước 1: GV chuyển giao nhiệm vụ học tập

- GV chia lớp thành các nhóm, yêu cầu thảo luận để hoàn thành Hoạt động 1 SGK trang 28:

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.

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?

- GV yêu cầu các nhóm tìm hiểu lời giải của bài toán tìm viên bi giả, sau đó trình bày hoặc biểu diễn cách chơi.

- Sau khi HS trả lời, GV chốt lại cách chơi, từ đó giới thiệu phương pháp chia để trị và các bước giải bài toán này.

- GV cho HS thảo luận cặp đôi, trả lời Câu hỏi (SGK – tr30) để củng cố kiến thức:

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

+ Câu 2: Mô tả bước "kết hợp" của bài toán 9 viên bi trên.

Bước 2: HS thực hiện nhiệm vụ học tập

- Các nhóm HS tìm hiểu lời giải của bài toán viên bi giả trong SGK.

- HS thảo luận nhóm, hoàn thành bài tập phần Câu hỏi.

- GV theo dõi, hỗ trợ HS trong quá trình học tập.

Bước 3: Báo cáo kết quả hoạt động và thảo luận

- GV mời đại diện các nhóm trình bày kết quả thảo luận của nhóm mình.

- Đại diện các nhóm xung phong trả lời Câu hỏi (SGK – tr30)

Câu 1: Với 9 viên bi, số lần cân tối đa là 3 lần.

Câu 2: Mô tả chi tiết cách cân của 9 viên bi.

Bước 1: Phân tách số bi thành 4 + 4 + 1 và cân 2 nhóm 4 viên. Nêu cân cân bằng thì tìm ngay 1 viên bi kia là bi giả. Nếu cân không cân bằng thì lấy ra 4 viên bên nặng hơn và thực hiện tiếp

Bước 2. Thực hiện tiếp đệ quy giải bài toán với 4 viên bi đã chọn. Kết quả của bước này sẽ tìm được ngay viên bi giả.

- Các HS còn lại nhận xét, bổ sung (nếu có).

Bước 4: Đánh giá kết quả, thực hiện nhiệm vụ học tập

- GV nhận xét, bổ sung, tuyên dương ghi điểm các nhóm làm tốt.

- GV tổng kết lại nội dung.

- GV chuyển sang nội dung tiếp theo.

1. Ý tưởng chia để trị

- Hoạt động 1

1. 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ả.

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

2. Tổng quát: Sau một lần cân, từ bài toán n viên bi sẽ dẫn đến bài toán với [n/2] viên bi. 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ừ 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.

*Kết luận

- Sơ đồ ý tưởng chia để trị:

- Kĩ thuật chia để trị là phương pháp thiết kế thuật toán theo 3 giai đoạn: chia (divide), trị (conquer) và kết hợp (combine). Bài toán gốc sẽ được chia thành các bài toán với kích thước nhỏ hơn, sau đó sẽ trị (giải quyết) các bài toán với kích thước nhỏ hơn, cuối cùng kết hợp các kết quả để giải quyết bài toán ban đầu.

- Kĩ thuật chia để trị thường sử dụng kĩ thuật đệ quy ở bước chia (divide) và bước trị (conquer).

HOẠT ĐỘNG CỦA GV - HS

DỰ KIẾN SẢN PHẨM

Nhiệm vụ 1. Tìm hiểu kĩ thuật chia để trị thông qua tìm kiếm nhị phân

Bước 1: GV chuyển giao nhiệm vụ học tập

- GV chia lớp thành các nhóm, yêu cầu thảo luận để hoàn thành Hoạt động 2 SGK trang 30:

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 và liên hệ với phương pháp chia để trị.

- GV nhắc lại phương án đệ quy của bài toán tìm kiếm nhị phân đã được học trong Bài 2 và diễn giải thuật toán này bằng phương pháp chia để trị.

- GV kết luận về nội dung thuật toán tìm kiếm nhị phân.

- GV cho HS thảo luận cặp đôi, trả lời Câu hỏi (SGK – tr31) để củng cố kiến thức:

+ Câu 1: 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 2: Mô tả các bước thực hiện thuật toán tìm kiếm nhị phân khi left = right.

Bước 2: HS thực hiện nhiệm vụ học tập

- Các nhóm HS tìm hiểu thuật toán tìm kiếm nhị phân  trong SGK.

- HS thảo luận nhóm, hoàn thành bài tập phần Câu hỏi.

- GV theo dõi, hỗ trợ HS trong quá trình học tập.

Bước 3: Báo cáo kết quả hoạt động và thảo luận

- GV mời đại diện các nhóm trình bày kết quả thảo luận của nhóm mình.

- Đại diện các nhóm xung phong trả lời Câu hỏi (SGK – tr31)

Câu 1: Phần cơ sở là các lệnh tại dòng 10,11.

Câu 2: Trường hợp left = right các bước thực hiện như sau:

Bước 1. Tính mid = left.

Bước 2. Nếu A[mid] = K thì trả về mid.

Bước 3. Nếu A[mid] ≠ K thì;

Bước 3.1. Nếu mid < K thì gọi đệ quy đến A [mid + 1..right] và trả về -1.

Bước 3.2. Nếu mid > K thì gọi đệ quy đến A [left..mid – 1] và trả về -1.

- Các HS còn lại nhận xét, bổ sung (nếu có).

Bước 4: Đánh giá kết quả, thực hiện nhiệm vụ học tập

- GV nhận xét, bổ sung, tuyên dương ghi điểm các nhóm làm tốt.

- GV tổng kết lại nội dung.

- GV chuyển sang nội dung tiếp theo.

2. Thuật toán tìm kiếm nhị phân

- Hoạt động 2

Bài toán gốc của tìm kiếm nhị phân như sau:

Cho trước dãy A gồm n phần tử đã được sắp xếp theo thứ tự tăng dần:

A[0] ≤ A[1] ≤ … ≤ A[n-1]

Cho trước giá trị cần tìm K. Cần tìm chỉ số k của dãy A sao cho A[k] = K. Nếu tìm thấy trả về k, nếu không thấy trả về -1.

- Thuật toán tìm kiếm nhị phân được mô tả bởi hàm đệ quy binarySearch(A, left, right, K) như sau:

*Kết luận

- Thuật toán tìm kiếm nhị phân là một triển khai của kĩ thuật chia để trị của bài toán tìm kiếm trên dãy các phần tử đã sắp xếp.

Nhiệm vụ 2. Đánh giá độ phức tạp thời gian của thuật toán tìm kiếm nhị phân

Bước 1: GV chuyển giao nhiệm vụ học tập

- GV chia lớp thành các nhóm, yêu cầu thảo luận để hoàn thành Hoạt động 3 SGK trang 31:

Đọ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 tuần tự, biết được vai trò của kĩ thuật chia để trị trong thiết kế thuật toán.

- GV trình bày độ phức tạp thời gian của thuật toán tìm kiếm nhị phân T(n) = O(logn) theo mô tả trong sách.

- GV nhấn mạnh kết quả T(n) = O(logn) của tìm kiếm nhị phân so với tìm kiếm tuần tự là T(n) = O(n), là một bậc thời gian tốt hơn hẳn. Qua đó thấy được tính ưu việt hơn hẳn của tìm kiếm nhị phân, tức là chia để trị, so với tìm kiếm tuần tự, tức là tư duy tự nhiên.

- GV kết luận về độ phức tạp thời gian của thuật toán tìm kiếm nhị phân.

- GV cho HS thảo luận cặp đôi, trả lời Câu hỏi (SGK – tr32) để củng cố kiến thức:

+ Câu 1: 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 2: 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ử.

Bước 2: HS thực hiện nhiệm vụ học tập

- Các nhóm HS tìm hiểu về đánh giá độ phức tạp của thuật toán tìm kiếm nhị phân trong SGK.

- HS thảo luận nhóm, hoàn thành bài tập phần Câu hỏi.

- GV theo dõi, hỗ trợ HS trong quá trình học tập.

Bước 3: Báo cáo kết quả hoạt động và thảo luận

- GV mời đại diện các nhóm trình bày kết quả thảo luận của nhóm mình.

- Đại diện các nhóm xung phong trả lời Câu hỏi (SGK – tr31)

Câu 1: Nếu dãy gốc có 1 phần tử thì số phép toán đơn tối đa là 4.

Câu 2: Trường hợp dãy gốc có 2 phần tử. Số phép toán đơn được tính như sau:

- Các dòng 2, 3, 4 mỗi dòng cần thực hiện 1 phép tính.

- Các dòng tiếp theo sẽ gọi đệ quy tại dòng 7, 9 sẽ sử dụng nhiều nhất là 4 phép tính nữa.

=> Vậy tổng số phép tính đơn nhiều nhất là 3 + 4 = 7.

- Các HS còn lại nhận xét, bổ sung (nếu có).

Bước 4: Đánh giá kết quả, thực hiện nhiệm vụ học tập

- GV nhận xét, bổ sung, tuyên dương ghi điểm các nhóm làm tốt.

- GV tổng kết lại nội dung.

- GV chuyển sang nội dung luyện tập.

2. Thuật toán tìm kiếm nhị phân

- Hoạt động 3

Trong mọi trường hợp chúng ta có công thức sau cho trường hợp tổng quát:

T(n) = T(n/2) + O(1)

Vậy không mất tổng quát có thể giả thiết tồn tại hằng số C sao cho:

T(1) = C  (1)

T(n) = T(n/2) + C    (2)

Từ các công thức (1) và (2) có thể chứng minh được T(n) = O(logn).

- Theo công thức (2) ta có:

T(n) = T(2^k) = T(2^k-1) + C

= T(2^k-2) + C + C = T(2^k-2) + 2C = …

= T(2⁰) + kC // theo công thức (1)

= (k+1)C

= C.k + C = C.log₂n + C = O(log₂n).

*Kết luận

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)