Ngagrave;y soạn:hellip;/hellip;/hellip;

Ngagrave;y dạy:hellip;/hellip;/hellip;

BAgrave;I 8. THỰC HAgrave;NH THIẾT KẾ THUẬT TOAacute;N TIgrave;M KIẾM THEO KĨ THUẬT CHIA ĐỂ TRỊ

1. MỤC TIEcirc;U
2. Về kiến thức

Sau bagrave;i học nagrave;y, HS sẽ:

• Biết caacute;ch thiết kế vagrave; viết chương trigrave;nh giải một số bagrave;i toaacute;n theo kĩ thuật chia để trị.
• Thực hagrave;nh viết chương trigrave;nh giải một số bagrave;i toaacute;n theo kĩ thuật chia để trị.

2. Năng lực

Năng lực chung:

• Năng lực tự chủ: Biết lựa chọn caacute;c nguồn tagrave;i liệu học tập phugrave; hợp.
• Năng lực giải quyết vấn đề vagrave; saacute;ng tạo: Xaacute;c định vagrave; tigrave;m hiểu được caacute;c thocirc;ng tin liecirc;n quan đến vấn đề, đề xuất giải phaacute;p giải quyết vấn đề trong bagrave;i học.
• Năng lực giao tiếp vagrave; hợp taacute;c: Thực hiện tốt nhiệm vụ trong hoạt động nhoacute;m.

Năng lực tin học:

• Higrave;nh thagrave;nh, phaacute;t triển năng lực giải quyết vấn đề với sự hỗ trợ của cocirc;ng nghệ thocirc;ng tin vagrave; truyền thocirc;ng.

3. Phẩm chất:

• Higrave;nh thagrave;nh yacute; thức traacute;ch nhiệm, tiacute;nh cẩn thận khi lagrave;m việc nhoacute;m, phẩm chất lagrave;m việc chăm chỉ, chuyecirc;n cần để hoagrave;n thagrave;nh một nhiệm vụ.
• Coacute; yacute; thức vận dụng kiến thức, kĩ năng đatilde; học ở nhagrave; trường vagrave;o thực tiễn.

1. THIẾT BỊ DẠY HỌC VAgrave; HỌC LIỆU
2. Đối với giaacute;o viecirc;n

• SGK, SGV, Giaacute;o aacute;n;
• Maacute;y tiacute;nh đatilde; cagrave;i đặt Python vagrave; maacute;y chiếu;
• Higrave;nh ảnh, sơ đồ minh họa cho caacute;c bước thực hiện trecirc;n một mẫu dữ liệu đơn giản.
• Sử dụng phần mềm mocirc; phỏng thuật toaacute;n để minh họa thecirc;m trong quaacute; trigrave;nh giảng dạy.

2. Đối với học sinh

• SGK, vở ghi.
• Điện thoại coacute; cagrave;i sẵn phần mềm Python (nếu coacute;).

III. TIẾN TRIgrave;NH DẠY HỌC

1. HOẠT ĐỘNG KHỞI ĐỘNG
2. Mục tiecirc;u:

- HS lagrave;m quen với caacute;c bagrave;i toaacute;n sẽ được học thiết kế trong bagrave;i.

- Kiacute;ch thiacute;ch sự tograve; mograve; cho người học.

1. Nội dung: GV cho caacute;c nhoacute;m HS trao đổi cacirc;u hỏi Mở đầu.
2. Sản phẩm học tập: HS dựa vagrave;o kiến thức vagrave; hiểu biết caacute; nhacirc;n để đưa ra cacirc;u trả lời.
3. Tổ chức thực hiện:

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

- GV đặt cacirc;u hỏi yecirc;u cầu HS thảo luận: Cho một datilde;y số A bất kigrave;. Để xaacute;c định một số C cho trước xuất hiện trong datilde;y A bao nhiecirc;u lần thigrave; lagrave;m thế nagrave;o?

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

- HS lắng nghe, suy nghĩ vagrave; đưa ra cacirc;u trả lời.

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

- GV mời HS trả lời cacirc;u hỏi.

- Caacute;c HS khaacute;c nhận xeacute;t, necirc;u yacute; kiến khaacute;c (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, đaacute;nh giaacute;, tuyecirc;n dương cacirc;u trả lời của HS.

- GV dẫn dắt vagrave;o nội dung bagrave;i mới: Hocirc;m nay, chuacute;ng ta sẽ vận dụng những kiến thức đatilde; học về thiết kế thuật toaacute;n tigrave;m kiếm theo kĩ thuật chia để trị. - Bagrave;i 8: Thực hagrave;nh thiết kế thuật toaacute;n tigrave;m kiếm theo kĩ thuật chia để trị.

1. HOẠT ĐỘNG HIgrave;NH THAgrave;NH KIẾN THỨC

Hoạt động: Thực hagrave;nh

1. Mục tiecirc;u: Viết được chương trigrave;nh thiết kế thuật toaacute;n tigrave;m kiếm theo kĩ thuật chia để trị.
2. Nội dung: GV yecirc;u cầu HS tigrave;m hiểu nhiệm vụ, tigrave;m hiểu yecirc;u cầu vagrave; caacute;c bước thực hiện.
3. Sản phẩm học tập: Caacute;c chương trigrave;nh magrave; HS viết ra.
4. Tổ chức hoạt động:

1. HOẠT ĐỘNG LUYỆN TẬP
2. Mục tiecirc;u: HS vận dụng kiến thức, hoagrave;n thagrave;nh bagrave;i tập phần Luyện tập.
3. Nội dung: GV giao nhiệm vụ, HS thảo luận.
4. Sản phẩm học tập: HS thiết kế thuật toaacute;n tigrave;m kiếm theo kĩ thuật chia để trị để giải caacute;c bagrave;i toaacute;n.
5. Tổ chức thực hiện:

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

- GV yecirc;u cầu HS thảo luận nhoacute;m đocirc;i, hoagrave;n thagrave;nh caacute;c bagrave;i tập:

Chỉnh sửa nacirc;ng cấp chương trigrave;nh của nhiệm vụ thực hagrave;nh để đưa ra kết quả lagrave; vugrave;ng caacute;c phần tử coacute; giaacute; trị bằng C của datilde;y gốc, tức lagrave; yecirc;u cầu đưa ra chỉ số đầu, chỉ số cuối vagrave; số lượng phần tử của vugrave;ng coacute; giaacute; trị bằng C.

Viacute; dụ nếu A = [0, 1, 2, 2, 2, 2, 4, 5, 5, 6], C = 2, thigrave; kết quả trả lại lagrave; 2, 5, 4.

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

- HS thảo luận, viết chương trigrave;nh giải bagrave;i toaacute;n.

- GV hướng dẫn, theo dotilde;i, hỗ trợ HS nếu cần thiết.

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

- GV đại diện của 1 nhoacute;m lecirc;n bảng thực hiện trecirc;n maacute;y vagrave; chạy thử chương trigrave;nh.

- HS khaacute;c quan saacute;t, nhận xeacute;t, sửa bagrave;i (nếu coacute;).

Kết quả:

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, tuyecirc;n dương.

1. HOẠT ĐỘNG VẬN DỤNG
2. Mục tiecirc;u: HS vận dụng kiến thức, liecirc;n hệ với thực tế để giải quyết vấn đề.
3. Nội dung: GV tổ chức cho HS lagrave;m bagrave;i tập phần Vận dụng SGK trang 39.
4. Sản phẩm học tập: HS viết vagrave; chạy thử chương trigrave;nh.
5. Tổ chức thực hiện:

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

- GV necirc;u yecirc;u cầu bagrave;i toaacute;n:

Bagrave;i 1. Cho một datilde;y số bất kigrave; (chưa được sắp xếp) vagrave; một số K, hatilde;y tigrave;m số lần xuất hiện của K trong datilde;y số trecirc;n. Yecirc;u cầu sử dụng phương phaacute;p chia để trị.

Bagrave;i 2. Cho một datilde;y số nguyecirc;n được sắp xếp theo thứ tự tăng dần. Hatilde;y thiết kế hagrave;m tigrave;m trong datilde;y phần tử thứ i coacute; giaacute; trị bằng I (A[i] = i). Phần tử A[i] như vậy được gọi lagrave; phần tử cố định.

Bagrave;i 3. Cho trước datilde;y số A đatilde; sắp xếp theo thứ tự tăng dần, cho trước hằng số C. Cần thiết lập hai hagrave;m sau bằng kĩ thuật chia để trị:

ndash; Hagrave;m firstInd(A, left, right, C) sẽ tigrave;m chỉ số của phần tử đầu tiecirc;n của datilde;y A coacute; giaacute; trị bằng C. Nếu khocirc;ng sẽ trả về -1.

ndash; Hagrave;m lastInd(A, left, right, C) sẽ tigrave;m chỉ số của phần tử cuối cugrave;ng của datilde;y A coacute; giaacute; trị bằng C. Nếu khocirc;ng thấy sẽ trả về ndash; 1.

Từ hai hagrave;m đatilde; thiết kế trecirc;n, đưa ra một caacute;ch giải khaacute;c cho bagrave;i toaacute;n trong nhiệm vụ 1. Lời giải nagrave;y coacute; độ phức tạp O(logn).

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

- HS thảo luận, viết chương trigrave;nh giải bagrave;i toaacute;n.

- GV hướng dẫn, theo dotilde;i, hỗ trợ HS nếu cần thiết.

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

- GV đại diện của 1 nhoacute;m lecirc;n bảng thực hiện trecirc;n maacute;y vagrave; chạy thử chương trigrave;nh.

- HS khaacute;c quan saacute;t, nhận xeacute;t, sửa bagrave;i (nếu coacute;).

Kết quả:

Bagrave;i 1. Hagrave;m đệ quy được xacirc;y dựng như sau:

--------------- Cograve;n tiếp ---------------