SỞ GIÁO DỤC VÀ ĐÀO TẠO THANH HOÁ
TRƯỜNG THPT THƯỜNG XUÂN 2
SÁNG KIẾN KINH NGHIỆM
XÂY DỰNG CHUYÊN ĐỀ KIỂU XÂU ĐỂ NÂNG CAO
CHẤT LƯỢNG BỒI DƯỠNG HỌC SINH GIỎI TIN HỌC Ở
TRƯỜNG THPT THƯỜNG XUÂN 2
Người thực hiện: Lê Thị Hoa
Chức vụ: Giáo viên
SKKN thuộc môn: Tin học
THANH HOÁ NĂM 2020
MỤC LỤC
Mở đầu ....................................................................................................................1
1.1. Lí do chọn đề tài.................................................................................................1
1.2. Mục đích nghiên cứu..........................................................................................1
1.3. Đối tượng nghiên cứu........................................................................................1
1.4. Phương pháp nghiên cứu....................................................................................1
2. Nội dung sáng kiến kinh nghiệm.......................................................................2
2.1. Cơ sở lí luận của sáng kiến kinh nghiệm...........................................................2
2.2. Thực trạng vấn đề trước khi áp dụng sáng kiến kinh nghiệm............................2
2.3. Các giải pháp đã sử dụng để giải quyết vấn đề..................................................3
2.4. Hiệu quả của sáng kiến....................................................................................20
3. Kết luận, kiến nghị............................................................................................20
2
1. Mở đầu
1.1. Lí do chọn đề tài
Người xưa đã từng nói: “Hiền tài là nguyên khí của quốc gia, nguyên khí
thịnh thì thế nước mạnh mà hưng thịnh, nguyên khí suy thì thế nước yếu mà thấp
hèn” [4]. Vì Vậy bồi dưỡng học sinh giỏi là một nhiệm vụ quan trọng trong việc
nâng cao chất lượng giáo dục, bồi dưỡng nhân tài cho quê hương, đất nước. Là một
trong những nhiệm vụ chuyên môn quan trọng của nhà trường. Bồi dưỡng học sinh
giỏi là một công việc khó khăn và lâu dài, đòi hỏi nhiều công sức của thầy và trò.
Trong thực tế đối với việc bồi dưỡng học sinh giỏi môn tin học, việc giúp
học sinh giải được một đề thi học sinh giỏi cấp tỉnh, cấp quốc gia thì một trong các
kiểu dữ liệu được sử dụng nhiều nhất trong các đề thi học sinh giỏi là kiểu dữ liệu
xâu. Sau thời gian được phân công bồi dưỡng học sinh giỏi tại trường THPT
Thường Xuân 2, bản thân tôi nhận thấy chuyên đề kiểu xâu rất hay bởi có thể
chuyển đổi một số dạng bài toán ở kiểu dữ liệu khác về kiểu dữ liệu này để giải
quyết, đặc biệt với các dạng bài toán có kiểu dữ liệu số lớn ngoài phạm vi lưu trữ
của các kiểu dữ liệu số nếu không chuyển về kiểu xâu thì thuật toán rất khó và phức
tạp, học sinh khó hiểu và không nắm bắt được, nhưng khi xử lí bằng kiểu xâu lại
làm cho thuật toán đơn giản đi rất nhiều, học sinh dễ dàng vận dụng và giải quyết
được các bài toán một cách triệt để, thế nhưng để biết cách vận dụng linh hoạt các
thao tác xử lý trên kiểu dữ liệu này vào từng bài toán cụ thể không phải là dễ và
chưa có tài liệu nào hướng dẫn. Với mong muốn phần nào giúp học sinh dễ dàng
nhận diện được các dạng bài tập và biết cách vận dụng các kiến thức kiểu xâu để
giải quyết các dạng bài tập đó một cách dễ dàng và hiệu quả, tôi đã tham khảo rất
nhiều tài liệu từ nhiều nguồn khác nhau như: qua sách, báo, các đề học sinh giỏi
các năm gần đây của tỉnh Thanh Hóa nói riêng và nhiều tỉnh khác trên cả nước nói
chung, các nguồn tài liệu trên Internet, vốn kiến thức và kinh nghiệm dạy học của
bản thân để viết tài liệu bồi dưỡng cho học sinh trong đội tuyển học sinh giỏi và
thấy có hiệu quả. Với những lí do trên tôi chọn đề tài: “Xây dựng chuyên đề kiểu
xâu để nâng cao chất lượng bồi dưỡng học sinh giỏi tin học ở trường THPT
Thường Xuân 2” để giúp các em học sinh có nguồn tài liệu tham khảo cũng như
các giáo viên bồi dưỡng học sinh giỏi ở trường THPT Thường xuân 2 có thêm
nguồn tài liệu rèn luyện cho học sinh.
1.2. Mục đích nghiên cứu
Nâng cao chất lượng ôn thi học sinh giỏi, từ đó góp phần nâng cao hiệu quả
dạy học Tin học 11 tại Trường THPT Thường Xuân 2 nói riêng và bộ môn tin học
nói chung.
1.3. Đối tượng nghiên
- Kiểu dữ liệu xâu và các dạng xử lý xâu.
- Học sinh trong đội tuyển học sinh giỏi tin học trường THPT Thường Xuân
2 năm học 2019-2020.
1.4. Phương pháp nghiên cứu
- Xây dựng cơ sở lý thuyết.
1
- Thu thập thông tin trong sách, báo, trên Internet, kinh nghiệm giảng dạy.
- Sử dụng phần mềm FreePascal/Turbo Pascal để viết chương trình.
2. Nội dung sáng kiến kinh nghiệm
2.1. Cơ sở lí luận của sáng kiến
Kiểu xâu là kiểu dữ liệu có cấu trúc được giới thiệu trong chương trình sách
giáo khoa tin học 11_ “ bài 12 _Kiểu xâu” . Sau khi học lý thuyết kiểu xâu đa số học
sinh nắm bắt được xâu là gì? Độ dài của xâu? Biết khai báo biến xâu như thế nào.
Nhưng khi làm việc với xâu thì các em còn lúng túng với việc áp dụng các hàm, thủ
tục và các thao tác xử lý xâu để giải quyết các bài toán thực tế, các câu hỏi vì sao
‘23’+‘9’ = ‘239’, muốn thực hiện được phép tính ‘23’+ ‘9’ = 32 liệu có thực hiện
được không? Muốn thực hiện được thì phải làm cách nào? Và nhiều các câu hỏi
tương tự khác. Vậy làm thế nào để học sinh có thể giải quyết triệt để các bài toán liên
quan đến kiểu dữ liệu xâu hoặc chuyển các kiểu dữ liệu khác về kiểu xâu để vận
dụng xử lý được các bài toán mang tính thực tế có trong các đề thi học sinh giỏi.
Bản thân tôi được sự tín nhiệm, tin tưởng của nhà trường đã phân công bồi
dưỡng học sinh giỏi, nên tôi đã trăn trở, tìm tòi nhiều nguồn tài liệu, dành nhiều
tâm huyết, thời gian nghiên cứu để công việc bồi dưỡng học sinh giỏi đạt kết quả
tốt nhất.
2.2. Thực trạng của vấn đề
Trong các đề thi học sinh giỏi cấp tỉnh, cấp quốc gia kiểu dữ liệu xâu là một
kiểu dữ liệu có cấu trúc thường được sử dụng 50 - 60% trong các đề thi. Tuy nhiên
phần kiểu xâu chỉ được được phân phối 4 tiết trong chương trình sách giáo khoa
Tin học 11 với vẻn vẹn 2 tiết lý thuyết và 2 tiết thực hành. Với lượng kiến thức
được cung cấp trong sách giáo khoa tin học 11 học sinh chỉ mới giải quyết được
các bài tập dạng xâu đơn giản. Thế nhưng bài tập về kiểu dữ liệu xâu có trong các
đề thi lại rất khó và đa dạng, với lượng kiến thức nhỏ được cung cấp trong sách
giáo khoa như vậy chưa đủ để giải quyết được các bài toán có trong các đề thi.
Học sinh trường THPT Thường Xuân 2 chiếm gần 80% là người dân tộc thiểu
số, 100% học sinh sống ở vùng đặc biệt khó khăn, đa số học sinh khả năng tư duy
chưa cao, các em chỉ học máy móc, học vẹt nên việc tự lập trình giải một bài toán
đối với học sinh là rất khó. Mặt khác kiến thức về lập trình cũng khá mới mẻ với
học sinh, đặc biệt với chương trình tin học lớp 11 yêu cầu học sinh phải có tư duy
về toán học tốt, hiểu rõ bản chất của ngôn ngữ lập trình thì mới viết được một
chương trình hoàn chỉnh, bên cạch đó môn tin học không có trong chương trình thi
THPT quốc gia nên học sinh và phụ huynh chỉ xem tin học là môn học phụ, môn
học giải trí nên chưa có ý thức đầu tư thời gian cho bộ môn này. Vì vậy, việc chọn
tuyển học sinh vào đội tuyển học sinh giỏi tin học là việc khó và bồi dưỡng học
sinh giỏi tin học để có thành tích lại càng khó khăn hơn. Đặc biệt khi giảng dạy cho
học sinh về nội dung kiểu dữ liệu xâu học sinh còn lúng túng, dẫn đến viết chương
trình cho một bài toán cụ thể còn chưa đúng.
Tài liệu về kiểu dữ liệu xâu trên Internet chủ yếu chỉ về kiến thức xử lí xâu ở
dạng đơn giản, chưa phân loại thành các dạng kiến thức thường gặp về kiểu dữ liệu
2
xâu, các đề thi học sinh giỏi thường không có code tham khảo nên nguồn tài liệu
giúp giáo viên bồi dưỡng học sinh giỏi cũng như học sinh trong đội tuyển nghiên
cứu còn hạn chế.
2.3. Các giải pháp sử dụng để giải quyết vấn đề
Với những lí do nên trên để giải quyết vấn đề đặt ra, tôi đã thực hiện các giải
pháp sau:
- Tìm hiểu các kiến thức cơ bản về kiểu dữ liệu xâu: Khái niệm xâu, cách khai
báo, cách nhập xuất kiểu dữ liệu xâu và các thao tác và phép toán xử lý trên xâu.
- Xây dựng các dạng thường gặp với kiểu xâu, đưa ra phương pháp chung để
giải quyết từng dạng bài tập đó và sử dụng phần mềm FreePascal để viết code tham
khảo cho các bài tập vận dụng. Từ đó giúp học sinh biết vận dụng tự phân tích,
định dạng bài tập, tự mình tìm ra lời giải thích hợp cho từng bài toán cụ thể, kích
thích tư duy phân tích, tổng hợp cũng như tư duy linh hoạt, sáng tạo của học sinh
trong lập trình.
o Dạng bài tập kiểu xâu đơn giản
o Dạng bài tập mã hóa và giải mã xâu
o Dạng bài tập xử lý các xâu con
o Dạng bài tập xâu đối xứng
o Dạng bài tập xử lí số nguyên kiểu dữ liệu lớn ngoài phạm vi lưu
trữ của các kiểu dữ liêu số.
Nội dung cụ thể:
1. Các kiến thức cơ bản về kiểu xâu [1]
1.1. Khái niệm:
Xâu là một dãy kí tự nằm trong bộ mã ASCII. Mỗi kí tự là một phần tử của xâu.
Ví dụ: S= ‘Tin Hoc’
+ Tên Xâu: S
+ Số phần tử của xâu: 7= Độ dài xâu
1.2. Khai báo
Var : String[độ dài lớn nhất của xâu];
+ Tên biến xâu gồm một hoặc nhiều biến xâu, nếu nhiều biến xâu mỗi biến cách
một dấu phẩy.
+ Độ dài lớn nhất của xâu là 255. Trong trường hợp bỏ qua khai báo độ dài lớn
nhất của xâu, thì độ dài lớn nhất mặc định là 255.
Chú ý: Trong Free Pascal còn sử dụng kiểu dữ liệu ansiString có kích thước gần
2GB=230B nên thường xem là độ dài của xâu là không giới hạn.
1.3. Nhập, xuất dữ liệu kiểu xâu
- Cách nhập hay xuất kiểu dữ liệu xâu cũng tương tự như các kiểu dữ liệu khác
bằng các thủ tục Read, Readln, Write, Writeln.
1.4. Các thao tác xử lí xâu
1.4.1. Phép ghép xâu Ví dụ: ‘HA’+ ‘NOI’= ‘HANOI’
1.4.2. Phép so sánh xâu
- Các phép so sánh: >, <, =, <>, >=, <=
3
- Quy tắc so sánh:
+ Xâu A lớn hơn xâu B nếu 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à nhỏ
hơn B.
1.4.3. Các hàm và thủ tục xử lí xâu.
a. Thủ tục Delete(S,vt,N) xóa trong xâu S từ vị trí vt, N kí tự.
b. Thủ tục Insert(S1,S2,vt) chèn xâu S1 vào xâu S2 từ vị trí vt.
c. Hàm Copy(S,vt,N) sao chép trong xâu S từ vị trí Vt, N kí tự.
d. Hàm Length(S) cho độ dài của xâu S.
e. Hàm Upcase(ch) trả về kết quả là chữ cái in hoa nếu ch là chữ thường và giữ
nguyên ch trong trường hợp ngược lại.
f. Ord(ch) Trả về giá trị là mã ASCII của ch.
g. Chr (ord(ch)+32) trả về kết quả là chữ cái in thường (nếu ch là chữ in hoa).
h. Pos(S1,S2) trả về vị trí đầu tiên xuất hiện xâu S1 trong xâu S2.
i. Val(So,Xau,code) chuyển dữ liệu số từ biến so thành xâu kí tự lưu vào biến xau.
Nếu chuyển đổi thành công thì biến code = 0, ngược lại biến code <> 0.
k. Str(Xau,So) chuyển dữ liệu kiểu xâu ở biến xau thành kiểu số và lưu vào biến so.
2.
Các dạng kiến thức thường gặp với kiểu xâu
2.1. Dạng bài tập kiểu xâu đơn giản
Phương pháp chung: Đây là dạng cơ bản thường gặp, việc biến đổi xâu được thực
hiện trên mỗi ký tự trong xâu nên cần nắm rõ các hàm, thủ tục trên kiểu dữ liệu xâu
đã giới thiệu ở mục 1.4 ở trên để vân dụng một cách linh hoạt vào từng bài tập cụ
thể trong thực tế.
Bài tập vận dụng:
Bài 1. Nén xâu (Đề HSG tỉnh Hà Tĩnh năm 2013-2014) [3]
Một xâu kí tự có thể “nén” theo cách sau: Một xâu con gồm n>1 kí tự giống
nhau, chẳng hạn n kí tự “a” sẽ được ghi thành na. Ví dụ xâu ‘mmmbbcd’ sẽ được
nén thành ‘3m2bcd’. Hãy viết chương trình nén xâu theo quy tắc trên.
Dữ liệu vào: Cho trong tệp NEN.INP chứa một xâu kí tự (không quá 200 kí tự)
Dữ liệu ra: Ghi vào tệp NEN.Out xâu đã nén.
Ví dụ:
NEN.INP
NEN.OUT
BbbAaaaceeegmmmm 3b4ac3eg4m
* Code tham khảo
var f,g:text; S,st,xau:string;i,dem:byte;
begin
assign(f,'NEN.inp'); reset(f);
Assign(g,'NEN.out'); Rewrite(g);
readln(f,s);
S:=S+' ';St:=''; dem:=1;
for i:=2 to length(s) do
4
if s[i]=S[i-1] then inc(dem)
else
begin
str(dem,xau);
if dem >1 then st:=st+xau+S[i-1] else st:=st+s[i-1];
dem:=1;
end;
writeln(g,st);Close(f); Close(g);
end.
Bài 2. Tỉ lệ xuất hiện
Cho một xâu chỉ chứa các kí tự ‘A’.. ‘Z’ hoặc ‘a’.. ‘z’ có độ dài không quá
255 lấy ra từ tệp TLXH.INP. Hãy thực hiện tính tỉ lệ phần trăm xuất hiện của mỗi
ký tự có trong xâu đó (theo các chữ cái in thường). Kết quả ghi vào tệp
TLXH.OUT, mỗi ký tự in trên 1 dòng (tỉ lệ phần trăm được làm tròn đến một chữ
số phập phân sau dấu phẩy).
Ví dụ:
TLXH.INP
TLXH.OUT
Thihocsinhgioi
c: 7.14%
g: 21.43%
h: 28.57%
i: 14,29%
n:7.14%
o:7.14%
s:7.14%
t:7.14%
* Code tham khảo:
Var Dau:array['a'..'z'] of byte;
S:ansistring;i,n:byte;ch:char;tl:real;f,g:text;
begin
Assign(f,'TLXH.inp'); reset(f);
Assign(g,'TLXH.Out'); Rewrite(g);
Read(f,S);
Fillchar(Dau,sizeof(Dau),0);
For i:=1 To length(S) Do
if S[i] in ['A'..'Z'] then S[i]:=chr(ord(S[i])+32);
For i:=1 To Length(S) Do inc(Dau[s[i]]);
n:=length(S);
For Ch:='a' To 'z' Do if dau[ch]<>0 then
begin
tl:=(dau[ch]/n)*100; Writeln(g,ch:3,':',tl:6:1,'%');
end;
close(f);close(g);
5
end.
2.2. Dạng bài tập mã hóa, giải mã xâu
Ở dạng này kiến thức thường xoay quanh việc:
+ Mã hóa một xâu kí tự bằng cách thay mỗi chữ cái bằng chữ cái đứng sau K vị trí
vòng tròn theo bảng chữ cái. Các kí tự ngoài chữ cái thì giữ nguyên.
+ Giải mã một xâu kí tự dựa vào quy tắc mã hóa ở trên
Phương pháp chung:
- Xây dựng chương trình con mã hóa một kí tự từ đó thực hiện mã hóa cả xâu kí tự.
Function Mahoa(Ch:Char):Char;
Var vt:byte;
Begin
If upcase(ch) in ['A'..'Z'] then
Begin
Vt:=ord(upcase(ch))-65; Vt:=Vt+k;
Mahoa:=Char(vt mod 26 +65);
End
Else Mahoa:=ch;
End;
- Giải mã xâu đã được mã hóa theo quy tắc trên: Xây dựng chương trình con giải
mã một kí tự từ đó thực hiện giải mã cả xâu kí tự. (Áp dụng trong bảng chữ cái)
Function Giaima(Ch:Char):Char;
Var vt:byte;
Begin
If upcase(ch) in ['A'..'Z'] then
Begin
Vt:=ord(upcase(ch))-65;Vt:=vt-k+26;
Giaima:=Char(vt mod 26 +65);
End
Else Giaima:=ch;
Bài tập vận dụng:
Trong lúc ngồi học lập trình Pascal Bờm nghĩ ra một việc muốn viết nhận kí
cho bản thân nhưng lại không muốn cho bất kì ai đọc được nhật kí mà mình viết.
Bờm nghĩ mình phải mã hóa các thông tin trước khi muốn lưu trữ lại nội dung nhật
kí. Bờm đưa ra cách mã hóa như sau: thay mỗi chữ cái bằng chữ cái đứng sau K vị
trí trong bảng chữ cái khi viết. Nếu bảng chữ cái có N chữ, thì sau chữ cái thức N-1
là chữ cái thứ N, sau chữ cái thứ N là chữ thứ nhất, ….Cách mã hóa như vậy được
gọi là nhật kí mã hóa. Các kí tự ngoài bảng chữ cái vẫn được giữ nguyên.
Cho tệp văn bản MAHOA.INP có cấu trúc như sau:
- Dòng 1: Ghi số nguyên K (157 Then
Begin Kt:=False; Break; end;
If KT=true Then Val(Xaucon,N);
If Nto(N) and (N>max)then Max:=N;
End;
Write(g,Max);close(f); close(g);
end.
Bài 2. Mật khẩu (Đề thi HSG tỉnh Thanh Hóa năm 2015 – 2016) [3]
Một xâu ký tự được gọi là mật khẩu "an toàn" nếu thỏa mãn các điều kiện:
Độ dài của xâu đó ≥ 6, chứa ít nhất một chữ cái in ('A'..'Z'), chứa ít nhất một chữ
cái thường ('a'..'z') và chứa ít nhất một chữ số ('0'..'9').
Ví dụ: 'a1B2C3', 'tinHoc6' là hai mật khẩu "an toàn", còn 'a1B2C', 'a1b2c3',
'A1B2C3' và 'tinhoc' đều không phải là mật khẩu "an toàn".
Cho xâu S mà mỗi ký tự trong S thuộc một trong ba loại ký tự sau: Chữ cái
in ('A'..'Z'), chữ cái thường ('a'..'z'), chữ số ('0'..'9'). Tìm xem có bao nhiêu cặp chỉ
số (i,j) thỏa mãn điều kiện: 1≤i=6) and (ANTOAN(Xaucon)=true) then
inc(dem);
End;
Write(g,dem);close(f); close(g);
End.
Bài 3. Xâu con (Đề thi HSGThanh Hóa năm 2016 -2017) [3]
Một xâu kí tự gọi là xâu nhị phân nếu nó chỉ chứa hai kí tự ‘0’ hoặc ‘1’.
Xâu v gọi là xâu con của xâu S nếu xâu v khác rỗng và được tạo bởi các kí tự liên
tiếp trong xâu S (thứ tự giữ nguyên). Hai xâu con u và v của xâu S là khác nhau
nếu nó có độ dài khác nhau hoặc được tạo từ các kí tự ở vị trí khác nhau trong xâu
S. Ví dụ: xâu “010” có các xâu con là “0”, “1”, “0”, “01”, “10”, “010”.
Yêu cầu: Cho trước một xâu nhị phân S và số nguyên dương k, hãy đếm xem có
bao nhiêu xâu con của xâu S chứa đúng k kí tự ‘1’.
Dữ liệu vào: Vào từ file văn bản XAUCON_NP.INP gồm:
- Dòng 1 chứa một số nguyên k (0 ≤ k ≤ 106).
- Dòng 2 chứa xâu nhị phân S có độ dài không quá 106.
Dữ liệu ra: Ghi ra file văn bản XAUCON_NP.OUT một số nguyên duy nhất là kết
quả tìm được.
Ví dụ:
XAUCON_NP.INP
XAUCON_NP.OUT
2
4
01010
* Code tham khảo
Var S,Xaucon:AnsiString;
i,j,k,sl,dem,m:Word;f,g:text;
Begin
Assign(f,'xaucon_NP.INP'); reset(f);
Assign(g, 'Xaucon_NP.OUT'); ReWrite(g);
Readln(f,k);readln(f,S);sl:=0;
For i:=1 To Length(S) Do
For J:=1 To Length(S)-i+1 Do
Begin
Xaucon:=copy(S,j,i); dem:=0;
For m:=1 to length(Xaucon) Do
if Xaucon[m]='1' then inc(dem);
if dem=k then Inc(Sl);
end;
10
Write(g,sl);close(f); close(g);
end.
2.4. Dạng bài tập xâu đối xứng
Xâu đối xứng còn hay gọi là xâu Palindrome, có nghĩa một xâu khi đọc các
ký tự trong xâu từ trái sang phải cũng giống từ phải sang trái thì xâu đó được gọi là
xâu đối xứng (xâu Palindorm).
Phương pháp chung:
Dạng 1: Với những bài tập kiểm tra xâu đối xứng hay tìm kiếm xâu có tính
chất đối xứng thì trước hết nên xây dựng hàm kiểm tra tính chất đối xứng của một
xâu, trên cơ sở đó chúng ta đi giải quyết những bài tập khó hơn. Để kiểm tra xâu
đối xứng có 2 cách sau đây:
- Cách 1: Một xâu s có tính chất đối xứng khi s[i] = s[n-i+1] với i chạy từ 1 đến
length(s) div 2. Dựa trên cơ sở đó ta xây dựng hàm kiểm tra.
- Cách 2: Ta tạo xâu S2 là xâu đảo ngược của xâu S1 đã cho. Sau đó kiểm tra nếu
S1=S2 thì S1 là xâu đối xứng ngược lại S1 không phải là xâu đối xứng
Dạng 2: Bài tập tìm xâu con đối xứng dài nhất. Sử dụng phương pháp quy
hoạch động bằng cách sử dụng mảng 2 chiều F và giá trị F[i, j] = true/false nếu
đoạn gồm các kí tự từ i đến j của S có/không là đối xứng
Ta có công thức là:
- F[i,i] = True
- F[i,j] = F[i+1,j-1]; (nếu s[i]=s[j])
- F[i,j] = False; (nếu s[i]<>s[j])
Dạng 3: Tìm số kí tự ít nhất cần thêm vào để có xâu đối xứng. Để giải các
bài tập dạng này ta làm như sau: Gọi S2 là xâu đảo của xâu S1 ban đầu, T là xâu
con chung dài nhất của S1 và S2. Khi đó các kí tự của S1 không thuộc T chính là
các kí tự cần chèn vào S1 để S1 trở thành xâu đối xứng.
Bài toán trở thành tìm dãy con chung dài nhất của hai dãy tương ứng là 2 xâu
S1 và S2 bằng phương pháp quy hoạch động. Sử dụng mảng L[0..max,0..max] để
lưu độ dài dãy con chun dài nhất với L[i,j] là độ dài của dãy con chung dài nhất của
hai xâu S1, S2
Khi đó:
L[0,j] = 0 với (N = length(s1))
L[i,0] = 0 với (M = length(s2))
Với:
Nếu s1[i]=s2[j] thì L[i,j]:= L[i-1,j-1]+1
Ngược lại L[i,j]=max{L[i-1,j],L[i,j-1]}
Bài tập xâu đối xứng dạng 1: (Đề thi HSG tỉnh Hải Dương 2015 -2016) [3]
Tí năm nay học lớp 11, hôm nay Bác Bill sang nhà Tí chơi, Tí có hỏi bác về
xâu kí tự đối xứng thì được bác trả lời rằng: "Mô ̣t xâu kí tự được gọi là đối xứng
nếu nó có không ít hơn 1 ký tự và ta đọc từ trái sang phải hoă ̣c từ phải sang trái đều
giống nhau, không phân biê ̣t hoa thường". Tí thắc mắc với Bác Bill vậy nếu ta
muốn đếm số lượng các xâu con đối xứng trong 1 xâu thì có được không và ta phải
11
đếm thế nào? Là người giỏi lập trình, bạn hãy giúp Bác Bill và Tí giải quyết vấn đề
này nhé? Cho một xâu kí tự bất kỳ có độ dài không quá 105 ký tự.
Yêu cầu: Hãy đếm có bao nhiêu xâu con là đối xứng.
Dữ liêụ vào: Từ tê ̣p XAUCON_DX.INP là mô ̣t xâu kí tự in hoa.
Dữ liệu ra: Ghi vào tê ̣p XAUCON_DX.OUT số lượng xâu con đối xứng.
Ví du:
XAUCON_DX.INP XAUCON_DX.OUT
ABANHOONA
11
* Code tham khảo
Var s,xaucon:ansistring;
i,j,dem:word;f,g:text;
function Doixung(s:Ansistring):boolean;
var i,n:integer;
begin
n:=length(s);
for i:=1 to (n div 2) do
if s[i] <> s[n+1-i] then
begin Doixung:=false; exit; end;
Doixung:=true;
end;
begin
Assign(f,'xaucon_DX.inp'); Reset(f);
Assign(g,'Xaucon_DX.OUT'); Rewrite(g);
Read(f,S);
For i:=1 to Length(S) Do
For j:=1 to length(s)-i+1 Do
begin
Xaucon:=copy(S,j,i);
If Doixung(Xaucon)=true then inc(Dem);
end;
Write(g,dem);Close(f); Close(g);
end.
Bài tập xâu đối xứng dạng 2:
Cho một xâu S có độ dài không vượt quá 1000 kí tự; tìm xâu đối xứng dài nhất là
xâu con của S.
* Code tham khảo
var s:ansistring; n,i,j,d,max,k,csd,csc:longint;
F:array[0..1001,0..1001] of boolean;
begin
write('nhap s:'); readln(s);
FillChar(F,sizeof(F),false);
12
n:=length(s); max:=1;
for i:= 1 to n do F[i,i]:= True;
for k:= 1 to (n-1) do
for i:= 1 to (n-k) do
begin
j:=i + k;
F[i,j]:= (F[i+1,j-1]) and (s[i]=s[j]);
end;
for i:=1 to n do
for j:=1 to n do
begin
d:=j-i+1;
if (f[i,j]=true) and (d>max) then
begin max:=d; csd:=i; csc:=j; end;
end;
for i:=csd to csc do write(s[i]); readln;
end.
Bài tập xâu đối xứng dạng 3:
Một xâu gọi là xâu đối xứng nếu xâu đó đọc từ trái sang phải cũng giống đọc
từ phải sang trái. Cho một xâu S hãy tìm số kí tự ít nhất cần thêm vào xâu S để S
trở thành xâu đối xứng.
Dữ liệu vào: XAU_DX.INP gồm: Một dòng là xâu S
Dữ liệu ra: Ghi vào tệp XAU_DX.OUT
- Dòng 1: Đưa ra kí tự ít nhất cần chèn vào
- Dòng 2: Các kí tự cần chèn
Ví dụ:
XAU_DX.INP
XAU_DX.OUT
Edbabcd
2
Ec
* Code tham khảo
var L:array[0..100,0..100] of byte;
kq:array[1..100] of boolean;
i,j,m:integer; s1,s2:string; f,g:text;
function max(x,y:integer):integer;
begin
if x>y then max:=x else max:=y;
end;
begin
assign(f,'XAU_DX.inp'); reset(f);
Assign(g,'XAU_DX.Out'); Rewrite(g);
readln(f,s1); s2:=''; m:=length(s1);
for i:=m downto 1 do s2:=s2+s1[i];
13
fillchar(L,sizeof(L),0);
for i:=1 to m do
for j:=1 to m do
if (s1[i]=s2[j]) then L[i,j]:=L[i-1,j-1]+1
else L[i,j]:= max(L[i-1,j], L[i,j-1]);
writeln(g,m-L[m,m]);
fillchar(kq,sizeof(kq),false);
i:=m; j:=m;
while (i>0) and (j>0) do
if s1[i]=s2[j] then
begin
kq[i]:=true;
dec(i); dec(j);
end
else
if L[i,j]=L[i,j-1] then dec(j) else dec(i);
For i:=1 to m do
if kq[i] = false then write(g,s1[i],' ');
close(f);close(g);
end.
2.5. Dạng bài tập xử lí số nguyên kiểu dữ liệu lớn [2]
Phương pháp chung: Để thực hiện các phép tính hoặc xử lý với số nguyên ngoài
phạm vi biểu diễn được cung cấp, cách đơn giản nhất là sử dụng xâu kí tự để biểu
diễn với mỗi ký tự của xâu tương ứng với một chữ số của số nguyên lớn tính từ trái
qua phải. Dưới đâytôi xin đưa ra một số chương trình con thể hiện phép toán trong
xử lý số lớn. Và sử dụng các chương trình con để vận dụng vào từng bài toán thực tế.
PHÉP CỘNG HAI SỐ LỚN
Function Cong(S1,S2:AnsiString): Ansistring;
Var Nho, tong, So1,so2,t,i:byte;S,Xau:AnsiString;
Begin
While length(S1)0 then S:= ‘1’+S;
Cong:=S;
End;
PHÉP TRỪ GIỮA HAI SỐ LỚN (VỚI SỐ TRỪ NHỎ HƠN SỐ BỊ TRỪ)
14
Function Hieu(S1,S2:AnsiString):AnsiString;
Var Nho, hieu, so1,so2, t:byte;S,xau:Ansistring;
Begin
While length(S1)1) and S[1]= ‘0’ Do Delete(S,1,1);
Hieu:=S;
End;
PHÉP NHÂN MỘT SỐ LỚN VỚI MỘT SỐ NHỎ
Function Nhannho(A:AnsiString; b:longint):AnsiString;
Var I,Nho,tong:longint;S,xau:String;
Begin
S:=’’; nho:=0;
For i:=length(a) Downto 1 Do
Begin
Val(a[i],so);Tong:=so*b+Nho;Nho:=Tong div 10;
T:= tong mod 10; Str(t,xau);S:=Xau+S;
End;
If nho>0 Then Str(nho,xau) else xau:=’’;
Nhannho:=Xau+S;
End;
PHÉP NHÂN MỘT SỐ NGUYÊN LỚN VỚI MỘT SỐ NGUYÊN LỚN
Function NhanLon(a,b:AnsiString):AnsiString;
Var Tong,xau:String;M,i,j,so:integer;
Begin
M:=-1;Tong:=’’;
For i:=length(a) Downto 1 Do
Begin
M:=m+1;Val(a[i],So);Xau:=nhannho(b,so);
For j:=1 To M Do Xau:=Xau+’0’;
Tong:=cong(xau,tong);
End;
Nhanlon:=Tong;
15
End;
PHÉP CHIA LẤY THƯƠNG NGUYÊN (DIV) SỐ LỚN VỚI 1 SỐ BÉ
Function ThuongDIV(A:ansiString;b:Longint):String;
Var so,I,thuong,du:longint;
Xau,S:ansistring;
Begin
Du:=0; thuong:=0; S:=’’;
For i:=1 to length(a) Do
Begin
Val(a[i],so);Du:=du*10+So;
Thuong:=du div b;Du:=du mod b;
Str(thuong,xau);S:=S+xau;
End;
While (length(S)<>0) and (S[1]=’0’) Do Delete(S,1,1);
Thuongnguyen:=S;
End;
PHÉP CHIA LẤY DƯ (MOD) SỐ LỚN VỚI SỐ NHỎ
Function Chiamod(a:AnsiString;b:longint):longint;
Var i,du,so:longint;
Begin
Du:=0;
For i:=1 To length(a) Do
Begin Val(A[i],so);Du:=(So+du*10)mod b End;
Chiamod:=Du;
End;
Bài tập vận dụng:
Bài 1. Chữ số cuối cùng khác 0 (Đề thi HSG tỉnh Ninh Bình 2015 -2016)[3]
Viết chương trình tìm chữ số cuối cùng khác 0 của N!
Ví dụ: Với n=10, ta có 10!=3628800, kết quả = 8
Với n=14, ta có 14!=87178291200, kết quả = 2
Dữ liệu vào: cho trong file GT_SCC.INP Chỉ gồm một dòng là một số n
(10<=n<=105)
Dữ liệu ra: Ghi ra file GT_SCC.OUT là chữ số cuối cùng khác 0 của n!
Ví dụ:
GT_SCC.INP
10
14
GT_SCC.OUT
8
2
* Code tham khảo
Var N,i,so,t,b:longint;
Tich,S,xau:ansiString;f,g:text;
Function nhannho(A:ansistring;b:longint):ansiString;
var i,nho,tong:longint;S,xau:String;
Begin
16
S:='';nho:=0;
For i:=length(a) Downto 1 Do
begin
Val(a[i],so);Tong:=so*b+ Nho;
nho:=Tong div 10;t:=Tong mod 10;
str(t,xau);S:=xau+S;
End;
If nho>0 Then Str(nho,Xau) else Xau:='';
Nhannho:=Xau+S;
End;
Begin
Assign(f,'GT_Scc.inp'); Reset(F);
Assign(g,'GT_Scc.out'); ReWrite(g);
readln(f,n); tich:='1';
For i:=1 To n Do tich:=nhannho(tich,i);
While (length(tich)>0) and (tich[length(tich)]='0') Do
Delete(tich,length(tich),1);
Writeln(g,tich[length(tich)]);Close(f);Close(g);
End.
Bài 2. Biểu thức (Đề thi HSG tỉnh Quảng Bình 2015 -2016) [3]
Cho biểu thức y=x2 + 2 (x nguyên dương). Với giá trị x nhỏ, các bạn học sinh
dễ dàng tính được y. Tuy nhiên, khi giá trị x khá lớn việc tính toán gặp nhiều khó
khăn. Hãy lập trình giúp các bạn ấy tìm giá trị biểu thức y, biết số lượng chữ số của
x từ 50 đến 100.
Dữ liệu vào: Đọc từ file ‘BIEUTHUC.INP’ chỉ một dòng chứa giá trị x (số lượng
số chữ số của x từ 50 đến 100);
Kết quả ra: ghi vào file ‘BIEUTHUC.OUT’là số dư của phép (y mod 2020) tìm được
Ví dụ:
BIEUTHUC.INP
BIEUTHUC.OUT
12345678901234567890123456789012345678901234567890 502
*code tham khảo
Var X,y: AnsiString;f,g:text;
Function Cong(S1,S2:AnsiString): Ansistring;
Var Nho, tong, So1,so2,t,i:byte;S,Xau:AnsiString;
Begin
While length(S1)0 then S:= '1'+S; Cong:=S;
End;
Function Nhannho(A:AnsiString; b:longint):AnsiString;
Var I,Nho,tong,so,T:longint;S,xau:String;
Begin
S:=''; nho:=0;
For i:=length(a) Downto 1 Do
Begin
Val(a[i],so);Tong:=so*b+Nho;Nho:=Tong div 10;
T:= tong mod 10; Str(t,xau);S:=Xau+S;
End;
If nho>0 Then Str(nho,xau) else xau:='';Nhannho:=Xau+S;
End;
Function NhanLon(a,b:AnsiString):AnsiString;
Var Tong,xau:String;M,i,j,so:integer;
Begin
M:=-1;Tong:='';
For i:=length(a) Downto 1 Do
Begin
M:=m+1;Val(a[i],So);Xau:=nhannho(b,so);
For j:=1 To M Do Xau:=Xau+'0';
Tong:=cong(xau,tong);
End;
Nhanlon:=Tong;
End;
Function Chiamod(a:AnsiString;b:word):longint;
Var i,du,so:longint;
Begin Du:=0;
For i:=1 To length(a) Do
Begin Val(A[i],so);Du:=(So+du*10)mod b End;
Chiamod:=Du;
End;
Begin
Assign(f,'Bieuthuc.inp'); Reset(f);
Assign(g,'bieuthuc.out'); Rewrite(g);
Read(f,X);Y:=Cong(nhanlon(X,X),'2');
Write(g,chiamod(y,2020));close(f); close(g);
End.
2.4. Hiệu quả của sáng kiến kinh nghiệm đối với hoạt động giáo dục, với bản
thân, đồng nghiệp và nhà trường
- Với hoạt động giáo dục
18
- Xem thêm -