Sáng kiến kinh nghiệm THPT: Sử dụng phương pháp mảng hậu tố để giải một số bài toán về xử lý xâu bằng ngôn ngữ lập trình C++ và Python trong công tác bồi dưỡng học sinh giỏi

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:56

Thêm vào BST

Báo xấu

1
lượt xem 0
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Đề tài "Sử dụng phương pháp mảng hậu tố để giải một số bài toán về xử lý xâu bằng ngôn ngữ lập trình C++ và Python trong công tác bồi dưỡng học sinh giỏi" này giúp cho học sinh nâng cao kỹ năng lập trình, góp phần đổi mới phương pháp giải quyết các bài toán dạng xâu trong công tác bồi dưỡng học sinh giỏi. Hình thành phát triển phẩm chất, năng lực cho học sinh thông qua hoạt động luyện giải các dạng bài tập từ dễ đến khó. Các bài toán xử lý xâu (chuỗi) trong công tác bồi dưỡng học sinh giỏi có thể giúp học sinh rèn luyện tư duy logic, khả năng tập trung, kỹ năng lập trình, kỹ năng xử lý các bài toán lớn, sáng tạo trong giải quyết vấn đề và hiểu sâu về cấu trúc dữ liệu trong lĩnh vực này.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Sáng kiến kinh nghiệm THPT: Sử dụng phương pháp mảng hậu tố để giải một số bài toán về xử lý xâu bằng ngôn ngữ lập trình C++ và Python trong công tác bồi dưỡng học sinh giỏi

SỞ GIÁO DỤC VÀ ĐÀO TẠO NGHỆ AN SÁNG KIẾN KINH NGHIỆM Đề tài: SỬ DỤNG PHƯƠNG PHÁP MẢNG HẬU TỐ ĐỂ GIẢI MỘT SỐ BÀI TOÁN VỀ XỬ LÝ XÂU BẰNG NGÔN NGỮ LẬP TRÌNH C++ VÀ PYTHON TRONG CÔNG TÁC BỒI DƯỠNG HỌC SINH GIỎI LĨNH VỰC: TIN HỌC NGHỆ AN, 2024
SỞ GIÁO DỤC VÀ ĐÀO TẠO NGHỆ AN TRƯỜNG THPT NGHI LỘC 5 ---o0o--- SÁNG KIẾN KINH NGHIỆM Đề tài: SỬ DỤNG PHƯƠNG PHÁP MẢNG HẬU TỐ ĐỂ GIẢI MỘT SỐ BÀI TOÁN VỀ XỬ LÝ XÂU BẰNG NGÔN NGỮ LẬP TRÌNH C++ VÀ PYTHON TRONG CÔNG TÁC BỒI DƯỠNG HỌC SINH GIỎI LĨNH VỰC: TIN HỌC NHÓM TÁC GIẢ: 1. TRẦN BÁ VĂN 2. ĐẶNG ĐÌNH KỲ ĐIỆN THOẠI: 0976252808 - 0918307313 NGHỆ AN, 2024
MỤC LỤC PHẦN I. ĐẶT VẤN ĐỀ .......................................................................................... 1 1. Lý do chọn đề tài ............................................................................................... 1 2. Tính mới, tính sáng tạo và đóng góp của đề tài ................................................ 2 3. Đối tượng và khách thể nghiên cứu .................................................................. 3 4. Mục đích nghiên cứu ......................................................................................... 3 5. Giới hạn và phạm vi nghiên cứu ....................................................................... 3 6. Nhiệm vụ nghiên cứu ........................................................................................ 3 7. Phương pháp nghiên cứu................................................................................... 3 8. Thời gian nghiên cứu ........................................................................................ 4 PHẦN II. NỘI DUNG ............................................................................................. 4 I. Cơ sở khoa học ..................................................................................................... 4 1. Cơ sở lý luận ..................................................................................................... 4 1.1. Tổng quan về công tác bồi dưỡng học sinh giỏi ........................................ 4 1.1.1. Tầm quan trọng của việc bồi dưỡng học sinh giỏi ....................................... 4 1.1.2. Ngôn ngữ lập trình C++, Python trong công tác bồi dưỡng học sinh giỏi . 5 1.1.3. Một số năng lực đặc thù cần chú trọng trong công tác bồi dưỡng HSG ..... 6 1.2. Tổng quan về xâu ký tự .............................................................................. 7 1.2.1. Khai báo xâu ký tự........................................................................................ 8 1.2.2. Các thao tác cơ bản trên xâu ....................................................................... 8 2. Cơ sở thực tiễn ................................................................................................ 11 2.1. Công tác bồi dưỡng HSG môn Tin học ở trường THPT Nghi Lộc 5 ...... 11 2.1.1. Vai trò của ban giám hiệu trong công tác bồi dưỡng học sinh giỏi. .........11 2.1.2. Vai trò của giáo viên trực tiếp bồi dưỡng đội tuyển. .................................12 2.2. Thực trạng việc giải quyết các bài toán về xử lý xâu bằng ngôn ngữ lập trình C++ và Python trong công tác bồi dưỡng học sinh giỏi. ........................ 13 2.3. Thực trạng trước khi thực hiện các giải pháp sáng kiến .......................... 14 2.4. Thực trạng giáo viên và học sinh trong dạy học đội tuyển học sinh giỏi 14 2.5. Thực trạng học lập trình của học sinh ở trường trung học phổ thông ..... 15 II. Nội dung và phương pháp thực hiện .............................................................. 15 1. Bài toán mở đầu: Đếm xâu con phân biệt ....................................................... 15 2. Mảng hậu tố ..................................................................................................... 16 2.1. Khái niệm ................................................................................................. 16 2.2. Xây dựng mảng hậu tố ............................................................................. 16
2.3. Tiền tố chung dài nhất của hai hậu tố ...................................................... 18 2.4. Mảng tiền tố chung dài nhất ..................................................................... 20 3. Lớp các bài toán về xử lý xâu ......................................................................... 23 3.1. Kiểm tra xâu con ...................................................................................... 23 3.2. Đếm số lượng xâu con trong xâu ............................................................. 25 3.3. Đếm số lượng xâu con phân biệt độ dài k ................................................ 28 3.4. Xâu con chung dài nhất ............................................................................ 31 3.5. Tìm xâu con nhỏ thứ k ............................................................................. 33 III. Khảo sát sự cấp thiết và tính khả thi của giải pháp .................................... 35 1. Khảo sát sự cấp thiết và tính khả thi của giải pháp. ........................................ 35 1.1. Đánh giá định tính. ................................................................................... 35 1.2. Đánh giá định lượng. ................................................................................ 36 1.3. Khảo sát sự cấp thiết và tính khả thi của giải pháp đưa ra....................... 36 1.3.1. Mục đích khảo sát.......................................................................................36 1.3.2. Nội dung và phương pháp khảo sát............................................................36 1.3.3. Phương pháp khảo sát và thang đánh giá. .................................................37 1.3.4. Đối tượng khảo sát .....................................................................................37 1.3.5. Kết quả khảo sát về sự cấp thiết và tính khả thi của các giải pháp. ..........37 2. Khảo sát khả năng tiếp nhận, nắm vững kiến thức, tính sáng tạo của HS ...... 39 2.1. Kết quả thực nghiệm sư phạm.................................................................. 41 2.1.1. Kết quả đánh giá thông qua bài kiểm tra ................................................... 41 2.1.2. Phân tích kết quả thực nghiệm sư phạm. ................................................... 43 3. Một số thành tích đạt được khi áp dụng đề tài ................................................ 43 PHẦN III. KẾT LUẬN VÀ KIẾN NGHỊ ........................................................... 44 1. Kết luận ........................................................................................................... 46 1.1. Đánh giá quá trình nghiên cứu, thực hiện đề tài. ..................................... 46 1.2. Ý nghĩa của đề tài đối với hoạt động giáo dục......................................... 47 1.3. Khả năng áp dụng và phát triển của đề tài. .............................................. 48 2. Kiến nghị. ........................................................................................................ 48 2.1. Đối với trường THPT. .............................................................................. 48 2.2. Đối với GV. .............................................................................................. 49 TÀI LIỆU THAM KHẢO .................................................................................... 49 PHỤ LỤC ............................................................................................................... 50
DANH MỤC CÁC TỪ VIẾT TẮT TRONG ĐỀ TÀI TT CỤM TỪ VIẾT TẮT Ý NGHĨA 1 GDPT Giáo dục phổ thông 2 HS Học sinh 3 GV Giáo viên 4 THCS Trung học cơ sở 5 THPT Trung học phổ thông 6 PPDH Phương pháp dạy học 7 Lớp TN Lớp thực nghiệm 8 Lớp ĐC Lớp đối chứng 9 TNSP Thực nghiệm sư phạm 10 CNTT Công nghệ thông tin 11 HSG Học sinh giỏi
PHẦN I. ĐẶT VẤN ĐỀ 1. Lý do chọn đề tài Chúng ta thấy Tin học được ứng dụng vào hầu hết tất cả các lĩnh vực của cuộc sống và đã đóng vai trò rất lớn trong sự phát triển của xã hội hiện đại. Với sự tiến bộ không ngừng, môn Tin học không chỉ là nguồn động lực đằng sau sự đổi mới về tiện ích hàng ngày, mà còn là nền tảng của sự phát triển toàn diện trong nhiều lĩnh vực khác nhau. Tin học còn tác động sâu rộng vào các lĩnh vực kinh tế và xã hội. Thấy được tầm quan trọng của Tin học trên thế giới nói chung và Việt Nam nói riêng, hiện nay nền giáo dục của chúng ta đã có những đầu tư lớn cho lĩnh vực này. Đặc biệt đào tạo nguồn nhân lực có chất lượng cao trong lĩnh vực Tin học. Phụ huynh và các thế hệ học sinh sau này cũng đã bắt đầu chú trọng và đã chọn các nghành nghề liên quan đến công nghệ thông tin nhiều hơn. Mặt khác môn Tin học có đặc thù riêng, trong kỳ thi chọn học sinh giỏi tỉnh, bài thi của học sinh được chấm tự động trên phần mềm Themis nên phụ thuộc lớn vào thời gian thực hiện (thời gian chạy) chương trình và giới hạn độ lớn dữ liệu mà bài toán yêu cầu. Vì vậy trong lập trình ngoài việc chú ý đến giới hạn dữ liệu của bài toán thì cần lựa chọn thuật toán tối ưu để đảm bảo yêu cầu bài toán đặt ra. Vì vậy để giải bài toán trong Tin học thường phải xác định được: - Bài toán thuộc lớp nào. - Sử dụng phương pháp tối ưu nào để giải bài toán đó. Khi giải các bài toán Tin học người lập trình luôn mong muốn viết chương trình với thuật toán tối ưu, thời gian thực hiện nhanh, bộ nhớ hạn chế, … Tuy nhiên, bài toán Tin học thường đa dạng, phong phú nên để có thể tìm được thuật toán tối ưu phù hợp dữ liệu bài toán là việc không hề dễ dàng. Trong lập trình Tin học đã có rất nhiều phương pháp giải các bài toán nhưng để đảm bảo thời gian, không gian là không dễ. Vì vậy lựa chọn thuật toán để tối ưu là rất quan trọng. Qua quá trình giảng dạy, học tập, tìm tòi và đặc biệt là tham gia bồi dưỡng học sinh giỏi nhiều năm qua, trong đề thi có những bài toán kích thước lớn, nếu giải bằng cách thông thường thì sẽ không tối ưu về mặt thời gian, hoặc có thể không vét hết các trường hợp xảy ra của bài toán. Trong quá trình nghiên cứu và bồi dưỡng học sinh giỏi chúng tôi gặp khá nhiều bài toán về xử lí xâu. Đây là một nội dung khá phổ biến trong các đề thi học sinh giỏi tỉnh bởi nó có tính ứng dụng thực tiễn cao và là một nội dung khá khó. Trong phạm vi đề tài này, chúng tôi xin được trình bày những hiểu biết và kinh nghiệm thực tế của bản thân trong quá trình bồi dưỡng đội tuyển dự thi học sinh giỏi cấp tỉnh ở trường sử dụng phương pháp mảng hậu tố để giải quyết lớp bài toán về xâu. Mảng hậu tố (Suffix Array) là một trong những phương pháp tiếp cận để giải lớp những bài toán này một cách chính xác và hiệu quả cao. Bên cạnh đó, cài đặt mảng hậu tố ngắn gọn và đơn giản hơn nhiều so với việc cài đặt cây hậu tố (Suffix Tree). Những bài toán tổng quát và lời giải được lựa chọn hi vọng có thể giúp ích được cho 1
những thầy cô có cùng quan tâm đến phương pháp tiếp cận này. Với mong muốn tìm ra các giải pháp tối ưu cho các bài toán về xử lý xâu, chúng tôi mạnh dạn đưa ra đề tài: “Sử dụng phương pháp mảng hậu tố để giải một số bài toán về xử lý xâu bằng ngôn ngữ lập trình C++ và Python trong công tác bồi dưỡng học sinh giỏi” Hi vọng đề tài này đóng góp một phần công sức đến việc thực hiện giáo dục có hiệu quả những học sinh khá, giỏi, những học sinh có niềm đam mê về Tin học, góp phần thúc đẩy thực hiện mục tiêu giáo dục phát triển mũi nhọn của Nhà trường. 2. Tính mới, tính sáng tạo và đóng góp của đề tài - Giúp học sinh tiếp cận một dạng bài tập được làm rõ trên cả 2 loại ngôn ngữ C++ và Python, đa dạng hóa về việc áp dụng các loại ngôn ngữ lập trình để giải quyết một bài toán phù hợp với tình hình thực tế hiện nay, đáp ứng một phần yêu cầu trong kiến thức luyện thi học sinh giỏi. - Đánh giá, so sánh hai ngôn ngữ C++ và Python trong lập trình thi học sinh giỏi. - Các bài toán xử lý xâu (chuỗi) trong công tác bồi dưỡng học sinh giỏi có thể giúp học sinh rèn luyện tư duy logic, khả năng tập trung, kỹ năng lập trình, kỹ năng xử lý các bài toán lớn, sáng tạo trong giải quyết vấn đề và hiểu sâu về cấu trúc dữ liệu trong lĩnh vực này. - Giúp cải thiện được thuật toán tối ưu hơn về lớp bài toán xử lý xâu, đáp ứng thời gian theo yêu cầu của đề ra. - Phương pháp mảng hậu tố (Suffix Array) là một cấu trúc dữ liệu giúp tối ưu hóa việc tìm kiếm và so sánh các chuỗi con trong một chuỗi lớn. - Mảng hậu tố cho phép tìm kiếm nhanh chóng vị trí của một chuỗi con trong chuỗi gốc. Điều này thực hiện được bằng cách sử dụng thuật toán tìm kiếm nhị phân. - Mảng hậu tố giảm độ phức tạp của các thao tác tìm kiếm chuỗi con từ O(n^2) xuống O(n log n), với n là độ dài của xâu gốc. - Góp phần làm rõ cơ sở lí luận về vấn đề bồi dưỡng học sinh giỏi, làm rõ khái niệm, vai trò đặc điểm, khảo sát và đánh giá thực trạng của các yếu tố ảnh hưởng đến chất lượng công tác bồi dưỡng học sinh giỏi. - Sáng kiến đã đưa ra một hệ thống các bài tập thích hợp, sắp xếp một cách logic, hợp lí từ dễ đến khó nhằm giúp học sinh củng cố kiến thức, rèn luyện kỹ năng phát triển tư duy và áp dụng Tin học vào thực tiễn, qua đó góp phần tạo niềm tin và hứng thú học tập. - Là tài liệu cho học sinh giỏi cấp trường và cấp tỉnh tham khảo, đóng góp một phần nhỏ bé vào việc nâng cao được chất lượng dạy học bồi dưỡng học sinh giỏi. Đồng thời đề tài là một tài liệu quý giá cho giáo viên dạy đội tuyển bậc THCS và THPT môn Tin học. 2
3. Đối tượng và khách thể nghiên cứu - Đề tài áp dụng cho đối tượng học sinh khá, giỏi, học sinh đội tuyển học sinh giỏi môn Tin học tại trường THPT Nghi Lộc 5. - Chương trình giáo dục phổ thông mới 2018. - Ngôn ngữ lập trình C++, ngôn ngữ lập trình Python. - Cấu trúc đề thi học sinh giỏi tỉnh môn Tin học tỉnh Nghệ An. 4. Mục đích nghiên cứu - Đề tài này giúp cho học sinh nâng cao kỹ năng lập trình, góp phần đổi mới phương pháp giải quyết các bài toán dạng xâu trong công tác bồi dưỡng học sinh giỏi. Hình thành phát triển phẩm chất, năng lực cho học sinh thông qua hoạt động luyện giải các dạng bài tập từ dễ đến khó. Các bài toán xử lý xâu (chuỗi) trong công tác bồi dưỡng học sinh giỏi có thể giúp học sinh rèn luyện tư duy logic, khả năng tập trung, kỹ năng lập trình, kỹ năng xử lý các bài toán lớn, sáng tạo trong giải quyết vấn đề và hiểu sâu về cấu trúc dữ liệu trong lĩnh vực này. - Giúp cải thiện được thuật toán tối ưu hơn về lớp bài toán xử lý xâu, đáp ứng thời gian chạy chương trình theo yêu cầu của đề ra. Áp dụng phương pháp mảng hậu tố trong xử lý xâu có thể giảm độ phức tạp của các thao tác tìm kiếm chuỗi con từ O(n^2) xuống O(n log n), với n là độ dài của xâu gốc. 5. Giới hạn và phạm vi nghiên cứu - Đề tài được nghiên cứu trong quá trình dạy luyện thi cho đội tuyển học sinh dự thi học sinh giỏi cấp tỉnh tại trường THPT Nghi Lộc 5. - Đề tài có khả năng áp dụng rộng rãi vào giảng dạy, bồi dưỡng đội tuyển học sinh giỏi môn Tin học THCS, THPT trên địa bàn toàn tỉnh Nghệ An. - Đề tài giúp giải quyết một số bài toán về xử lý xâu bằng ngôn ngữ lập trình C++ và Python trong công tác bồi dưỡng học sinh giỏi. 6. Nhiệm vụ nghiên cứu - Giúp khơi nguồn cảm hứng cho học sinh khá, giỏi khi học Tin học lập trình THPT. - Giúp học sinh có cách nhìn khác về các bài toán xử lý xâu, khi học sinh gặp các bài toán về xâu thường các em cảm thấy rất khó để đưa ra cách giải hợp lý đảm bảo về thời gian chạy chương trình. - Rèn luyện kĩ năng lập trình cho học sinh. Tìm ra phương pháp tối ưu để giải quyết một số bài toán dạng xâu trong công tác bồi dưỡng học sinh giỏi. 7. Phương pháp nghiên cứu Để nghiên cứu và thực hiện đề tài này chúng tôi đã sử dụng một số nhóm phương pháp nghiên cứu sau: 3
Phương pháp nghiên cứu tài liệu: Thường xuyên sưu tầm tra cứu sách báo tài liệu có liên quan đến nội dung đề tài, qua đó phân tích tổng hợp hệ thống hóa theo mục đích nghiên cứu. Phương pháp quan sát: Thực hiện quan sát quá trình giảng dạy của đồng nghiệp, các video liên quan tới nội dung đề tài trên Internet,… Quan sát học sinh trong quá trình học tập, đặc biệt là theo dõi trong những giờ thảo luận của học sinh nhằm đánh giá thực trạng, tìm hiểu nguyên nhân, giải pháp nhằm nâng cao hiệu quả của việc bồi dưỡng học sinh giỏi, định hướng và phát triển năng lực cho học sinh. Phương pháp điều tra phỏng vấn: Tiến hành thiết lập một số câu hỏi cho nhóm giáo viên và học sinh, điều tra, khảo sát, phân tích đánh giá thực trạng của vấn đề. Phương pháp nghiên cứu, kiểm tra, đánh giá: Thông qua kết quả thực hành, bài tập tự học, làm việc theo nhóm, theo chủ đề, bài kiểm tra của học sinh hoặc bài làm cá nhân nhằm để phân tích, đánh giá kết quả và nhận định từ đó đưa ra kết luận đúng khi áp dụng đề tài. Phương pháp tổng kết kinh nghiệm: Qua các hoạt động, Giáo viên ghi chép qua đó đúc rút kinh nghiệm được và chưa được để tổng hợp đi đến kết luận. 8. Thời gian nghiên cứu Đề tài được chúng tôi nghiên cứu trong năm học 2022 – 2023 và tiếp tục hoạt động hoàn thiện trong năm học 2023 - 2024 tại trường THPT Nghi Lộc 5. PHẦN II. NỘI DUNG I. Cơ sở khoa học 1. Cơ sở lý luận 1.1. Tổng quan về công tác bồi dưỡng học sinh giỏi 1.1.1. Tầm quan trọng của việc bồi dưỡng học sinh giỏi Bồi dưỡng học sinh giỏi (HSG) trong các môn văn hóa là một phần quan trọng của chiến lược giáo dục nhà trường, hướng đến việc phát triển nguồn nhân lực và nuôi dưỡng tài năng. Việc này không chỉ giúp tăng cường kiến thức chuyên môn và kỹ năng giảng dạy của đội ngũ giáo viên, mà còn đóng góp vào thành tựu của nhà trường và thúc đẩy động lực học tập cho các em học sinh. Nhân tài có vai trò hết sức quan trọng trong việc phát triển kinh tế, xã hội. Trong đường lối đổi mới toàn diện của đất nước ta về giáo dục và đào tạo, Đảng ta đã xác định: “Cùng với khoa học và công nghệ, giáo dục và đào tạo là quốc sách hàng đầu nhằm nâng cao dân trí, đào tạo nhân lực, bồi dưỡng nhân tài...”. Việc bồi dưỡng học sinh giỏi, đào tạo nguồn nhân tài cho đất nước là một nhiệm vụ rất quan trọng và cần thiết vì những người tài bao giờ cũng là nhân tố quan trọng để thúc đẩy xã hội phát triển. Bồi dưỡng học sinh giỏi có tầm quan trọng đặc biệt trong hệ thống giáo dục vì 4
nó không chỉ giúp học sinh phát triển tốt hơn trong học tập mà còn góp phần đẩy mạnh sự tiến bộ toàn diện của nền giáo dục. Phát hiện và phát triển tiềm năng: Bồi dưỡng học sinh giỏi giúp nhận diện và phát triển những học sinh có tiềm năng xuất sắc, từ đó hỗ trợ họ đạt được tiến bộ tối đa trong học tập và sự nghiệp sau này. Tạo động lực cho học sinh: Việc được tham gia vào đội tuyển bồi dưỡng học sinh giỏi các môn thường khiến học sinh cảm thấy được đánh giá cao và có động lực hơn để phấn đấu và cố gắng hơn trong học tập. Đổi mới và nâng cao chất lượng giáo dục: Bồi dưỡng học sinh giỏi giúp thầy cô giáo phát triển phương pháp giảng dạy, đổi mới nội dung học tập và nâng cao chất lượng giáo dục chung. Phát triển tinh thần đội ngũ: Khi các học sinh giỏi được đào tạo và phát triển, họ có thể trở thành nguồn lực quý báu cho cộng đồng, đóng góp vào sự phát triển của đất nước. Khuyến khích sự đa dạng trong giáo dục: Bồi dưỡng học sinh giỏi khích lệ sự đa dạng về tài năng và khả năng, đảm bảo rằng tất cả học sinh đều có cơ hội để phát triển hết tiềm năng về phẩm chất và năng lực của mình. Tổ chức bồi dưỡng học sinh giỏi và thi học sinh giỏi nhằm: Động viên khích lệ học sinh và giáo viên trong dạy và học, góp phần thúc đẩy việc cải tiến, nâng cao chất luợng giáo dục, đồng thời phát hiện học sinh có năng khiếu để tiếp tục bồi dưỡng và định hướng nghề nghiệp đúng sở thích, sở trường, nhằm tạo nguồn nhân lực chất lượng cao cho đất nước. 1.1.2. Ngôn ngữ lập trình C++, Python trong công tác bồi dưỡng học sinh giỏi môn Tin học Trong quy định của các kỳ thi HSG Tin học, thí sinh có thể lập trình bằng ngôn ngữ C++ (trên DevC++, Code Block) hoặc Python để giải các bài toán. C++ và Python là hai ngôn ngữ lập trình phổ biến và có ưu việt riêng biệt ở một số đặc điểm sau: - Ngôn ngữ lập trình C++ là lựa chọn lý tưởng để học sinh nắm vững kiến thức về thuật toán và cách phân tích, đánh giá hiệu quả của thuật toán. Đồng thời, C++ cũng là một ngôn ngữ lập trình phổ biến và được ưa chuộng trong việc thiết kế và phát triển các ứng dụng thực tế phổ biến hiện nay như game, hệ thống nhúng và ứng dụng đồ họa. - Thư viện C++ có nhiều cấu trúc dữ liệu khác nhau cho học sinh linh hoạt lựa chọn cấu trúc phù hợp để lưu trữ và xử lý bài toán của mình. Bên cạnh đó C++ có hệ thống hàm có sẵn rất phong phú như tìm min, max, tính tổng, sắp xếp (với nhiều thuật toán khác nhau), thay thế các phần tử, tìm kiếm (tìm kiếm thường và tìm kiếm nhị phân)… Do đó tiết kiệm thời gian và tăng tốc độ chạy chương trình lên rất nhiều. 5
- C++ cho phép chương trình chạy với tốc độ thực thi nhanh. Thời gian biên dịch và thực thi của chương trình viết bằng C++ được đánh giá là nhanh hơn so với nhiều ngôn ngữ lập trình khác, điều này đặc biệt quan trọng trong việc lập trình thi đấu và trong các kỳ thi học sinh giỏi ở các cấp khác nhau. - Python có cú pháp đơn giản và rõ ràng, giúp người mới bắt đầu dễ dàng tiếp cận và hiểu được ngôn ngữ này. - Python cung cấp môi trường lập trình thân thiện và linh hoạt, khuyến khích học sinh tập trung vào việc giải quyết vấn đề thay vì những chi tiết kỹ thuật. - Python có một cộng đồng lớn và năng động, cung cấp rất nhiều thư viện và framework cho việc phát triển ứng dụng, từ web development đến machine learning và data science. Tùy thuộc vào yêu cầu và mục tiêu của từng bài toán, học sinh có thể chọn C++ cho các bài toán đòi hỏi hiệu suất cao và tối ưu hóa, trong khi Python thích hợp cho phát triển nhanh, dễ dàng, và có sẵn các thư viện mạnh mẽ cho các ứng dụng phức tạp. 1.1.3. Một số năng lực đặc thù cần chú trọng trong công tác bồi dưỡng học sinh giỏi bộ môn Tin học * Năng lực vận dụng, khai thác kiểu dữ liệu, cấu trúc dữ liệu. Mỗi ngôn ngữ lập trình đều cung cấp một số kiểu dữ liệu đơn giản cho biết phạm vi giá trị có thể lưu trữ, dung lượng bộ nhớ cần thiết để có thể lưu trữ và các phép toán tác động lên dữ liệu. Kiểu dữ liệu có cấu trúc là kiểu dữ liệu được tạo ra từ các phần tử có kiểu dữ liệu đơn giản bằng một cách nào đó. Chúng được đặc trưng bằng kiểu dữ liệu của các phần tử và điều quan trọng hơn cả là phương pháp cấu thành kiểu dữ liệu mới, phương pháp truy nhập vào kiểu dữ liệu có cấu trúc. Các đề thi học sinh giỏi hiện nay đặt ra các yêu cầu khắt khe về phạm vi dữ liệu, giới hạn dung lượng bộ nhớ và thời gian chạy chương trình thường giới hạn 1 giây. Do đó, việc chọn lựa và sử dụng cấu trúc dữ liệu phải được thực hiện một cách cẩn trọng để tối ưu hóa việc sử dụng bộ nhớ và tăng hiệu quả xử lý. Đối với học sinh luyện thi học sinh giỏi môn Tin học, việc hiểu và sử dụng các cấu trúc dữ liệu trong ngôn ngữ lập trình là rất quan trọng. Học sinh cần phải có khả năng áp dụng các cấu trúc dữ liệu để tổ chức và xử lý dữ liệu phù hợp với từng bài toán cụ thể. * Năng lực phân tích và đánh giá độ phức tạp của thuật toán. Mỗi thuật toán chỉ giải một dạng bài toán, nhưng có thể có nhiều thuật toán khác nhau cùng giải một bài toán. Do vậy, cần thiết phải lựa chọn một thuật toán tốt nhất để giải bài toán đã cho. Khi đánh giá và lựa chọn thuật toán người ta thường căn cứ vào các tiêu chí như: - Thuật toán đơn giản, dễ hiểu, dễ cài đặt, dễ viết chương trình; 6
- Số lượng bộ nhớ sử dụng ít nhất; - Thuật toán có độ phức tạp thấp nhất, thực hiện chương trình trong thời gian ngắn nhất. Trong các tiêu chí trên người ta coi trọng tiêu chí độ phức tạp thuật toán nhất. Độ phức tạp thuật toán thấp thực hiện chương trình tốn ít thời gian là tốt nhất vì thời gian là dạng tài nguyên không tái tạo được. Các đề thi học sinh giỏi môn Tin học có yêu cầu ngày càng cao cả về độ khó lẫn thời gian thực hiện chương trình. Chúng ta thường thấy trong các bài thi có ghi yêu cầu thời gian thực hiện là 1 giây và việc cho điểm ứng với miền giá trị của tham số. Vì vậy, hiểu rõ về khái niệm độ phức tạp thuật toán và cách tính toán, ước lượng độ phức tạp của giải thuật để lựa chọn thuật toán tối ưu giải quyết được các bộ dữ liệu lớn của bài toán là hết sức quan trọng, yêu cầu học sinh phải thường xuyên học tập và rèn luyện. * Năng lực viết chương trình triển khai giải thuật. Việc viết chương trình bao gồm cả việc lựa chọn cấu trúc dữ liệu để diễn tả thuật toán. Kỹ năng viết chương trình hết sức quan trọng. Nó liên quan tới phong cách, thói quen, tay nghề lập trình và thậm chí cả yếu tố tâm lý lúc làm việc. Trong quá trình chuẩn bị giải một bài toán Tin học, học sinh thường chỉ dừng lại ở việc đoán nhận giải thuật và ngay lập tức viết chương trình. Do đó, kết quả thường không đạt hiệu quả cao, dễ gặp lỗi và việc tìm và khắc phục lỗi có thể mất nhiều thời gian, thậm chí không kém phần thời gian để viết chương trình. Để giải quyết vấn đề này, học sinh cần lập sơ đồ cấu trúc chương trình trước khi thực hiện việc viết chi tiết. Kỹ năng trình bày giải thuật là một kỹ năng vô cùng quan trọng, cần được rèn luyện kỹ năng này từ rất sớm, bắt đầu từ những bài toán đơn giản và trong suốt quá trình học cho đến khi các em đi thi. 1.2. Tổng quan về xâu ký tự Dữ liệu trong các bài toán không chỉ thuộc kiểu số mà cả kiểu phi số - dạng kí tự. Dữ liệu kiểu xâu là dãy các kí tự Unicode. Ví dụ. Các xâu kí tự đơn giản: "Bach khoa" "KI SU" "2024 la nam Tan Dau" Xâu (chuỗi) là dãy các kí tự trong bảng mã ASCII, mỗi kí tự được gọi là một phần tử của xâu. Số lượng kí tự trong một xâu được gọi là độ dài của xâu. Xâu có độ dài bằng 0 gọi là xâu rỗng. Các ngôn ngữ lập trình đều có quy tắc, cách thức cho phép xác định: • Tên kiểu xâu; • Cách khai báo biến kiểu xâu; • Số lượng kí tự của xâu; 7
• Các phép toán thao tác với xâu; • Cách tham chiếu tới phần tử xâu. Biểu thức gồm các toán hạng là biến xâu hoặc hằng xâu được gọi là biểu thức xâu. Với dữ liệu kiểu xâu có thể thực hiện phép toán ghép xâu và các phép toán quan hệ. Có thể xem xâu là danh sách một chiều mà mỗi phần tử là một kí tự. Trong C++, các kí tự của xâu được đánh số thứ tự bắt đầu từ 0. Tương tự như với mảng, việc tham chiếu tới phần tử của xâu được xác định bởi tên biến xâu và chỉ số đặt trong cặp ngoặc vuông [ và ]. Ví dụ: giả sử có biến Hoten = 'Nguyen Le Huyen' thì Hoten[5] cho ta chữ 'n' là chữ thứ 6 trong xâu Hoten. Dưới đây trình bày cách khai báo kiểu dữ liệu xâu, các thao tác xử lí xâu và một số ví dụ sử dụng kiểu xâu trong C++ và Python. 1.2.1. Khai báo xâu ký tự a. Khai báo xâu ký tự trong C++ Biến kiểu xâu có thể khai báo như sau: string ; Ví dụ: string Hoten; Trong C++, độ dài xâu là giới hạn bộ nhớ và không cần khai báo độ dài xâu từ trước. b. Khởi tạo xâu trong ngôn ngữ Python. = Ví dụ: s1 = “” #Tạo xâu rỗng s1 s2 = “Viet Nam” 1.2.2. Các thao tác cơ bản trên xâu a. Các thao tác cơ bản trên xâu trong ngôn ngữ lập trình C++ 1) Phép ghép xâu, kí hiệu là dấu cộng (+), được sử dụng để ghép nhiều xâu thành một. Có thể thực hiện phép ghép xâu đối với các hằng xâu và biến xâu. Ví dụ: Phép ghép xâu: "Ha"+ " Noi" +" - "+"Viet Nam" cho xâu kết quả là "Ha Noi - Viet Nam". 2) Các phép so sánh bằng (=), khác (!=), nhỏ hơn (), nhỏ hơn hoặc bằng (=) có thứ tự ưu tiên thực hiện thấp hơn phép ghép xâu và thực hiện việc so sánh hai xâu theo các quy tắc sau: • Xâu A lớn hơn xâu B nếu như kí tự đầu tiên khác nhau giữa chúng kể từ trái sang trong xâu A có mã ASCII lớn hơn. • Nếu A và B là các xâu có độ dài khác nhau và A là đoạn đầu của B thì A là 8
nhỏ hơn B. Ví dụ: "May tinh" < "May tinh cua toi" "12723" < "2345" • Hai xâu được coi là bằng nhau nếu như chúng giống nhau hoàn toàn. Ví dụ: "TIN HOC" == "TIN HOC" Để xử lí các xâu có thể sử dụng các hàm thành viên của kiểu xâu dưới đây: 3) Hàm st.length() trả về độ dài (số ký tự) của xâu st. Giá trị st Lệnh Kết quả "abcdef" st.length(); 6 "Song Hong" st.length(); 9 4) Hàm st.erase(vt, n) thực hiện việc xoá n kí tự của xâu st bắt đầu từ vị trí vt. Giá trị st Lệnh Kết quả "abcdef" st.erase(4, 2); "abcd" "Song Hong" st.erase(st, 0, 5); "Hong" 5) Hàm st.insert(s, vt) thực hiện chèn xâu s vào xâu st bắt đầu từ vị trí vt. Giá trị st Giá trị s Lệnh Kết quả "IBM486" " PC " st.insert(s,3); "IBM PC 486" "Hinh .2" "1" st.insert(s,5); "Hinh 1.2" 6) Hàm st.substr (vt, n) thực hiện sao chép n ký tự của xâu st bắt đầu từ vị trí vt. Nếu thiếu tham số n thì mặc định là sao chép đến hết xâu st. Giá trị st Lệnh Kết quả "Bai hoc thu 9" st.substr(8,5); "thu 9" "abcdef" st.substr(1); "bcdef" 7) Hàm st.find(s, vt) tìm kiếm vị trí xuất hiện lần đầu tiên của xâu s trong xâu st, vị trí bắt đầu tìm là vt. Nếu thiếu tham số vt thì mặc định là tìm từ đầu xâu st. Nếu không tìm thấy thì hàm trả về giá trị hằng số trong C++ có tên string::npos. Giá trị st Lệnh Kết quả "abcdef" st.find("cd",1) 2 "abcdef" st.find("cd",3) string::npos "abcdef" st.find("k") string::npos Ngoài các hàm thành viên của kiểu string, C++ còn cung cấp thư viện 9
có các hàm chuẩn trên kiểu dữ liệu ký tự (char): Cú pháp Ý nghĩa Ví dụ Kết quả Nếu c là chữ cái in thường thì trả về mã ASCII của ký tự in hoa tương ứng 65 mã của toupper(c) x = toupper('a') với ký tự c, ngược lại thì trả về mã chữ A ASCII của ký tự c Nếu c là chữ cái in hoa thì trả về mã ASCII của ký tự in thường tương ứng x= 110 mã tolower(c) với ký tự c, ngược lại thì trả về mã tolower('N') của chữ n ASCII của ký tự c Ngoài ra còn có nhiều hàm khác, chúng ta có thể tra cứu thêm trên trang http://www.cplusplus.com/ b. Các thao tác cơ bản trên xâu trong ngôn ngữ lập trình Python 1) Lệnh duyệt ký tự của xâu. Có hai cách duyệt xâu, duyệt theo chỉ số và duyệt theo phần tử của xâu kí tự. Ví dụ: Duyệt theo chỉ số với lệnh range() >>> S=”Thời khóa biểu” >>> for i in range(len(S)): print(S[i], end=“ ”) Ví dụ: Duyệt theo kí tự của xâu. >>>for ch in S: print(ch, end = “ ”) 2) Xâu con và lệnh tìm vị trí câu con. Biểu thức kiểm tra nằm trong là: in Nếu đúng thì trả lại giá trị True, nếu sai trả lại giá trị False. 3) Một số lệnh (phương thức) đối với xâu kí tự trong Python . * Cú pháp đầy đủ của lệnh find(): .find(, start) Lệnh sẽ tìm vị trí đầu tiên của xâu con trong xâu mẹ bắt đầu từ vị trí start và trả về vị trí đó. - Một số phương thức thường dùng đối với xâu kí tự trong Python.  len(): Trả về chiều dài của chuỗi.  lower(): Trả về chuỗi bằng cách ký tự chữ thường 10
 upper(): Trả về chuỗi bằng cách ký tự chữ hoa  replace(): Thay thế một chuỗi với một chuỗi khác  split(): Tách một chuỗi thành các chuỗi con, tùy thuộc vào dấu phân cách.  min(): Trả về ký tự nhỏ nhất trong chuỗi.  max(): Trả về ký tự lớn nhất trong chuỗi.  isnumeric(): Kiểm tra xem chuỗi có chỉ chứa các chữ số hay không  isspace(): Kiểm tra xem chuỗi có chỉ chứa các khoảng trắng hay không.  strip(): Loại bỏ khoảng trắng ở đầu và cuối chuỗi.  capitalize(): Viết hoa ký tự đầu tiên của chuỗi. 2. Cơ sở thực tiễn 2.1. Công tác bồi dưỡng HSG môn Tin học ở trường THPT Nghi Lộc 5 2.1.1. Vai trò của ban giám hiệu trong công tác bồi dưỡng học sinh giỏi. Ban giám hiệu đóng một vai trò quan trọng và trọng yếu trong việc bồi dưỡng học sinh giỏi. Vai trò của ban giám hiệu trong việc bồi dưỡng học sinh giỏi không chỉ là lãnh đạo mà còn là người điều phối, hỗ trợ, là người động viên, tạo điều kiện thuận lợi cho sự phát triển toàn diện của giáo viên bồi dưỡng cũng như học sinh trong đội tuyển học sinh giỏi trong trường học. Ban giám hiệu nhà trường quan tâm chỉ đạo sát sao tới công tác bồi dưỡng học sinh giỏi của trường, coi đó là nhiệm vụ chính trị quan trọng hàng đầu của trường, luôn nghiên cứu để tìm ra biện pháp chỉ đạo bồi dưỡng học sinh giỏi nhằm nâng cao chất lượng học sinh mũi nhọn của trường cụ thể là: * Nâng cao nhận thức về công tác bồi dưỡng học sinh giỏi: - Thường xuyên gặp gỡ, trao đổi, nắm bắt những tâm tư nguyện vọng, những đề xuất, kiến nghị của giáo viên, học sinh để tìm biện pháp đáp ứng, đặc biệt là vấn đề tài liệu, công cụ học tập, … - Luôn quan tâm đến công tác bồi dưỡng giáo viên: Bồi dưỡng tư tưởng, chính trị, đạo đức, phẩm chất nghề nghiệp; năng lực chuyên môn; kỹ năng sư phạm; kiến thức kinh nghiệm thực tế và bồi dưỡng các kiến thức bổ trợ. - Làm tốt công tác động viên, khen thưởng thích đáng cho giáo viên, học sinh có kết quả cao trong quá trình bồi dưỡng, ... * Xây dựng kế hoạch công tác bồi dưỡng học sinh giỏi: - Xây dựng kế hoạch phải dài hạn, khoa học, chi tiết, cụ thể, có chiều sâu và có tính khả thi cao. - Trong kế hoạch phải thể hiện được mục tiêu, hình thức thi đua khen thưởng, kinh phí cần sử dụng. 11
- Kế hoạch phải được toàn thể cán bộ, giáo viên và học sinh nắm vững, kế hoạch hội thảo rút kinh nghiệm trong việc dạy đội tuyển. * Phân công giáo viên trực tiếp bồi dưỡng đội tuyển học sinh: Vai trò của người giáo viên trong công tác phát hiện, bồi dưỡng học sinh giỏi là hết sức quan trọng. Có thể nói giáo viên bồi dưỡng là một trong những yếu tố quan trọng quyết định kết quả bồi dưỡng. Vì vậy khi tuyển chọn và phân công giáo viên bồi dưỡng, cán bộ quản lí phụ trách công tác chuyên môn cần dựa trên tiêu chí như: - Lựa chọn giáo viên có trình độ năng lực, chuyên môn, nghiệp vụ cao. - Nhiệt tình, yêu nghề, say sưa với nghề, ham học hỏi, tự bồi dưỡng và cầu tiến, có ý thức kỉ luật cao trong chuyên môn. - Có sức khoẻ, tự tin, giàu kinh nghiệm, có tính sáng tạo trong giảng dạy. - Cần phân công, cần giao nhiệm vụ cho giáo viên ngay từ lớp 10 đến lớp 12 để giáo viên có trách nhiệm và kế hoạch bồi dưỡng sớm. * Tổ chức chỉ đạo bồi dưỡng học sinh giỏi: - Việc bồi dưỡng học sinh giỏi cần được làm thường xuyên, liên tục không nhất thiết phải tổ chức riêng lớp, riêng buổi. Giáo viên có thể dạy lồng ghép vào trong từng bài học, tiết học của bộ môn. Mỗi giờ học có thể phát triển một lượng kiến thức nâng cao một cách phù hợp, nhẹ nhàng, tự nhiên rồi ra bài tập thêm cho đối tượng học sinh khá, giỏi qua nhiều hình thức khác nhau. - Khoảng ba tháng trước thi có thể tổ chức bồi dưỡng nâng cao cho học sinh mỗi tuần một buổi với thời lượng phù hợp vừa sức với học sinh tránh gò ép, nhồi nhét dẫn đến tình trạng học sinh mất hứng thú với việc học. - Tổ nhóm chuyên môn cần xây dựng nội dung chương trình thống nhất, giáo viên cần phải sử dụng quỹ thời gian hợp lý đảm bảo theo hết chương trình này. * Tổ chức kiểm tra, đánh giá xếp loại học sinh: Hàng tháng, tổ chức kiểm tra, thi thử xếp thứ tự học sinh trong đội tuyển bằng các hình thức như: Giáo viên trực tiếp dạy tự ra đề, chấm, xếp loại học sinh hoặc kết hợp với các trường trong huyện tổ chức thi cụm để tăng tính thi đua và luyện tập cho học sinh. Hàng tháng, động viên, khen thưởng những em có thành tích cao nhất trong đội tuyển. Sự quan tâm của BGH ảnh hưởng lớn đến nhận thức của phụ huynh, học sinh. Từ đó giáo viên và học sinh ngày càng thấy được niềm tự hào và trách nhiệm của mình trong việc thực hiện mục tiêu đào tạo của nhà trường trong công tác bồi dưỡng học sinh giỏi. 2.1.2. Vai trò của giáo viên trực tiếp bồi dưỡng đội tuyển. Phẩm chất, uy tín, năng lực của người giáo viên có ảnh hưởng trực tiếp đến quá 12
trình học tập và rèn luyện của học sinh. Thầy cô là yếu tố hàng đầu đóng vai trò quyết định trong công tác BDHSG, là người chỉ đường về quy trình ôn luyện, định hướng các nội dung học tập, truyền dạy hứng thú, niềm say mê môn học cho các em. Giáo viên là tấm gương trong việc tự học, tự hoàn thiện bản thân về phẩm chất và năng lực chuyên môn, tâm huyết với công việc để từ đó các em tin tưởng noi theo. Giáo viên phải rất cố gắng, nỗ lực, sáng tạo và nghiêm túc trong các khâu của quá trình bồi dưỡng: như tuyển chọn học sinh, thiết kế nội dung bồi dưỡng, các phương pháp dạy học truyền thống và hiện đại phải được sử dụng linh hoạt và nhuần nhuyễn, phát huy được khả năng tự học, tự nghiên cứu của học trò trong lĩnh hội kiến thức. Môn tin học là một lĩnh vực không ngừng phát triển và thay đổi vì vậy người giáo viên giảng dạy tin học phải không ngừng học tập và cập nhật những kiến thức mới về lĩnh vực CNTT để kịp thời bổ sung cho học sinh gieo niềm tin, sự hứng thú học tập và kích thích đam mê khám phá cho học sinh. Bằng cách tạo ra môi trường học tập khích lệ và thú vị, giáo viên bồi dưỡng học sinh giỏi có thể giúp học sinh giữ vững động lực và mục tiêu trong việc phát triển phẩm chất và năng lực của mình. Việc hỗ trợ và khuyến khích học sinh giỏi có thể tạo ra những tác động tích cực không chỉ trong cuộc sống học đường mà còn trong sự nghiệp và cuộc sống sau này của học sinh. Những học sinh giỏi được bồi dưỡng thích hợp có thể trở thành nguồn nhân lực chất lượng cao vô cùng quý giá cho xã hội, góp phần vào sự phát triển và tiến bộ của đất nước. 2.2. Thực trạng việc giải quyết các bài toán về xử lý xâu bằng ngôn ngữ lập trình C++ và Python trong công tác bồi dưỡng học sinh giỏi. Giáo viên dạy bồi dưỡng vừa phải bảo đảm chất lượng đại trà, vừa phải hoàn thành chỉ tiêu chất lượng mũi nhọn và công tác kiêm nhiệm do đó cường độ làm việc quá tải và việc đầu tư cho công tác bồi dưỡng HSG cũng có phần bị hạn chế. Giáo viên dạy bồi dưỡng đều phải tự soạn chương trình dạy theo kinh nghiệm của bản thân, tự nghiên cứu, tự sưu tầm tài liệu: Tài liệu về bộ môn Tin học không nhiều. Việc tìm kiếm tài liệu dạy học phù hợp trình độ học sinh rất vất vả. Hệ thống bài tập ít ỏi, rời rạc nên việc tổng hợp bài tập và đề thi thành các dạng bài tập phục vụ dạy học mất rất nhiều thời gian. Rất ít tài liệu, sách vở nói đến các tiểu tiết để cải tiến chương trình trong các bài toán dạng xâu ký tự. Học sinh học chương trình chính khóa phải học quá nhiều môn, lại phải học thêm nhiều môn khác, cộng thêm chương trình bồi dưỡng HSG nên rất hạn chế về thời gian tự học. Các em đầu tư ít thời gian cho việc học bồi dưỡng HSG, do đó kết quả không cao là điều tất yếu. 13
Vì vậy, trong quá trình giảng dạy giáo viên phải luôn tích cực trao đổi kinh nghiệm, thảo luận về nội dung, phương pháp, kỹ thuật dạy học với các đồng nghiệp trong và ngoài nhà trường để nâng cao chất lượng giáo dục bộ môn. 2.3. Thực trạng trước khi thực hiện các giải pháp sáng kiến Việc giải các bài toán liên quan đến xâu ký tự thường học sinh có thể gặp phải một số vấn đề như sau: Phức tạp về logic: Xử lý và phân tích xâu ký tự đòi hỏi logic rõ ràng và chi tiết. Khi bài toán có nhiều quy tắc và điều kiện, việc thiếu logic hoặc hiểu sai yêu cầu có thể dẫn đến kết quả sai. Hiệu suất: Một số phương pháp giải quyết có thể không hiệu quả với các xâu ký tự lớn. Việc sử dụng các thuật toán không tối ưu có thể làm tăng độ phức tạp và thời gian thực hiện. Xử lý ngôn ngữ: Một số ngôn ngữ lập trình không hỗ trợ xâu ký tự một cách hiệu quả, điều này có thể làm cho việc lập trình trở nên khó khăn và phức tạp hơn. Khó khăn trong mã hóa và giải mã: Khi làm việc với xâu ký tự mã hóa hoặc các thuật toán mã hóa/giải mã, việc hiểu và thực hiện chính xác quá trình này đòi hỏi sự cẩn trọng và kỹ lưỡng. Độ dài biến đổi: Trong một số trường hợp, việc thay đổi độ dài của xâu ký tự có thể làm cho các phép toán hoặc thuật toán trở nên phức tạp hơn, đặc biệt là khi không có sự quản lý và kiểm soát tốt. Hiểu biết về xâu ký tự: Việc thiếu kiến thức sâu rộng về xâu ký tự và các thuật toán liên quan có thể làm giảm khả năng giải quyết vấn đề một cách hiệu quả và sáng tạo. Để vượt qua những hạn chế này, việc nắm vững kiến thức về xâu ký tự, học hỏi các thuật toán hiệu quả, và thực hành thường xuyên sẽ giúp cải thiện năng lực giải quyết bài toán dạng này. 2.4. Thực trạng giáo viên và học sinh trong dạy học đội tuyển học sinh giỏi Ơ cấp THCS các em đang học chương trình cũ nên một số trường có dạy tin học cho lớp 9 với ngôn ngữ lập trình C++. Tuy nhiên một số trường cơ sở vật chất còn hạn chế nên lớp 9 không lựa chọn học môn Tin học nên các em sẽ không biết đến ngôn ngữ lập trình bậc cao. Học sinh THPT học chương trình giáo dục phổ thông 2018 nên các em đa số đã làm quen với ngôn ngữ lập trình Python. Vậy với học sinh đã biết một số ngôn ngữ như Pascal hay C++ khi tiếp cận ngôn ngữ Python các em thường đặt ra câu hỏi là khi giải quyết bài toán nên lựa chọn ngôn ngữ nào để dễ viết, dễ sử dụng. Còn đối với học sinh đội tuyển các em lại băn khoăn trong các ngôn ngữ trên thì ngôn ngữ nào giải quyết bài toán thời gian nhanh nhất. Đây cũng là băn khoăn của nhiều giáo viên hiện nay. Giáo viên dạy đội tuyển cơ bản đã đầu tư tìm tòi. Tuy nhiên việc tiếp cận các 14
ngôn ngữ Python hay C++ của giáo viên cũng chưa nhiều nên gặp khó khăn. Dựa vào cấu trúc đề thi học sinh giỏi cấp huyện, cấp tỉnh. Có rất nhiều chuyên đề giáo viên cần bồi dưỡng cho học sinh. Một trong các chuyên đề thường có trong các đề thi học sinh giỏi môn tin là chuyên đề về dạng xâu. Đó là các lớp bài toán dạng xâu trong các đề thi. Tài liệu về ôn thi đội tuyển thật sự rất khó tìm để phù hợp cả học sinh và giáo viên 2.5. Thực trạng học tin lập trình của học sinh ở trường trung học phổ thông Lập trình Tin học là một môn học khó và cứng nhắc nên các em không mấy quan tâm. Vậy làm sao để các em thấy hứng thú và yêu thích Tin học lập trình luôn là vấn đề trăn trở của nhiều giáo viên dạy bộ môn này. Trong thực tế những năm dạy Tin học lập trình có rất nhiều các em thắc mắc rằng ngoài việc lập trình những bài toán nhàm chán như tính tổng, tính diện tích, chu vi tam giác,… thì Tin học còn lập trình những gì? Các em học sinh đều có cách nhìn chung về nội dung Tin học lập trình là nội dung rất khó. Vừa phải biết ngôn ngữ, vừa phải hiểu bản chất toán học. Đồng thời biết tìm ra thuật toán tối ưu cho bài toán. Một số học sinh có tâm lý học tập đối phó, làm sao có điểm hơn là khả năng nghiên cứu, học hỏi, tiếp cận tri thức một cách chủ động. II. Nội dung và phương pháp thực hiện 1. Bài toán mở đầu: Đếm xâu con phân biệt Cho xâu kí tự 𝑺, xâu con của 𝑺 là một đoạn gồm các kí tự liên tục của 𝑺. Ví dụ các xâu 𝑰, 𝑰𝑶, 𝑶 … là các xâu con của xâu 𝑰𝑶𝑰. Hai xâu không bằng nhau được gọi là hai xâu phân biệt. Yêu cầu: Đếm số lượng xâu con phân biệt khác rỗng của 𝑺. Dữ liệu vào: từ tệp văn bản DEMXAUPB.INP ghi duy nhất xâu 𝑺 gồm các chữ cái in hoa. Kết quả: ghi ra tệp văn bản DEMXAUPB.OUT gồm một dòng ghi một số là số lượng các xâu con phân biệt của 𝑺. Ví dụ: DEMXAUPB.INP DEMXAUPB.OUT IOI 5 Ràng buộc: - Có 20 % test độ dài của 𝑺 ≤ 𝟐𝟎𝟎 tương ứng 20 % số điểm; - Có 40 % test độ dài của 𝑺 ≤ 𝟏. 𝟎𝟎𝟎 tương ứng 40 % số điểm; - Có 40 % test độ dài của 𝑺 ≤ 𝟏𝟎𝟎. 𝟎𝟎𝟎 tương ứng 40 % số điểm. Subtest đầu tiên có thể dùng thuật toán duyệt với độ phức tạp 𝑂(𝑛3 ), subtest thứ hai có thể lấy ra tất cả các xâu con có cùng độ dài, đẩy các xâu đó vào 𝑠𝑒𝑡 để loại bỏ các xâu trùng, nếu sử dụng Hash (http://vnoi.info/wiki/algo/string/hash) để mã 15