Tải về bản chuẩn giáo án chuyên đề học tập Khoa học máy tính 11 bộ sách mới kết nối tri thức Bài 9: Sắp xếp trộn (P1). Giáo án soạn chi tiết, hướng dẫn học sinh hoạt động để tìm tòi, khám phá ra kiến thức mới, vận dụng chúng vào việc giải quyết các vấn đề của học tập và của thực tiễn cuộc sống. Mời thầy cô kéo xuống tham khảo
Rõ nét về file powerpoint trình chiếu. => Xem thêm
Ngày soạn:…/…/…
Ngày dạy:…/…/…
Sau bài học này, HS sẽ:
Năng lực chung:
Năng lực tin học:
III. TIẾN TRÌNH DẠY HỌC
- Hướng sự tò mò của học sinh muốn tìm hiểu một thuật toán sắp xếp khác tốt hơn hẳn các thuật toán sắp xếp khác tốt hơn hẳn các thuật toán sắp xếp đã biết như thuật toán sắp xếp chèn, sắp xếp chọn, sắp xếp nổi bọt.
- Kĩ thuật hướng đến chính là chia để trị.
Bước 1: GV chuyển giao nhiệm vụ học tập
- GV đặt vấn đề: Ta đã biết tìm kiếm nhị phân trên các dãy đã sắp xếp có độ phức tạp thời gian tốt hơn so với các thuật toán tìm kiếm trên dãy chưa sắp xếp. Chính vì thế, việc sắp xếp thông tin theo một trình tự nào đó luôn đóng vai trò quan trọng trong các bài toán tìm kiếm thông tin. Tuy nhiên, một số thuật toán sắp xếp mà em đã biết như sắp xếp chèn, sắp xếp chọn, sắp xếp nổi bọt, ... đều có độ phức tạp thời gian O (n2 ) (n - kích thước dãy cần sắp xếp). Câu hỏi đặt ra là: Liệu có hay không một cách sắp xếp dãy với thời gian tốt hơn O (n2)?
- GV đặt câu hỏi yêu cầu HS thảo luận: Liệu kĩ thuật chia để trị có thể áp dụng cho bài toán sắp xếp được không? Nếu có thì có làm tăng hiệu quả của sắp xếp được không?
Bước 2: HS thực hiện nhiệm vụ học tập
- HS lắng nghe, suy nghĩ và đưa ra câu trả lời.
Bước 3: Báo cáo kết quả hoạt động và thảo luận
- GV mời HS trả lời câu hỏi.
- Các HS khác nhận xét, nêu ý kiến khác (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, đánh giá, tuyên dương câu trả lời của HS.
- GV dẫn dắt vào nội dung bài mới: Để trả lời cho câu hỏi này, chúng ta vào bài học ngày hôm nay - Bài 9. Sắp xếp trộn.
Hoạt động 1. Tìm hiểu ý tưởng thuật toán sắp xếp trộn
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 40: Quan sát và thực hiện các bước theo ý tưởng của thuật toán sắp xếp trộn để biết thuật toán này là mô hình kĩ thuật chia để trị. Em có nhận xét gì về đặc thù của các giai đoạn 1, 2, 3 trong sơ đồ dưới đây? - GV yêu cầu các nhóm quan sát và thực hiện ý tưởng chính của sắp xếp trộn theo sơ đồ hình 9.1 - GV nêu ý nghĩa của việc trộn: Trộn hai dãy đã sắp xếp thành một dãy lớn hơn cũng sẽ được sắp xếp. - GV giao cho các nhóm nghiên cứu và mô tả ú tưởng của sắp xếp trộn theo ba bước Chia, Trị và Kết hợp. - GV kết luận về ý tưởng chia để trị của sắp xếp trộn. - GV cho HS thảo luận cặp đôi, trả lời Câu hỏi (SGK – tr41) để củng cố kiến thức: + Câu 1: Hãy thực hiện thao tác trộn hai dãy sau: B = 1, 4, 7; C = 2, 3, 6. + Câu 2: Thực hiện sắp xếp dãy 3, 2, 7, 1, 6, 5 theo các bước tương tự 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 ý tưởng thuật toán sắp xếp trộ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 – tr41) Câu 1: Thực hiện bằng tay trộn hai dãy B = 1, 4, 7 và C = 2, 3, 6. Mỗi bước sau mô tả một thao tác đơn thực hiện trộn hai dãy B, C, kết quả trả về dãy mới A. Bước 1. Đưa 1 vào A. Bước 2. Đưa 2 vào A. Bước 3. Đưa 3 vào A. Bước 4. Đưa 4 vào A. Bước 5. Đưa 6 vào A. Bước 6. Đưa 7 vào A. Kết thúc dãy A sẽ là 1, 2, 3, 4, 6, 7. Câu 2: Thực hiện sắp xếp trộn dãy 3, 2, 7, 1, 6, 5 theo sơ đồ. - 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 thuật toán sắp xếp trộn - Hoạt động 1 Giai đoạn 1. Từ dãy gốc ban đầu chúng ta tách chia đôi làm hai dãy con, mỗi dãy con có kích thước bằng ½ kích thước của dãy gốc. Quá trình này chính là bước Chia của kĩ thuật chia để trị. Giai đoạn 2. Khi tất cả các dãy con thu được đều chỉ còn một phần tử. Tất cả các dãy này hiển nhiên đều đã được sắp xếp đúng. Đây chính là bước Trị tương ứng của chiến lược chia để trị. Giai đoạn 3. Từ các dãy đã sắp xếp xong, chúng ta sẽ trộn chúng lại với nhau, mỗi lần trộn hai dãy đã sắp xếp để tạo thành một dãy lớn hơn cũng được sắp xếp đúng. Quá trình trộn sẽ kết thúc khi nhân được đúng một dãy chính là dãy ban đầu nhưng đã sắp xếp xong. Đây chính là quá trình Kết hợp tương ứng của kĩ thuật chia để trị.
*Kết luận Ý tưởng của thuật toán sắp xếp trộn được thực hiện qua 3 bước: Chia nhỏ dãy gốc thành các dãy với kích thước nhỏ hơn (bằng ½ dãy ban đầu), tiếp tục cho đến khi nhận được các dãy con đã sắp xếp đúng thì tiến hành trộn các dãy này để nhận được kết quả cuối cùng. Các bước trên chính là kĩ thuật chia để trị. |
Hoạt động 2. Tìm hiểu mô tả thuật toán sắp xếp trộn
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 2 SGK trang 41: Cùng thực hiện các bước cụ thể triển khai ý tưởng và cài đặt chương trình cho thuật toán sắp xếp trộn. - GV yêu cầu các nhóm thảo luận về các bước chính của sắp xếp trộn. - GV chốt lại: Có thể hiểu sắp xếp trộn luôn bao gồm hai quá trình: (1) Tách dãy gốc thành hai dãy con với mỗi dãy con có kích thước ½ dãy ban đầu. Dùng đệ quy để sắp xếp hai dãy con này. (2) Sau đó, dùng thuật toán trộn để trộn hai dãy con đã sắp xếp thành dãy ban đầu nhưng đã được sắp xếp. Thuật toán sắp xếp trộn được mô tả tổng quát như sau: Trong đó lệnh 6 chính là thuật toán "trộn" đóng vai trò rất quan trọng của sắp xếp trộn. - GV phân tích để HS hiểu được bản chất và ý nghĩa của sắp xếp trộn. - GV cho HS thảo luận cặp đôi, trả lời Câu hỏi (SGK – tr43) để củng cố kiến thức: + Câu 1: Trong chương trình 1 (trộn hai dãy B, C), vòng lặp tại dòng 6 có nhiều nhất là bao nhiêu bước lặp? + Câu 2: Mô tả các bước thực hiện chương trình 2 nếu dãy gốc A chỉ có một 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 các bước thực hiện sắp xếp trộ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 – tr43) Câu 1: Vòng lặp 6 có nhiều nhất là m + n bước lặp. Câu 2: Nếu dãy gốc có 1 phần tử thì thuật toán sắp xếp trộn sẽ không thực hiện gì và trả về ngay dãy gốc. - 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. Mô tả thuật toán sắp xếp trộn - Hoạt động 2 a) Thuật toán trộn hai dãy (merge algorithm) - Giả sử cho trước hai dãy đã được sắp thứ tự B và C có số phần tử lần lượt là m, n. Thuật toán merge(B, C) sẽ được thực hiện "trộn" hai dãy trên và đưa kết quả vào dãy A. Quy trình trộn này rất tự nhiên và được minh họa trong sơ đồ hình 9.2 Thuật toán 1. Thuật toán trộn hai dãy b) Thuật toán sắp xếp trộn (mergeSort) - Thuật toán sắp xếp trộn được mô tả bởi hàm mergeSort(A) trong chương trình sau. Thuật toán 2. Thuật toán sắp xếp trộn - Đoạn chương trình sau sẽ thực hiện sắp xếp dãy A và đưa kết quả đã sắp xếp vào dãy B. Lời gọi hàm đệ quy là: 1 A = [2, 1, 10, 0, -7, -20, 19, 100, -3, -2, 9, 11] 2 B = mergeSort(A)
*Kết luận - Thuật toán sắp xếp trộn sẽ bao gồm một hàm mergeSort(), hàm này sẽ tiến hành các bước chính của thuật toán và gọi hàm trộn hai dãy đã sắp xếp merge() khi thực hiện bước kết hợp. |
Tải giáo án chuyên đề Khoa học máy tính 11 KNTT, giáo án chuyên đề học tập Khoa học máy tính 11 Kết nối Bài 9: Sắp xếp trộn (P1), soạn giáo án chuyên đề Khoa học máy tính kết nối Bài 9: Sắp xếp trộn (P1)