CHUYEcirc;N ĐỀ 2: THỰC HAgrave;NH THIẾT KẾ THUẬT TOAacute;N THEO KĨ THUẬT CHIA ĐỂ TRỊ

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 thagrave;nh caacute;c nhoacute;m, yecirc;u cầu thảo luận để hoagrave;n thagrave;nh Hoạt động 1 SGK trang 28:

1. Hatilde;y trigrave;nh bagrave;y caacute;ch giải bagrave;i toaacute;n tigrave;m bi giả với 5 viecirc;n bi.

2. Trường hợp tổng quaacute;t coacute; n viecirc;n bi caacute;ch lagrave;m như thế nagrave;o?

3. Yacute; tưởng chia để trị để giải bagrave;i toaacute;n tigrave;m bi giả được thể hiện như thế nagrave;o?

- GV yecirc;u cầu caacute;c nhoacute;m tigrave;m hiểu lời giải của bagrave;i toaacute;n tigrave;m viecirc;n bi giả, sau đoacute; trigrave;nh bagrave;y hoặc biểu diễn caacute;ch chơi.

- Sau khi HS trả lời, GV chốt lại caacute;ch chơi, từ đoacute; giới thiệu phương phaacute;p chia để trị vagrave; caacute;c bước giải bagrave;i toaacute;n nagrave;y.

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

+ Cacirc;u 1: Với n = 9, bagrave;i toaacute;n tigrave;m bi giả cần tối đa bao nhiecirc;u lần cacirc;n?

+ Cacirc;u 2: Mocirc; tả bước "kết hợp" của bagrave;i toaacute;n 9 viecirc;n bi trecirc;n.

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

- Caacute;c nhoacute;m HS tigrave;m hiểu lời giải của bagrave;i toaacute;n viecirc;n bi giả trong SGK.

- HS thảo luận nhoacute;m, hoagrave;n thagrave;nh bagrave;i tập phần Cacirc;u hỏi.

- GV theo dotilde;i, hỗ trợ HS trong quaacute; trigrave;nh học tập.

Bước 3: Baacute;o caacute;o kết quả hoạt động vagrave; thảo luận

- GV mời đại diện caacute;c nhoacute;m trigrave;nh bagrave;y kết quả thảo luận của nhoacute;m migrave;nh.

- Đại diện caacute;c nhoacute;m xung phong trả lời Cacirc;u hỏi (SGK ndash; tr30)

Cacirc;u 1: Với 9 viecirc;n bi, số lần cacirc;n tối đa lagrave; 3 lần.

Cacirc;u 2: Mocirc; tả chi tiết caacute;ch cacirc;n của 9 viecirc;n bi.

Bước 1: Phacirc;n taacute;ch số bi thagrave;nh 4 + 4 + 1 vagrave; cacirc;n 2 nhoacute;m 4 viecirc;n. Necirc;u cacirc;n cacirc;n bằng thigrave; tigrave;m ngay 1 viecirc;n bi kia lagrave; bi giả. Nếu cacirc;n khocirc;ng cacirc;n bằng thigrave; lấy ra 4 viecirc;n becirc;n nặng hơn vagrave; thực hiện tiếp

Bước 2. Thực hiện tiếp đệ quy giải bagrave;i toaacute;n với 4 viecirc;n bi đatilde; chọn. Kết quả của bước nagrave;y sẽ tigrave;m được ngay viecirc;n bi giả.

- Caacute;c HS cograve;n lại nhận xeacute;t, bổ sung (nếu coacute;).

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

- GV nhận xeacute;t, bổ sung, tuyecirc;n dương ghi điểm caacute;c nhoacute;m lagrave;m tốt.

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

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

1. Yacute; tưởng chia để trị

- Hoạt động 1

1. Với 5 viecirc;n bi, lần cacirc;n đầu tiecirc;n chuacute;ng ta lấy 4 viecirc;n bi, đặt 2 viecirc;n bi ở hai becirc;n cacirc;n.

Trường hợp 1: Necirc;u cacirc;n thăng bằng thigrave; xaacute;c định được viecirc;n bi cograve;n lại chưa cacirc;n lagrave; bi giả.

Trường hợp 2: Necirc;u cacirc;n bị lệch, ta sẽ xaacute;c định becirc;n nặng hơn chứa bi giả. Lấy hai viecirc;n bi ở becirc;n nặng hơn vagrave; cacirc;n mỗi becirc;n một viecirc;n, ta sẽ xaacute;c định được viecirc;n bi giả.

2. Tổng quaacute;t: Sau một lần cacirc;n, từ bagrave;i toaacute;n n viecirc;n bi sẽ dẫn đến bagrave;i toaacute;n với [n/2] viecirc;n bi. Khi bagrave;i toaacute;n dẫn đến cograve;n hai hoặc ba viecirc;n bi thigrave; chỉ cần một lần cacirc;n nữa sẽ tigrave;m được viecirc;n bi giả.

3. Từ bagrave;i toaacute;n gốc luocirc;n chia thagrave;nh caacute;c bagrave;i toaacute;n coacute; kiacute;ch thước nhỏ hơn, ở đacirc;y lagrave; [n/2]. Khi số bi cograve;n lại lagrave; 2 thigrave; bagrave;i toaacute;n rất đơn giản để coacute; thể giải quyết ngay, đoacute; lagrave; trị. Sau khi trị xong, kết hợp lại cả quaacute; trigrave;nh để tổng hợp kết quả chung sẽ giải quyết được bagrave;i toaacute;n gốc.

*Kết luận

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

- Kĩ thuật chia để trị lagrave; phương phaacute;p thiết kế thuật toaacute;n theo 3 giai đoạn: chia (divide), trị (conquer) vagrave; kết hợp (combine). Bagrave;i toaacute;n gốc sẽ được chia thagrave;nh caacute;c bagrave;i toaacute;n với kiacute;ch thước nhỏ hơn, sau đoacute; sẽ trị (giải quyết) caacute;c bagrave;i toaacute;n với kiacute;ch thước nhỏ hơn, cuối cugrave;ng kết hợp caacute;c kết quả để giải quyết bagrave;i toaacute;n ban đầu.

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

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

DỰ KIẾN SẢN PHẨM

Nhiệm vụ 1. Tigrave;m hiểu kĩ thuật chia để trị thocirc;ng qua tigrave;m kiếm nhị phacirc;n

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

- GV chia lớp thagrave;nh caacute;c nhoacute;m, yecirc;u cầu thảo luận để hoagrave;n thagrave;nh Hoạt động 2 SGK trang 30:

Quan saacute;t lại một lần nữa thuật toaacute;n tigrave;m kiếm nhị phacirc;n trecirc;n datilde;y caacute;c phần tử đatilde; sắp xếp vagrave; liecirc;n hệ với phương phaacute;p chia để trị.

- GV nhắc lại phương aacute;n đệ quy của bagrave;i toaacute;n tigrave;m kiếm nhị phacirc;n đatilde; được học trong Bagrave;i 2 vagrave; diễn giải thuật toaacute;n nagrave;y bằng phương phaacute;p chia để trị.

- GV kết luận về nội dung thuật toaacute;n tigrave;m kiếm nhị phacirc;n.

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

+ Cacirc;u 1: Trong thuật toaacute;n tigrave;m kiếm nhị phacirc;n trecirc;n, phần cơ sở lagrave; caacute;c lệnh nagrave;o?

+ Cacirc;u 2: Mocirc; tả caacute;c bước thực hiện thuật toaacute;n tigrave;m kiếm nhị phacirc;n khi left = right.

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

- Caacute;c nhoacute;m HS tigrave;m hiểu thuật toaacute;n tigrave;m kiếm nhị phacirc;n trong SGK.

- HS thảo luận nhoacute;m, hoagrave;n thagrave;nh bagrave;i tập phần Cacirc;u hỏi.

- GV theo dotilde;i, hỗ trợ HS trong quaacute; trigrave;nh học tập.

Bước 3: Baacute;o caacute;o kết quả hoạt động vagrave; thảo luận

- GV mời đại diện caacute;c nhoacute;m trigrave;nh bagrave;y kết quả thảo luận của nhoacute;m migrave;nh.

- Đại diện caacute;c nhoacute;m xung phong trả lời Cacirc;u hỏi (SGK ndash; tr31)

Cacirc;u 1: Phần cơ sở lagrave; caacute;c lệnh tại dograve;ng 10,11.

Cacirc;u 2: Trường hợp left = right caacute;c bước thực hiện như sau:

Bước 1. Tiacute;nh mid = left.

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

Bước 3. Nếu A[mid] ne; K thigrave;;

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

Bước 3.2. Nếu mid > K thigrave; gọi đệ quy đến A [left..mid ndash; 1] vagrave; trả về -1.

- Caacute;c HS cograve;n lại nhận xeacute;t, bổ sung (nếu coacute;).

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

- GV nhận xeacute;t, bổ sung, tuyecirc;n dương ghi điểm caacute;c nhoacute;m lagrave;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 toaacute;n tigrave;m kiếm nhị phacirc;n

- Hoạt động 2

Bagrave;i toaacute;n gốc của tigrave;m kiếm nhị phacirc;n như sau:

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

A[0] le; A[1] le; hellip; le; A[n-1]

Cho trước giaacute; trị cần tigrave;m K. Cần tigrave;m chỉ số k của datilde;y A sao cho A[k] = K. Nếu tigrave;m thấy trả về k, nếu khocirc;ng thấy trả về -1.

- Thuật toaacute;n tigrave;m kiếm nhị phacirc;n được mocirc; tả bởi hagrave;m đệ quy binarySearch(A, left, right, K) như sau:

*Kết luận

- Thuật toaacute;n tigrave;m kiếm nhị phacirc;n lagrave; một triển khai của kĩ thuật chia để trị của bagrave;i toaacute;n tigrave;m kiếm trecirc;n datilde;y caacute;c phần tử đatilde; sắp xếp.

Nhiệm vụ 2. Đaacute;nh giaacute; độ phức tạp thời gian của thuật toaacute;n tigrave;m kiếm nhị phacirc;n

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

- GV chia lớp thagrave;nh caacute;c nhoacute;m, yecirc;u cầu thảo luận để hoagrave;n thagrave;nh Hoạt động 3 SGK trang 31:

Đọc, quan saacute;t phacirc;n tiacute;ch sau để biết được tiacute;nh vượt trội của tigrave;m kiếm nhị phacirc;n với tigrave;m kiếm tuần tự, biết được vai trograve; của kĩ thuật chia để trị trong thiết kế thuật toaacute;n.

- GV trigrave;nh bagrave;y độ phức tạp thời gian của thuật toaacute;n tigrave;m kiếm nhị phacirc;n T(n) = O(logn) theo mocirc; tả trong saacute;ch.

- GV nhấn mạnh kết quả T(n) = O(logn) của tigrave;m kiếm nhị phacirc;n so với tigrave;m kiếm tuần tự lagrave; T(n) = O(n), lagrave; một bậc thời gian tốt hơn hẳn. Qua đoacute; thấy được tiacute;nh ưu việt hơn hẳn của tigrave;m kiếm nhị phacirc;n, tức lagrave; chia để trị, so với tigrave;m kiếm tuần tự, tức lagrave; tư duy tự nhiecirc;n.

- GV kết luận về độ phức tạp thời gian của thuật toaacute;n tigrave;m kiếm nhị phacirc;n.

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

+ Cacirc;u 1: Tigrave;m chiacute;nh xaacute;c số pheacute;p toaacute;n đơn cần thực hiện trong thuật toaacute;n tigrave;m kiếm nhị phacirc;n nếu datilde;y gốc chỉ coacute; 1 phần tử.

+ Cacirc;u 2: Tigrave;m số pheacute;p toaacute;n đơn cần thực hiện trong thuật toaacute;n trecirc;n nếu datilde;y coacute; 2 phần tử.

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

- Caacute;c nhoacute;m HS tigrave;m hiểu về đaacute;nh giaacute; độ phức tạp của thuật toaacute;n tigrave;m kiếm nhị phacirc;n trong SGK.

- HS thảo luận nhoacute;m, hoagrave;n thagrave;nh bagrave;i tập phần Cacirc;u hỏi.

- GV theo dotilde;i, hỗ trợ HS trong quaacute; trigrave;nh học tập.

Bước 3: Baacute;o caacute;o kết quả hoạt động vagrave; thảo luận

- GV mời đại diện caacute;c nhoacute;m trigrave;nh bagrave;y kết quả thảo luận của nhoacute;m migrave;nh.

- Đại diện caacute;c nhoacute;m xung phong trả lời Cacirc;u hỏi (SGK ndash; tr31)

Cacirc;u 1: Nếu datilde;y gốc coacute; 1 phần tử thigrave; số pheacute;p toaacute;n đơn tối đa lagrave; 4.

Cacirc;u 2: Trường hợp datilde;y gốc coacute; 2 phần tử. Số pheacute;p toaacute;n đơn được tiacute;nh như sau:

- Caacute;c dograve;ng 2, 3, 4 mỗi dograve;ng cần thực hiện 1 pheacute;p tiacute;nh.

- Caacute;c dograve;ng tiếp theo sẽ gọi đệ quy tại dograve;ng 7, 9 sẽ sử dụng nhiều nhất lagrave; 4 pheacute;p tiacute;nh nữa.

=> Vậy tổng số pheacute;p tiacute;nh đơn nhiều nhất lagrave; 3 + 4 = 7.

- Caacute;c HS cograve;n lại nhận xeacute;t, bổ sung (nếu coacute;).

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

- GV nhận xeacute;t, bổ sung, tuyecirc;n dương ghi điểm caacute;c nhoacute;m lagrave;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 toaacute;n tigrave;m kiếm nhị phacirc;n

- Hoạt động 3

Trong mọi trường hợp chuacute;ng ta coacute; cocirc;ng thức sau cho trường hợp tổng quaacute;t:

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

Vậy khocirc;ng mất tổng quaacute;t coacute; 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ừ caacute;c cocirc;ng thức (1) vagrave; (2) coacute; thể chứng minh được T(n) = O(logn).

- Theo cocirc;ng thức (2) ta coacute;:

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

= T(2^k-2) + C + C = T(2^k-2) + 2C = hellip;

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

= (k+1)C

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

*Kết luận

Thuật toaacute;n tigrave;m kiếm nhị phacirc;n coacute; độ phức tạp thời gian O(logn), tốt hơn hẳn so với tigrave;m kiếm tuần tự với thời gian chạy lagrave; O(n)