Sáng kiến kinh nghiệm THPT: Phân tích, vận dụng các thuật toán sắp xếp để giải quyết một số bài toán viết bằng NNLT C++

Mục đích chính của sáng kiến là nghiên cứu, phân tích và vận dụng các thuật toán sắp xếp dành cho đối tượng HSG khối THPT. Việc lĩnh hội được sáng kiến sẽ giúp học sinh: Mô tả đúng khái niệm, bản chất và mục đích của việc sắp xếp. Trình bày và thực hiện cài đặt một cách chính xác các thuật toán sắp xếp. Đánh giá đúng về các thuật toán sắp xếp và tìm ra thuật toán sắp xếp phù hợp cho từng bài toán. Giúp các em học giỏi môn Tin Học đạt kết quả cao. Tạo ra nguồn tài liệu tham khảo về thuật toán hỗ trợ cho học sinh, giáo viên dạy Tin học bậc THPT. Sử dụng NNLT C++ trong chương trình giáo dục phổ thông mới.
Nội dung trích xuất từ tài liệu:
Sáng kiến kinh nghiệm THPT: Phân tích, vận dụng các thuật toán sắp xếp để giải quyết một số bài toán viết bằng NNLT C++ SỞ GIÁO DỤC VÀ ĐÀO TẠO NGHỆ AN SÁNG KIẾN KINH NGHIỆM ĐỀ TÀIPHÂN TÍCH, VẬN DỤNG CÁC THUẬT TOÁN SẮP XẾP ĐỂGIẢI QUYẾT MỘT SỐ BÀI TOÁN VIẾT BẰNG NNLT C++ SKKN thuộc lĩnh vực: Tin học Nghệ An năm 20211. MỞ ĐẦU1.1. Lý do chọn đề tài Chúng ta biết rằng để có kết quả cao trong kì thi tuyển chọn học sinh giỏimôn tin học nói chung thì phải có vốn kiến thức về thuật toán để giải được cácbài toán khó, hoặc những bài toán dữ liệu vào lớn, sau đó học sinh lựa chọnNNLT để lập trình dựa vào thuật toán đã tìm được và giải bài toán theo yêu cầu. Trong quá trình dạy bồi dưỡng học sinh giỏi tôi gặp rất nhiều bài toán có sửdụng giải thuật sắp xếp. Đây là dạng bài tập không khó nhưng học sinh thườnghay chủ quan nên không chạy được hết các test lớn. Nguyên nhân cơ bản là học sinh không áp dụng phương pháp phù hợp chobài toán đó. Với mong muốn giúp học sinh giải quyết tốt hơn các bài tập sắp xếp dãy số,tôi đã dày công nghiên cứu các thuật toán sắp xếp và phân tích để áp dụng vàotừng dạng toán phù hợp. Mặt khác, theo chương trình mới của Bộ Giáo Dục khuyến khích giáo viêndạy NNLT mới thay Pascal nên tôi viết chương trình bằng NNLT C++ để làmtài liệu tham khảo mới cho giáo viên và học sinh. Từ những lý do trên tôi đã mạnh dạn trình bày sáng kiến kinh nghiệm:“Phân tích, vận dụng các thuật toán sắp xếp để giải quyết một số bài toánviết bằng NNLT C++”.1.2. Mục đích nghiên cứu Mục đích chính của sáng kiến là nghiên cứu, phân tích và vận dụng cácthuật toán sắp xếp dành cho đối tượng HSG khối THPT. Việc lĩnh hội được sángkiến sẽ giúp học sinh: - Mô tả đúng khái niệm, bản chất và mục đích của việc sắp xếp - Trình bày và thực hiện cài đặt một cách chính xác các thuật toán sắp xếp. - Đánh giá đúng về các thuật toán sắp xếp và tìm ra thuật toán sắp xếp phùhợp cho từng bài toán. - Giúp các em học giỏi môn Tin Học đạt kết quả cao - Tạo ra nguồn tài liệu tham khảo về thuật toán hỗ trợ cho học sinh, giáoviên dạy Tin học bậc THPT - Sử dụng NNLT C++ trong chương trình giáo dục phổ thông mới. 21.3. Đối tượng nghiên cứu Sáng kiến kinh nghiệm có đối tượng nghiên cứu là các thuật toán sắp xếpvà viết một số chương trình có sử dụng các thuật toán sắp xếp bằng NNLT C++.1.4. Phương pháp nghiên cứu Để trình bày sáng kiến kinh nghiệm này, chúng tôi đã sử dụng phối kết hợpnhiều phương pháp như: nghiên cứu tài liệu, thuyết trình, quan sát, điều tra cơbản, thực nghiệm so sánh, phân tích kết quả thực nghiệm, vận dụng… phù hợpvới môn học thuộc lĩnh vực Tin học. 32. NỘI DUNG NGHIÊN CỨU2.1. Cơ sở lý luận Nếu học sinh thực hiện tốt việc lựa chọn và cài đặt chương trình tối ưu khigiải các bài toán sắp xếp nói riêng và các bài tập lập trình nói chung thì chấtlượng học sinh giỏi sẽ được nâng cao. Học sinh dần được làm quen với NNLT C++.2.2. Thực trạng2.2.1 Thực trạng trước khi nghiên cứu Đối với thi học sinh giỏi, dù kết quả output của 2 thí sinh có giống hệt nhauvới cùng một bộ input, nhưng việc chênh lệch về thời gian quyết định thí sinh cóthể chiến thắng hay thất bại (yêu cầu thời gian xử lí chương trình không quá 1giây/1 test). Lý do khi vận dụng các thuật toán thì thường học sinh chỉ chọnnhững thuật toán quen thuộc mà ít khi phân tích bài toán để tìm ra thuật toán phùhợp hơn. Vấn đề đặt ra, là làm thế nào để lấy được điểm với các bộ input có dữ liệulớn. Muốn vậy cần phải lựa chọn và cài đặt được chương trình hiệu quả (tối ưu).Chương trình hiệu quả là chương trình giải quyết được những bộ input có dữliệu lớn, chính xác, dung lượng sử dụng bộ nhớ nhỏ, thời gian thực chương trìnhngắn,...2.3. Các biện pháp sử dụng để giải quyết vấn đề2.3.1. Giới thiệu về bài toán sắp xếp2.3.1.1. Khái niệm Sắp xếp là quá trình xử lý một danh sách các phần tử (hoặc các mẫu tin)để đặt chúng theo một thứ tự, thỏa mãn một tiêu chuẩn nào đó dựa trên nội dungthông tin lưu trữ tại mỗi phần tử. Ví dụ: cho trước một dãy số a1, a2,..., an được lưu trữ trong cấu trúc dữliệu mảng.Sắp xếp dãy số a1, a2,..., an là thực hiện việc bố trí lại các phần tử sao cho đượcdãy mới có thứ tự tăng dần (hoặc giảm dần). Hai thao tác so sánh và gán là các thao tác cơ bản của hầu hết các thuậttoán sắp xếp. Bài toán sắp xếp xuất hiện trong bất kỳ lĩnh vực nào của tin học. Khi xây dựng một bài toán sắp xếp, cần tìm cách giảm thiểu những phépso sánh và đổi chỗ không cần thiết để tăng hiệu quả của thuật toán. Trong đề tài này tôi giới thiệu một số giải thuật sắp xếp từ đơn giản đếnphức tạp có thể áp dụng thích hợp cho việc sắp xếp. ...