Sáng kiến kinh nghiệm Phương pháp giải một số bài toán chuỗi con bằng NNLT C++

tra int main() {
string s; cin >> s;
string result = longestSubstring(s); cout << result << endl;
return 0;
}
/ Ví dụ:
Bài toán: CHUỖI ĐỒNG NHẤT
Chuỗi ký tự được gọi là đồng nhất khi tất cả các ký tự trong chuỗi đều giống
nhau.
Cho tệp văn bản Dong_nhat_3.INP gồm 1 dòng chứa chuỗi ký tự S với độ
dài không quá 104 ký tự. Hãy đưa ra chuỗi con đồng nhất có độ dài lớn nhất của
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.
Dong_nhat_3.Inp
Dong_nhat_3.OUT
hooocc
ooo

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ụ:
Ý 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) {
max_len = count[i]; max_pos = i;
}
}
string result = S.substr(max_pos, max_len); cout << result << endl;
return 0;
}
3.4 – BÀI TẬP ÁP DỤNG:
Để học sinh có năng lực phân tích, vận dụng các phương pháp. Học sinh cùng giáo viên giải một số bài tập.
1/ Giải một số đề thi HSG Tỉnh Nghệ An:
Bài 1. RÚT GỌN XÂU (Đề thi HSG tỉnh lớp 12 năm học 2009 – 2010)
Cho một xâu S chỉ gồm các chữ cái in thường với độ dài tối đa 250 ký tự. Em hãy viết chương trình để tạo ra xâu SG từ xâu S bằng cách xóa các ký tự liên tiếp giống nhau trong xâu S và chỉ để lại một kí tự đại diện trong đoạn đó.
Dữ liệu vào: Đọc từ file văn bản XAUGON.INP chứa xâu S chỉ gồm các chữ cái in thường.
Kết quả: Ghi ra file văn bản XAUGON.OUT là xâu SG tìm được.
Ví dụ:
XAUGON.INP
XAUGON.OUT
Hhooocccsssiiiiinnnhhh
hocsinh
Phân tích bài toán:
Với bài toán này ta có thể hiểu: Xâu SG là kết quả của việc nối ký tự đầu tiên của các xâu con đồng nhất trong xâu S. Vì vậy ta có thể duyệt theo phương pháp phát triển xâu con để xác định ký tự đầu dãy con.
Code bài toán: #include #include 
#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 << SG << endl;
fin.close();
fout.close(); return 0;
}
Bài 2: NÉN XÂU (Đề thi HSG tỉnh lớp 12 năm học 2011 – 2012)
Một xâu ký tự có thể nén lại bằng 1 xâu mới bằng cách nén các ký tự giống nhau đứng cạnh nhau. Ví dụ trong xâu AAAA sẽ nén thành 4A. Hãy lập trình để nén 1 xâu ký tự in hoa theo cách trên.
Dữ liệu: Vào từ file văn bản NENXAU.INP một xâu, mà các ký tự là chữ cái in hoa.
Kết quả: Ghi vào xâu văn bản NENXAU.OUT một xâu ký tự sau khi nén.
Ví dụ:
NENXAU.INP
NENXAU.OUT
MMAABBBEEEEZH
2M2A3B4EZH
Phân tích bài toán:
Yêu cầu bài toán chính là xác định độ dài và ký tự của các xâu con đồng nhất. Kết quả ghi vào tệp nên ta không cần sử dụng xâu phụ để lưu kết quả mà ghi trực tiếp sau mỗi xâu con tìm được. Sử dụng phương pháp phát triển xâu con ta có chương trình như sau.
Code bài toán #include #include #include using namespace std; int main() {
ifstream inFile("NENXAU.INP"); ofstream outFile("NENXAU.OUT");
string inputStr; getline(inFile, inputStr);
string compressedStr;
char currentChar = inputStr[0]; int count = 1;
for (int i = 1; i < inputStr.length(); i++) { if (inputStr[i] == currentChar) {
count++;
} else {
if (count == 1) {
compressedStr += currentChar;
} else {
compressedStr += to_string(count) + currentChar;
}
currentChar = inputStr[i]; count = 1;
}
}
if (count == 1) {
compressedStr += currentChar;
} else {
compressedStr += to_string(count) + currentChar;
}
outFile << compressedStr;
inFile.close(); outFile.close();
return 0;
}
Bài 3. XÂU CON CHUNG DÀI NHẤT
(Đề thi HSG tỉnh lớp 12 năm học 2012 – 2013)
Xâu S được gọi là xâu con chung của xâu S1 và xâu S2 nếu xâu S là một dãy các ký tự liên tiếp trong S1 và cũng là dãy các ký tự liên tiếp trong S2.
Yêu cầu: Cho hai xâu kí tự S1 và S2 (có không quá 255 ký tự). Hãy tìm một xâu con chung S dài nhất của hai xâu S1 và S2. Ví dụ: S1 = ’Ky thi học sinh gioi Tinh môn Tin hoc’, S2 = ’hoc sinh gioi mon Tin hoc’ thì S = ‘hoc sinh gioi '.
Dữ liệu vào từ file văn bản Bai2.inp:
Dòng đầu tiên ghi xâu S1;
Dòng thứ hai ghi xâu S2.
Kết quả ghi ra file văn bản Bai2.out: Chỉ một số duy nhất là độ dài của xâu con chung dài nhất S. (Nếu hai xâu S1, S2 không có kí tự nào chung thì ghi số 0).
Ví dụ:
Bai2.inp
Bai2.inp
Ky thi hoc sinh gioi Tinh mon tin hoc hoc sinh gioi mon Tin hoc
14
Phân tích bài toán:
Đây là bài toán tìm chuỗi con dài nhất của một chuỗi trong chuỗi còn lại. Ta có thể sử dụng quy hoạch động.
Cụ thể, ta có thể tạo một ma trận dp với kích thước (m+1)x(n+1) (m, n là độ dài của hai xâu S1 và S2), trong đó phần tử dp[i][j] sẽ lưu trữ độ dài của xâu con chung dài nhất của đoạn S1[1...i] và đoạn S2[1...j]. Vậy nếu kí tự thứ i trong S1 và kí tự thứ j trong S2 giống nhau, thì ta có dp[i][j] = dp[i-1][j-1] + 1, ngược lại thì ta có dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
Kết quả cần tìm sẽ nằm ở ô dp[m][n] của ma trận. Code bài toán:
#include #include using namespace std;
const int MAX = 255; int dp[MAX][MAX];
int LCS(string s1, string s2) { int m = s1.length();
int n = s2.length();
memset(dp, 0, sizeof(dp)); // Khởi tạo ma trận dp ban đầu
// Xây dựng ma trận dp
for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) {
if (s1[i-1] == s2[j-1]) {
dp[i][j] = dp[i-1][j-1] + 1;
} else {
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
}
}
return dp[m][n];
}
int main() { string s1, s2;
getline(cin, s1); // Nhập xâu S1 getline(cin, s2); // Nhập xâu S2
int res = LCS(s1, s2);
cout << res << endl; // Xuất kết quả
return 0;
}
Bài 6. XÂU CON	(Đề thi HSG tỉnh lớp 11 năm học 2014 – 2015)
Cho trước một xâu có độ dài L (1 < L < 2.105) chỉ chứa các chữ cái thường trong bảng chữ cái tiếng Anh.
Yêu cầu:
Hãy tìm xâu con dài nhất xuất hiện ít nhất 2 lần trong xâu đã cho.
Dữ liệu vào từ file XAU.INP:
Dòng đầu là một số nguyên L. Dòng sau là một xâu có độ dài L.
Kết quả ghi ra file XAU.OUT: Chỉ một số duy nhất là độ dài của xâu con tìm được, nếu không tìm được thì ghi ra 0.
Ví dụ:
XAU.INP
XAU.OUT
XAU.INP
XAU.OUT
XAU.INP
XAU.OUT
11
sabcabcfabc
3
18
trutrutiktiktappop
4
6
abcdef

0
Phân tích bài toán:
Để giải quyết bài toán này, ta có thể sử dụng thuật toán KMP để tìm kiếm chuỗi con xuất hiện ít nhất 2 lần trong xâu đã cho.
#include #include #include #include 
using namespace std;
vector prefixFunction(string s) { int n = s.length();
vector pi(n, 0);
for (int i = 1; i < n; i++) { int j = pi[i-1];
while (j > 0 && s[i] != s[j]) { j = pi[j-1];
}
if (s[i] == s[j]) { j++;
}
pi[i] = j;
}
return pi;
}
int main() {
ifstream input("XAU.INP"); ofstream output("XAU.OUT"); int n;
string s;
input >> n >> s;
vector pi = prefixFunction(s); int result = 0;
for (int i = 1; i < n; i++) {
if (pi[i] > 0 && pi[i] < i && pi[i] == pi[pi[i]-1]) { result = max(result, pi[i]);
}
}
output << result << endl; return 0;
}
3.5. Một số bài tập mở rộng: Bài 1:
Trong lập trình khái niệm từ được hiểu là một dãy ký tự không chứa dấu
cách. Cho tệp văn bản XAU.INP chứa 1 xâu ký tự trong đó có cả chữ cái và chữ số. Hãy viết chương trình xử lý các yêu cầu sau:
a/ Tách xâu chưa chuẩn hoá thành mỗi từ 1 dòng.
b/ Loại bỏ các dấu cách thừa trong xâu để giữa các từ chỉ còn 1 dấu cách. c/ Đưa ra từ dài nhất trong xâu.
d/ Đưa ra xâu con tạo thành số nguyên lớn nhất.
Các kết quả ghi vào tệp văn bản lần lượt là A.OUT, B.OUT, C.OUT, D.OUT, E.OUT.
Gợi ý:
a/ Xác định các chuỗi con không chứa các dấu cách và ghi chúng trên 1
dòng. Nên duyệt phương pháp phát triển chuỗi con.
b/ Xác định các chuỗi con có độ dài lớn hơn 1 chứa toàn dấu cách và xoá chuỗi con đó chỉ trừ 1 dấu cách. Nên duyệt phương pháp phát triển chuỗi con.
c/ Ta có thể sử dụng 1 trong 3 cách duyệt. Nhưng duyệt theo phương pháp phát triển dãy con là tốt nhất
d/ Trước hết ta nên duyệt để lấy ra các xâu con số có độ dài lớn nhất rồi so sánh các xâu con đó để tìm xâu lớn nhất. Nên duyệt theo phương pháp kiểm tra độ dài.
Bài 2: Trong đợt tập luyện biểu diễn văn nghệ chào mừng ngày khai giảng của trường THPT Kim Liên. Có n thành viên tham gia gồm cả nam và nữ. Các thành viên đã được sắp thành 1 hàng tăng dần theo chiều cao của mỗi người. Cô giáo phụ trách văn thể muốn chọn ra một nhóm gồm những thành viên liên tiếp nhau để chiều cao không quá lệch nhau và có số lượng nam bằng nữ để tập luyện.
a/ Có bao nhiêu cách chọn thỏa mãn yêu cầu trên?
b/ Để có một tiết mục đồng diễn đẹp mắt cần chọn ra nhóm có nhiều thành viên nhất thỏa mãn yêu cầu. Hỏi số lượng thành viên nhiều nhất mà cô giáo có thể chọn.Em hãy viết chương trình giúp cô giáo biết các cách lựa chọn.
Dữ liệu vào: Cho trong file Vannghe.INP.
- Dòng đầu ghi số nguyên N (1<=N<=250).
-Dòng thứ 2 ghi mô tả các thành viên đứng trong hàng: Là một dãy các ký tự B và G. Trong đó chữ B tương ứng với nam, G tương ứng với nữ.
Dữ liệu ra: Ghi ra tệp Vannghe.Out gồm 2 số nguyên cách nhau bởi 1 dấu cách. Số thứ nhất là đáp án của câu a. Số thứ 2 là đáp án của câu b.
Gợi ý: Để trả lời được câu a ta sử dụng phương pháp vét cạn.
Để trả lời câu b ta có thể sử dụng thêm biến để lưu độ dài lớn nhất trong các cách chọn được ở việc duyệt vét cạn. Nếu yêu cầu ở câu b là viết chương trình tách biệt với câu a thì ta nên duyệt theo phương pháp kiểm tra độ dài.
Bài 3: Qua cầu.
Trong chiến dịch tấn công Thành phố, các chiến sĩ biệt động cần phải qua một chiếc cầu. Thời gian qua cầu hết T phút. Cầu được một trung đội có N lính gác rất nghiêm ngặt. Hàng ngày, người lính thứ i gác từ thời điểm Ai đến thời điểm Bi (thời điểm tính bằng phút). Các chiến sĩ qua cầu an toàn nếu từ thời điểm lên cầu đến khi đi hết cầu không gặp phải người lính gác nào. Cho trước một lịch gác, em hãy cho biết các chiến sĩ biệt động trong ngày có qua được cầu để vào thành phố không? Nếu qua được thì em hãy tìm cho các chiến sỹ thời điểm xuất sớm nhất để qua cầu.
Dữ liệu vào cho từ file văn bản GAC.inp có cấu trúc như sau
+ Dòng đầu tiên ghi 2 số nguyên dương N,T( 0<N<100)
+ N dòng tiếp theo, mỗi dòng ghi 2 số nguyên dương Ai,Bi (Ai < Bi) là lịch gác của người lính thứ i (các số trên một dòng ghi cách nhau một ký tự trắng)
Kết quả ghi ra file văn bản GAC.out có cấu trúc như sau:
Nếu không qua được thì ghi là KHONG, Trong trường hợp qua được dòng đầu tiên ghi CO, dòng thứ 2 ghi thời điểm bắt đầu lên cầu sớm nhất.
Bài 4: Chuỗi đối xứng
Mỗi chuỗi kí tự được gọi là đối xứng nếu nó có không ít hơn 1 kí tự và nếu ta đọc từ phải sang trái hay từ trái sang phải đều giống nhau. Ví dụ ' Z ' , ' TOT ' ,
' NAN ' là các chuỗi đối xứng còn ' NAM ' không phải. Yêu cầu:
Viết chương trình nhận vào chuỗi kí tự cho trước S và hãy cho biết có bao nhiêu chuỗi con khác nhau của S là chuỗi đối xứng. Chuỗi con của S là chuỗi gồm một số kí tự nằm liên tiếp nhau trong S.
Dữ liệu vào cho trong tập tin văn bản CHUOI.INP gồm nhiều dòng, mỗi dòng là một chuỗi kí tự cần xem xét(các chuỗi có độ dài không quá 80 kí tự ).
Kết quả ghi trong tập tin văn bản CHUOI.OUT có số dòng bằng với số dòng của CHUOI.INP. Mỗi dòng chứa một số nguyên là con số cho biết số chuỗi con đối xứng của chuỗi ở dòng tương ứng trong CHUOI.INP.
Ví dụ:
Dữ liệu vào:
Dữ liệu ra:
Z
1
TOT
3
NANG
4
Khảo sát sự cấp thiết và tính khả thi của các giải pháp đề xuất
4.1) Những vấn đề chung về khảo sát - Mục đích khảo sát:
Thông qua khảo sát nhằm khẳng định sự cấp thiết và tính khả thi của các giải pháp, để từ đó hoàn thiện các giải pháp phù hợp với thực tiễn.
- Đối tượng khảo sát:
Chúng tôi đã tiến hành khảo sát ý kiến của 190 em học sinh và 4 GV ở trường THPT Kim Liên
TT
Đối tượng
Số lượng
1
Học sinh học khối A
199
2
Giáo viên
4
Tổng
213
- Thời gian tiến hành khảo sát: tháng 04/2023.
4.2. Sự cấp thiết của các giải pháp đề xuất Đánh giá sự cấp thiết của các giải pháp đề xuất
TT
Các giải pháp
Các thông số

X
Mức

X
Mức

X
Mức

X
Mức
4
3
2
1
1
Xây dựng các dạng bài tập
về chuổi
50
200
140
420
10
20
13
13
2
Trình bày các ví dụ mẫu và
lời giải chi tiết
60
240
145
435
5
10
3
3
3
Hệ thống các bài tập để ôn
luyện về chuổi
70
280
140
420
3
6


4
Lựa chọn xây dựng các
dạng bài tập về chuổi
55
220
147
441
8
16
3
3
Tổng
235
940
572
1716
26
52
19
19

4.3. Tính khả thi của các giải pháp đề xuất Đánh giá tính khả thi các giải pháp đề xuất
TT
Các giải pháp
Các thông số

X
Mức

X
Mức

X
Mức

X
Mức
4
3
2
1
1
Xây dựng các dạng bài tập
về chuổi
60
240
145
435
8
16


2
Trình bày các ví dụ mẫu và
lời giải chi tiết
65
260
145
435
3
6


3
Hệ thống các bài tập để ôn
luyện về chuổi
55
220
150
450
8
16


4
Lựa chọn xây dựng các
dạng bài tập về chuổi
45
180
140
420
25
50
3
3
Tổng
225
900
580
1740
44
88
3
3

PHẦN 3. KẾT LUẬN VÀ KHUYẾN NGHỊ
Kết luận
Hiện nay hầu hết các lĩnh vực trong xã hội đã ứng dụng CNTT để giải quyết các công việc một cách nhanh chóng, chính xác và hiệu quả hơn. Trong đó, các ngôn ngữ lập trình, các nhà lập trình chuyên nghiệp đóng vai trò rất quan trọng trong việc xây dựng các chương trình ứng dụng để phục vụ cho cuộc sống.
Bởi vậy, việc phát hiện những học sinh có năng lực, yêu thích lập trình và bồi dưỡng HSG Tin học trở thành một việc làm quan trọng và cấp thiết, góp phần phát triển đội ngũ lập trình viên, phát triển nền kinh tế, tri thức của đất nước.
Đề tài này được xây dựng cũng với mục đích trên và hiệu quả của nó đã được chứng minh trong thực tiễn, qua quá trình bồi dưỡng HSG Tin học
Khuyến nghị
Trong quá trình dạy học mỗi thầy cô cần cố gắng xây dựng nội dung khoa học, lựa chọn phương pháp phù hợp, thu hút, tạo sự hứng thú, tạo động cơ học tập cho học sinh với bộ môn Tin học.
Đề tài của chúng tôi hoàn thành nhờ vào sự giúp đỡ của các bạn bè và đồng nghiệp. Chúng tôi xin chân thành cám ơn thầy cô và các bạn bè đồng nghiệp đã giúp đỡ hoàn thành sáng kiến này.
Rất mong tiếp tục nhận được sự góp ý, nhận xét của các đồng nghiệp để chúng tôi có thêm kinh nghiệm và đạt kết quả tốt hơn trong công tác dạy học.
Chúng tôi xin chân thành cảm ơn!
Nam Đàn, Ngày 24 tháng 04 năm 2023.
NGƯỜI THỰC HIỆN
Nguyễn Quang Hùng	Nguyễn Thị Lưu
TÀI LIỆU THAM KHẢO
Hồ Sĩ Đàm (chủ biên), Đỗ Đức Đông, Lê Minh Hoàng, Nguyễn Thanh Hùng (2009), Tài liệu giáo khoa chuyên tin, NXB Giáo dục.
Hồ Sĩ Đàm (chủ biên), Hồ Cẩm Hà, Trần Đỗ Hùng, Nguyễn Đức Nghĩa, Nguyễn Thanh Tùng, Ngô Ánh Tuyết (2008), Sách giáo khoa Tin học 11, NXB Giáo dục .
Trang Web laptrinhphothong.vn
Trang web thptchuyenntucoder.vn