SKKN PHƯƠNG PHÁP GIẢI MỘT SỐ BÀI TOÁN CHUỔI CON BẰNG NNLT C++

1. Lý do chọn đề tài 

  Chúng ta đang từng bước triển khai Chương trình giáo dục phổ thông mới, trong đó môn Tin học ngày càng khẳng định vai trò chủ đạo trong việc trang bị cho người học khả năng tìm kiếm, tiếp nhận, mở rộng tri thức và sáng tạo trong thời đại cách mạng công nghiệp lần thứ tư và toàn cầu hóa.   

Trong quá trình giảng dạy chúng tôi đã dành nhiều thời gian để tìm kiếm, sưu tầm, phân loại được một số bài tập về xử lý chuổi con. Nên chúng tôi cùng nghiên cứu và viết đề tài “PHƢƠNG PHÁP GIẢI MỘT SỐ BÀI TOÁN CHUỔI CON BẰNG NNLT C++” nhằm hệ thống hóa toàn bộ kiến thức về dữ liệu kiểu chuổi để giúp giáo viên và học sinh sử dụng trong việc dạy và học. 

 Khi trao đổi với đồng nghiệp cùng trường và một số giáo viên ở trường khác trong khu vực, chúng tôi nhận thấy còn nhiều giáo viên khi dạy về vấn đề xử lý chuổi con còn khó khăn khi đưa ra các bài tập và code viết bằng NNLT C++, cho nên chúng tôi mạnh dạn trao đổi kinh nghiệm của mình. Rất mong các đồng nghiệp nhận xét, góp ý để đề tài của chúng tôi ngày càng hoàn thiện và ứng dụng rộng rãi trong thực tiễn. 

Các bài toán và code mà chúng tôi đưa ra chỉ nhằm giới thiệu cho học sinh cách viết chứ chưa hẳn là một phương án tối ưu để giải quyết bài toán cụ thể đó. 

 2. Tính cấp thiết của đề tài 

  Các bài toán xử lý chuổi con là rất quan trọng trong lập trình, nó thường gây ra khó khăn cho học sinh khi mới bắt đầu làm quen và Giáo viên khi mới bắt đầu viết C++. Vì vậy việc đưa ra nhiều bài toán và code của nó là rất cần thiết. 

3. Tính mới của đề tài 

• Đưa ra được nhiều bài tập mới về chuổi con và code viết bằng  NNLT C++ 
• Đưa ra một số định hướng để giải bài toán về xử lý chuổi con trong NNLT C++  

4. Khả năng ứng dụng và triển khai đề tài 

  Đề tài có thể là tài liệu tham khảo bổ ích cho Học sinh, Giáo viên THPT đặc biệt là Học sinh khá, giỏi. 

5. Đối tƣợng và phạm vi nghiên cứu 

5.1. Đối tƣợng nghiên cứu 

• Học sinh THPT. 
• Giáo viên trường THPT. 
• Các bài toán về xử lý chuổi con. 

5.2. Phạm vi nghiên cứu 

• Bám sát nội dung chương trình Tin học THPT. 
• Mở rộng phù hợp với nội dung thi Học sinh giỏi Tỉnh  

6. Phƣơng pháp và nhiệm vụ nghiên cứu 

6.1. Phƣơng pháp nghiên cứu – Phương pháp phân tích, tổng hợp. 

– Phương pháp thực nghiệm. 

6.2. Nhiệm vụ nghiên cứu 

  Rút ra một số kinh nghiệm để giải các bài toán về xử lý chuổi con khi dạy tin học lớp 11 chương trình Tin học THPT. 

PHẦN II. NỘI DUNG NGHIÊN CỨU 

1. Cơ sở khoa học 

1.1. Cơ sơ lý luận 

Để giải quyết các bài toán về chuỗi con một cách tối ưu, học sinh phải biết khái niệm về chuỗi con, các thuật toán thông dụng; Học sinh phải có kỹ năng nhận dạng bài toán khi được phát biểu dưới nhiều dạng khác nhau và lựa chọn thuật toán thích hợp để giải quyết. 

+) Chuỗi là gì? 

Trong lập trình, chuỗi là một dãy các ký tự được lưu trữ dưới dạng một mảng các ký tự. Ví dụ, chuỗi “hello” có thể được lưu trữ trong mảng char s[] = {‘h’, ‘e’, ‘l’, ‘l’, 

‘o’, ‘\0’}. 

+) Chuỗi con là gì? 

Một chuỗi con là một chuỗi mà có thể được tạo ra từ chuỗi ban đầu bằng cách lấy ra một số ký tự liên tiếp của chuỗi ban đầu. Ví dụ, chuỗi con “ell” được tạo ra từ chuỗi “hello” bằng cách lấy ra 3 ký tự liên tiếp bắt đầu từ vị trí thứ 1. +) Thuật toán tìm chuỗi con 

Để tìm chuỗi con trong C++, ta có thể sử dụng các thuật toán như Vét cạn, Quy hoạch động, phương pháp phát triển xâu con. Mỗi thuật toán có cách hoạt động khác nhau và độ phức tạp thời gian khác nhau, tùy thuộc vào kích thước của chuỗi ban đầu và chuỗi con cần tìm. 

*/ Một số dạng bài toán thƣờng gặp:  

Dạng 1: Cho xâu ký tự S. Yêu cầu: Tìm ra tất cả các xâu con của S thoả mãn điều kiện Q nào đó. 

Dạng 2: Cho xâu ký tự S. Yêu cầu: Đưa ra các đoạn ký tự là xâu con của S thỏa mãn điều kiện Q nào đó. Trong đó điều kiện Q có tính chất: Nếu xâu con A thỏa mãn điều kiện Q thì  thì mọi xâu con liên tục của A cũng thoả mãn điều kiện Q và ta cũng chỉ tính một xâu con là A. 

Dạng 3: Cho xâu ký tự S. Yêu cầu: Tìm xâu con dài nhất của S thỏa mãn điều kiện Q. 

  Trường hợp 1: Điều kiện Q có tính chất: Xâu con A thỏa mãn điều kiện Q nhưng các xâu con của A có thể không thỏa mãn Q. 

Trường hợp 2: Điều kiện Q có tính chất: Nếu xâu con A thỏa mãn điều kiện Q thì mọi xâu con liên tục của A cũng thoả mãn tính chất Q và các ký tự của A không được xét vào xâu con khác. 

1.2. Cơ sơ thực tiễn 

  Chúng tôi đã tìm tòi các bài toán về chuổi con, nghiên cứu kỹ các code và đúc rút ra một số kinh nghiệm cho bản thân trong quá trình dạy học. 

2. Thực trạng 

  Các bài toán về xử lý chuổi con là các bài toán cơ bản. Nhưng trong thực tế vấn đề dạy và học về kiểu chuổi bằng NNLT C++, Giáo viên và Học sinh còn gặp một số khó khăn và hạn chế  

3. Phƣơng hƣớng và giải pháp 

3.1. Một số định hƣớng để viết code cho các bài toán xử lý chuổi con viết bằng NNLT C++  

Dưới đây là một số định hướng viết code cho các bài toán xử lý chuỗi con bằng C++: 

1. Sử dụng chuỗi đệ quy (Recursion): Đây là phương pháp tiếp cận bài toán bằng cách sử dụng hàm đệ quy để phân tích chuỗi ban đầu thành các chuỗi con. Điều này đặc biệt hữu ích trong việc tìm kiếm chuỗi con phù hợp với một mẫu chuỗi. 
2. Sử dụng vòng lặp (Loop): Sử dụng vòng lặp để duyệt qua tất cả các ký tự trong chuỗi ban đầu và tạo ra các chuỗi con từ ký tự hiện tại đến ký tự cuối cùng của chuỗi ban đầu. Điều này đặc biệt hữu ích trong việc tìm kiếm chuỗi con có độ dài cố định. 
3. Sử dụng thuật toán động (Dynamic Programming): Đây là một phương pháp tiếp cận bài toán bằng cách sử dụng bảng để lưu trữ các kết quả phụ thuộc vào các bài toán con đã được giải quyết trước đó. Điều này đặc biệt hữu ích trong việc giải quyết các bài toán có quy mô lớn. 
4. Sử dụng thuật toán KMP (Knuth-Morris-Pratt): Đây là một thuật toán tối ưu cho việc tìm kiếm chuỗi con phù hợp với một mẫu chuỗi. Thuật toán này sử dụng một bảng tiền xử lý để lưu trữ thông tin về các tiền tố và hậu tố của mẫu chuỗi và sử dụng thông tin này để tìm kiếm chuỗi con trong chuỗi ban đầu. 

Sử dụng thư viện chuỗi (String Library): C++ cung cấp một số thư viện chuỗi hữu ích, chẳng hạn như thư viện <string>, cho phép bạn thực hiện các thao tác chuỗi thông thường, chẳng hạn như tìm kiếm chuỗi con, so