Giáo án Bài 22 · KHMT. Thực hành bài toán sắp xếp

Huy động kiến thức về sắp xếp đã học; xác định nhiệm vụ của tiết học là kiểm tra xem thuật toán sắp xếp có đúng hay không.

GV trình chiếu chương trình sap(a) và đầu vào a=[6,2,6,1], yêu cầu HS dự đoán giá trị in ra của sum(b). GV đặt câu hỏi: “Nếu dãy sau sắp chỉ tăng nhưng mất mất một số 6 thì kết quả tổng có còn đúng không? Vì sao?”

HS dự đoán kết quả in ra là 15 (vì 1 + 2 + 6 + 6 = 15). HS nhận ra: dãy tăng chưa đủ, còn phải giữ đủ các phần tử của dãy ban đầu. Nhiệm vụ tiết học được xác định là kiểm tra hai tính chất của thuật toán sắp xếp.

Nêu được hai tính chất của thuật toán sắp xếp và giải thích được vì sao tổng các phần tử không đủ để kết luận dãy được bảo toàn.

HS làm việc nhóm 4 với Phiếu học tập số 1, phần A. Nhóm thảo luận các câu hỏi: (1) Dãy sau sắp cần thỏa mãn điều kiện gì về thứ tự? (2) Làm sao để biết dãy sau sắp không mất và không thừa phần tử nào? (3) Hai dãy [1,3] và [2,2] có cùng tổng nhưng có giống nhau không? Nhóm ghi kết luận vào phiếu.

Hai tính chất cần kiểm tra:

• Thứ tự: mỗi phần tử đứng sau không nhỏ hơn phần tử đứng trước (dãy không giảm).
• Bảo toàn phần tử: dãy sau sắp có cùng độ dài và cùng số lần xuất hiện của từng giá trị với dãy ban đầu.
  Kiến thức rút ra: tổng bằng nhau chưa đủ, vì [1,3] và [2,2] đều có tổng 4 nhưng khác nhau; phải so tần số từng giá trị. Với bản ghi nhiều trường, so sánh theo khóa nhưng di chuyển cả bản ghi để không ghép sai dữ liệu.

Thực hiện được việc thử chương trình sắp xếp với các trường hợp biên, có giá trị lặp và với bản ghi nhiều trường.

HS làm việc theo 2 trạm trên máy tính. Trạm 1 (trường hợp biên): chạy sap với các đầu vào [], [7], [9,4,1], [6,2,6,1], dãy đã sắp và dãy ngược; ghi kết quả vào Phiếu học tập số 1, phần B. Trạm 2 (bản ghi): với danh sách (tên, điểm) như [(An,7),(Binh,9),(Cuong,7)], sắp theo điểm và kiểm tra tên có đi cùng điểm không. Các trạm có thể dùng trang NeoEdu để đối chiếu ví dụ.

Bảng kết quả thử:

• [] → [] (dãy rỗng vẫn rỗng)
• [7] → [7] (một phần tử giữ nguyên)
• [9,4,1] → [1,4,9]
• [6,2,6,1] → [1,2,6,6], tổng 15, nguồn không đổi
  Bản ghi: danh sách sắp theo điểm, mỗi tên đi cùng điểm của mình; không có trường hợp tên bị ghép với điểm của người khác.

Vận dụng hai tính chất và các trường hợp thử để đọc đúng kết quả chương trình và đánh giá một chương trình sắp xếp.

Làm các bài tập 1–8 trong bài học. Bài 1–5 làm nhanh trên trang NeoEdu theo cá nhân. Bài 6–8 làm theo nhóm: sắp xếp các bước giải, viết và kiểm tra chương trình sắp xếp chọn với đầu vào [6,2,6,1], nêu kết quả với [], [7], [9,4,1]; đưa phản ví dụ cho việc chỉ kiểm tra tổng.

Đáp án:

1. Dãy rỗng: in 0.
2. sap([7])[0] in 7.
3. sap([9,4,1])[-1] in 9 (dãy sau sắp là 1,4,9).
4. Đáp án A: Không; cần bảo toàn đa tập phần tử, dãy tăng nhưng thiếu số lặp là sai.
5. Đúng: phải di chuyển cả tên và điểm cùng nhau.
6. Thứ tự đúng: Chuẩn bị bộ ca đa dạng → Chạy sắp xếp trên bản sao → Kiểm tra thứ tự → Kiểm tra số lượng và phần tử nguồn.
7. Mã đúng (chọn vị trí nhỏ nhất rồi đổi chỗ); kết quả [6,2,6,1] → [1,2,6,6], tổng 15, nguồn không đổi; [] → []; [7] → [7]; [9,4,1] → [1,4,9]. Thang chấm: mã chọn đúng 0,4 điểm; dãy 1,2,6,6 và tổng 15 là 0,25 điểm; giữ nguồn và tần số 0,2 điểm; ca rỗng và một phần tử 0,15 điểm.
8. Phản ví dụ: [1,3] và [2,2] đều có tổng 4 nhưng khác phần tử. Thang chấm: đưa đúng phản ví dụ 0,4 điểm; giải thích khác phần tử 0,3 điểm; nêu cách kiểm tra tần số hoặc độ dài 0,3 điểm.

Vận dụng hai tính chất kiểm tra để đánh giá một sản phẩm sắp xếp dữ liệu thực tế và giải thích kết quả.

Nhóm nhận một danh sách điểm kiểm tra của lớp dạng (tên, điểm), sắp theo điểm tăng dần bằng sap đã cho (áp dụng cho bản ghi). Nhóm viết hai hàm kiểm tra: hàm kiểm tra dãy không giảm và hàm đếm tần số giá trị của dãy ban đầu và dãy sau sắp. Nhóm báo cáo: sản phẩm có đạt không, nếu không thì phản ví dụ là gì. Về nhà: HS dùng bảng điểm thật của lớp mình (không ghi họ tên đầy đủ) để kiểm tra chương trình và viết báo cáo ngắn.

Bảng kiểm tra sản phẩm gồm: (1) dãy điểm sau sắp không giảm; (2) số lượng bản ghi không đổi; (3) mỗi tên đi cùng đúng điểm của mình; (4) số lần xuất hiện của từng điểm không đổi. Kết luận: sản phẩm đạt khi cả 4 mục đều đúng; nếu sai ở mục nào thì nêu rõ bản ghi hoặc giá trị gây lỗi.