Sáng kiến kinh nghiệm THPT: Phương pháp giải một số bài toán chuỗi con bằng ngôn ngữ lập trình C++

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

Thêm vào BST

Báo xấu

23
lượt xem 12
download

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

Mục đích nghiên cứu sáng kiến nhằm đưa ra được nhiều bài tập mới về chuỗi con và code viết bằng ngôn ngữ lập trình C++; Đưa ra một số định hướng để giải bài toán về xử lý chuỗi con trong ngôn ngữ lập trình C++

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: Phương pháp giải một số bài toán chuỗi con bằng ngôn ngữ lập trình C++

1 SỞ GIÁO DỤC & ĐÀO TẠO NGHỆ AN TRƢỜNG THPT KIM LIÊN SÁNG KIẾN KINH NGHIỆM Đề tài: “PHƢƠNG PHÁP GIẢI MỘT SỐ BÀI TOÁN CHUỔI CON BẰNG NNLT C++” Lĩnh vực: Tin học
2 SỞ GIÁO DỤC & ĐÀO TẠO NGHỆ AN TRƢỜNG THPT KIM LIÊN SÁNG KIẾN KINH NGHIỆM Đề tài: “PHƢƠNG PHÁP GIẢI MỘT SỐ BÀI TOÁN CHUỔI CON BẰNG NNLT C++” Lĩnh vực: Tin học Giáo viên: Nguyễn Quang Hùng – Nguyễn Thị Lƣu Trƣờng THPT Kim Liên Năm học: 2022-2023 Số điện thoại: 0973484114 - 0914527656
1 MỤC LỤC PHẦN 1. ĐẶT VẤN ĐỀ:..……………………………………………………2 1. Lý do chọn đề tài: ………………………………………………...…2 2. Tính cấp thiết của đề tài: ……………………………………………3 3. Tính mới của đề tài: ………………………………………………...3 4. Khả năng ứng dụng và triển khai đề tài: ………………………… ..3 5. Đối tượng và phạm vi nghiên cứu: …………………………………3 PHẦN 2. NỘI DUNG NGHIÊN CỨU ……………..………………………..3 1. Cơ sở khoa học: ……………………………………………………..4 2. Thực trạng của vấn đề: ……………………………………………...4 3. Phương hướng và giải quyết : ……………………………………….5 3.1. Một số định hướng để viết code cho các bài toán xử lý chuổi:…….5 3.2. Vận dụng định hướng để giải một số bài toán kiểu chuổi:………..13 4. Khảo sát sự cấp thiết và tính khả thi của giải pháp:……..…………..26 PHẦN 3. KẾT LUẬN VÀ KHUYẾN NGHỊ: ……………… …………… . 28 TÀI LIỆU THAM KHẢO: ……………………………………………. …29
2 PHẦN I. ĐẶT VẤN ĐỀ 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.
3 - 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
4 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ế
5 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. 5. 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 , 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 sánh chuỗi và cắt chuỗi. Việc sử dụng thư viện chuỗi có thể giúp tiết kiệm thời gian 6. Phương pháp phát triển chuỗi con là cách để tách một phần của một chuỗi ban đầu thành một chuỗi con mới, có độ dài và nội dung khác nhau. Có nhiều cách để phát triển chuỗi con trong C++, nhưng phương pháp chung là bạn cần xác định vị trí bắt đầu và độ dài của chuỗi con 3.2. Vận dụng các định hƣớng trên để giải một số bài toán Giáo viên đưa ra từng dạng bài toán, phân tích đặc điểm bài toán, ý tưởng thuật toán và ví dụ minh họa cho mỗi dạng. Sau đó cho học sinh soạn thảo chương trình rồi tiến hành chấm bài
6 Dạng 1: Bài toán duyệt theo phƣơng pháp vét cạn. 1.1/ Bài toán: Cho chuỗi kí tự S. Hãy tìm ra tất cả các chuổi con của S thoả mãn điều kiện Q. 1.2/ Phân tích: Với bài toán này, đề yêu cầu đưa ra tất cả các chuỗi con (các chuỗi con có thể lồng nhau, có thể giao nhau) nên phải kiểm tra tất cả các chuỗi con. Để kiểm tra hết ta phải duyệt theo phương pháp vét cạn. 1.3/ Ý tưởng thuật toán: Để giải quyết bài toán này trong C++, ta có thể sử dụng phương pháp vét cạn, tức là kiểm tra tất cả các chuỗi con của S có thỏa mãn điều kiện Q hay không. Cụ thể, ta sẽ duyệt qua tất cả các vị trí i, j (i ≤ j) trong chuỗi S và lấy ra chuỗi con từ vị trí i đến j. Sau đó, kiểm tra xem chuỗi con này có thỏa mãn điều kiện Q hay không. Nếu có, ta lưu lại đoạn ký tự tìm được và tiếp tục duyệt đến vị trí tiếp theo. Để kiểm tra chuỗi con có thỏa mãn điều kiện Q hay không, ta cần định nghĩa điều kiện đó. Ví dụ, nếu điều kiện là chuỗi con có chứa chữ số, ta có thể duyệt qua từng ký tự trong chuỗi con và kiểm tra xem ký tự đó có phải là số hay không. Nếu có ít nhất một ký tự là số, ta coi chuỗi con này thỏa mãn điều kiện Q. Sau khi duyệt qua tất cả các vị trí trong chuỗi S, ta sẽ có được tất cả các đoạn ký tự thỏa mãn điều kiện Q. Ta in ra các đoạn này và kết thúc chương trình. Dưới đây là code về cách giải bài toán này trong C++ #include #include using namespace std; int main() { string s; getline(cin, s); // nhập xâu ký tự for (int i = 0; i < s.length(); i++)
7 { for (int j = i; j < s.length(); j++) { string sub = s.substr(i, j - i + 1); // lấy xâu con từ vị trí i đến j // kiểm tra xâu con có thỏa mãn điều kiện Q hay không if (/*Điều kiện Q*/) { cout
8 34 44 55 56 66 Ý tưởng: Để giải quyết bài toán này bằng phương pháp vét cạn, chúng ta có thể thực hiện các bước sau: 1. Đọc chuỗi ký tự S từ tệp đầu vào. 2. Duyệt qua tất cả các xâu con của chuỗi S. Với mỗi xâu con, kiểm tra xem các ký tự trong xâu con đều giống nhau hay không. 3. Nếu xâu con đồng nhất, ghi lại vị trí đầu và cuối của xâu con vào tệp đầu ra. 4. Kết thúc quá trình duyệt và đóng tệp đầu vào và tệp đầu ra. Dƣới đây là đoạn code minh họa cho bài toán này: #include #include #include using namespace std; bool checkSame(string s, int start, int end) { // Hàm kiểm tra xâu con từ vị trí start đến vị trí end có đồng nhất không for(int i = start + 1; i
9 } int main() { ifstream inFile; ofstream outFile; inFile.open("Dong_nhat_1.INP"); outFile.open("Dong_nhat_1.OUT"); if(inFile.fail()) { cout
10 } } inFile.close(); outFile.close(); return 0; } Dạng 2: Bài toán duyệt theo phƣơng pháp phát triển chuổi con. 2.1/ Bài toán: Cho chuổi S. Hãy đưa ra các đoạn ký tự là chuổi 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 chuổi con A thỏa mãn điều kiện Q thì mọi chuổi con liên tục của A cũng thoả mãn tính chất Q và lúc đó ta cũng chỉ tính một chuổi con là A. 2.2/ Phân tích: Với dạng này yêu cầu chuổi con thoả mãn Q có các tính chất trên nên ta sẽ duyệt theo phương pháp Phát triển chuổi con (kiểm tra sự thỏa mãn của phần tử tiếp theo để bổ sung vào đoạn đã tìm được). 2.3/ Ý tưởng thuật toán: Đầu tiên, ta khởi tạo một chuỗi rỗng, sau đó duyệt qua từng ký tự của chuỗi S. Tại mỗi bước lặp, ta thêm ký tự đó vào cuối chuỗi rỗng để tạo thành một chuỗi con mới. Sau đó, ta kiểm tra xem chuỗi con mới này có thỏa mãn điều kiện Q hay không. Nếu thỏa mãn, ta lưu trữ chuỗi con này vào một danh sách các chuỗi con thỏa mãn Q. Sau khi duyệt qua toàn bộ chuỗi S, ta sẽ có danh sách các chuỗi con của chuỗi S thỏa mãn điều kiện Q. Ví dụ, nếu điều kiện Q là "chuỗi con chứa ít nhất một ký tự 'a'", Code minh họa nhƣ sau #include #include #include using namespace std;
11 int main() { string s = "abcbadefga"; vector substrings; string sub = ""; for(int i = 0; i < s.length(); i++) { sub += s[i]; if(sub.find('a') != string::npos) { substrings.push_back(sub); } } cout
12 Cho tệp văn bản DONG_NHAT_2.INP gồm 1 dòng chứa xâu ký tự S với độ dài không quá 250 ký tự. Hãy cắt xâu S thành các xâu con đồng nhất, sao cho số xâu con là ít nhất. Kết quả ghi vào tệp DONG_NHAT_2.Out mỗi dòng là 1 xâu con đồng nhất. Dong_nhat_2.Inp Dong_nhat_2.OUT hooocc h ooo cc Ý tưởng: Đầu tiên, ta duyệt qua từng ký tự của chuỗi S. Tại mỗi bước lặp, ta kiểm tra xem ký tự hiện tại có giống với ký tự trước đó hay không. Nếu giống nhau, ta thêm ký tự đó vào chuỗi con hiện tại. Nếu khác nhau, ta lưu trữ chuỗi con hiện tại vào danh sách các chuỗi con đồng nhất và khởi tạo chuỗi con mới bắt đầu từ ký tự hiện tại. Sau khi duyệt qua toàn bộ chuỗi S, ta sẽ có danh sách các chuỗi con đồng nhất của chuỗi S. Code bài toán: #include #include #include #include using namespace std; int main() { ifstream infile("DONG_NHAT_2.INP"); ofstream outfile("DONG_NHAT_2.OUT"); string s; getline(infile, s); vector substrings;
13 string sub = ""; for(int i = 0; i < s.length(); i++) { if(sub == "" || s[i] == sub[0]) { sub += s[i]; } else { substrings.push_back(sub); sub = ""; sub += s[i]; } } substrings.push_back(sub); // lưu trữ chuỗi con cuối cùng for(int i = 0; i < substrings.size(); i++) { outfile
14 Dạng 3: Bài toán tìm xâu con dài nhất. 3.1/ Bài toán: Cho chuỗi ký tự S. Tìm ra chuỗi con dài nhất thoả mãn một tính chất Q nào đó. 3.2/ Phân tích: Bài toán trên có thể giải quyết bằng một số phương pháp như: 1. Vét cạn: Kiểm tra tất cả các chuỗi con của chuỗi S và kiểm tra tính chất Q của từng chuỗi con. Lưu lại độ dài của chuỗi con thoả mãn tính chất Q và trả về chuỗi con dài nhất. 2. Sử dụng thuật toán Quy hoạch động: Dùng một mảng dp để lưu độ dài của chuỗi con dài nhất thoả mãn tính chất Q tại mỗi vị trí trong chuỗi S. Từ đó, ta có thể tính toán độ dài của chuỗi con dài nhất thoả mãn tính chất Q tại vị trí cuối cùng của chuỗi S. 3. Sử dụng phương pháp phát triển chuổi con. 3.3/ Ý tưởng giải bài toán trên bằng phương pháp phát triển chuổi con 1. Tạo ra tất cả các chuỗi con có thể từ chuỗi S. 2. Kiểm tra tính chất Q của từng chuỗi con. 3. Lưu lại độ dài của chuỗi con thoả mãn tính chất Q và trả về chuỗi con dài nhất. Ta có thể cài đặt đoạn code nhƣ sau: #include #include using namespace std; // Hàm kiểm tra tính chất Q của một chuỗi con bool check(string str) { // Code kiểm tra tính chất Q của chuỗi con ở đây } // Hàm tìm chuỗi con dài nhất thoả mãn tính chất Q string longestSubstring(string s) {
15 string result = ""; // Chuỗi con dài nhất thoả mãn tính chất Q int n = s.length(); // Phát triển các chuỗi con và kiểm tra tính chất Q của chúng for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { string sub = s.substr(i, j-i+1); // Tạo chuỗi con từ vị trí i đến j if (check(sub) && sub.length() > result.length()) { // Nếu chuỗi con thoả mãn tính chất Q và dài hơn chuỗi con hiện tại result = sub; // Lưu lại chuỗi con mới } } } return result; } // Hàm main để kiểm tra int main() { string s; cin >> s; string result = longestSubstring(s); cout
16 chuỗi S. Nếu có nhiều chuỗi con thỏa mãn thì đưa ra dãy đầu tiên tính từ trái sang phải. Kết quả ghi vào tệp Dong_nhat_3.OUT gồm 1 dòng là chuỗi con tìm được. Ví dụ: Dong_nhat_3.Inp Dong_nhat_3.OUT hooocc ooo Ý tưởng:  Duyệt từ đầu đến cuối chuỗi S và lưu trữ số lượng ký tự đồng nhất liên tiếp tại mỗi vị trí. Ví dụ, nếu chuỗi S là "abbbccdd", ta sẽ có mảng count = {1, 3, 2, 2, 1, 1, 1, 1}.  Duyệt qua mảng count và tìm phần tử lớn nhất. Lưu lại vị trí của phần tử lớn nhất đó.  Sử dụng vị trí lớn nhất đã tìm được và độ dài phần tử lớn nhất đó để trích xuất chuỗi con đồng nhất có độ dài lớn nhất từ chuỗi S. Code của bài toán: #include #include using namespace std; int main() { string S; cin >> S; int n = S.length(); int count[n]; for (int i = 0; i < n; i++) { int j = i + 1; while (j < n && S[j] == S[i]) j++; count[i] = j - i; } int max_len = 0, max_pos = 0; for (int i = 0; i < n; i++) { if (count[i] > max_len) {
17 max_len = count[i]; max_pos = i; } } string result = S.substr(max_pos, max_len); cout
18 #include using namespace std; int main() { ifstream fin("XAUGON.INP"); ofstream fout("XAUGON.OUT"); string S, SG; fin >> S; char prev_char = '\0'; for (char c : S) { if (c != prev_char) { SG += c; prev_char = c; } } fout