SKKN Phương pháp giải một số dạng bài tập về kiểu dữ liệu xâu trong đề thi học sinh giỏi môn Tin học

 Phương pháp giải một số dạng bài tập về kiểu dữ liệu xâu trong đề thi HSG môn tin học
 MỤC LỤC
TÀI LIỆU THAM KHẢO......................................................................................................2
BÁO CÁO KẾT QUẢ NGHIÊN CỨU, ỨNG DỤNG SÁNG KIẾN ..................................3
 1. LỜI GIỚI THIỆU ..........................................................................................................3
 1.1. Lí do chọn đề tài........................................................................................................3
 1.2. Mục tiêu nghiên cứu..................................................................................................3
 1.3. Đối tượng nghiên cứu................................................................................................4
 1.4. Phương pháp thực hiện..............................................................................................4
 2. TÊN SÁNG KIẾN:.........................................................................................................4
 3. TÁC GIẢ SÁNG KIẾN:.................................................................................................4
 4. CHỦ ĐẦU TƯ TẠO RA SÁNG KIẾN .........................................................................5
 5. LĨNH VỰC ÁP DỤNG SÁNG KIẾN............................................................................5
 6. NGÀY SÁNG KIẾN ĐƯỢC ÁP DỤNG LẦN ĐẦU....................................................5
 7. MÔ TẢ BẢN CHẤT CỦA SÁNG KIẾN......................................................................5
 CHƯƠNG I: CƠ SỞ LÍ LUẬN CỦA ĐỀ TÀI.............................................................5
 CHƯƠNG II: THỰC TRẠNG CỦA VẤN ĐỀ NGHIÊN CỨU.................................6
 CHƯƠNG III: NỘI DUNG CỦA ĐỀ TÀI ...................................................................6
 1. Lý thuyết về kiểu xâu ..............................................................................................6
 1.1. Khái niệm..........................................................................................................6
 1.2. Khai báo............................................................................................................7
 1.3. Các thao tác xử lý xâu:......................................................................................7
 2. Các dạng bài tập kiểu xâu.....................................................................................10
 Dạng 1: Kiểm tra xâu thỏa mãn tính chất nào đó.......................................................10
 Dạng 2: Đếm số lần xuất hiện của các kí tự trong xâu ..............................................15
 Dạng 3: Mã hóa và giải mã ........................................................................................18
 Dạng 4: Xóa và thay thế.............................................................................................21
 Dạng 5: Chuyển số sang xâu và ngược lại.................................................................23
 8. NHỮNG THÔNG TIN CẦN ĐƯỢC BẢO MẬT (NẾU CÓ):..................................30
 9. CÁC ĐIỀU KIỆN CẦN THIẾT ĐỂ ÁP DỤNG SÁNG KIẾN:................................30
 10. ĐÁNH GIÁ LỢI ÍCH THU ĐƯỢC ..........................................................................30
KẾT LUẬN............................................................................................................................31
 11. DANH SÁCH NHỮNG TỔ CHỨC/CÁ NHÂN ĐÃ THAM GIA ÁP DỤNG THỬ 
 HOẶC ÁP DỤNG SÁNG KIẾN LẦN ĐẦU (NẾU CÓ): ..............................................31
 1 Phương pháp giải một số dạng bài tập về kiểu dữ liệu xâu trong đề thi HSG môn tin học
 BÁO CÁO KẾT QUẢ
 NGHIÊN CỨU, ỨNG DỤNG SÁNG KIẾN
1. LỜI GIỚI THIỆU
 1.1. Lí do chọn đề tài
 Môn tin học đặc biệt là nội dung tin học lập trình là một môn học khá là mới lạ 
 đối với học sinh phổ thông nên đa số các em rất bỡ ngỡ khi tiếp cận nội môn học này. 
 Trong thực tiễn dữ liệu vào của các bài toán đều liên quan đến các kiểu dữ liệu 
 khác nhau, để tiện cho việc lập trình và xử lý dữ liệu chúng ta thường đưa dữ liệu đó 
 về các dạng kiểu dữ liệu chuẩn hoặc kiểu dữ liệu có cấu trúc, một trong những kiểu dữ
liệu đó là kiểu xâu.
 Qua quá trình tham gia giảng dạy môn tin học tại trường THPT Đồng Đậu và bồi 
dưỡng học sinh giỏi tôi nhận thấy dữ liệu kiểu xâu gặp rất nhiều trong các bài toán 
nhưng để học sinh có thể 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 bài toán không phải là dễ.
 Với mong muốn hệ thống các bài toán dưới dạng một số dạng bài tập thường gặp 
giúp cho giáo viên và học sinh phần nào nhận dạng và giải một số bài tập liên quan tới 
kiểu dữ liệu xâu dễ dàng hơn, tôi xin đưa ra “PHƯƠNG PHÁP GIẢI MỘT SỐ DẠNG 
BÀI TẬP VỀ KIỂU DỮ LIỆU XÂU TRONG ĐỀ THI HỌC SINH GIỎI MÔN TIN 
HỌC”.
 1.2. Mục tiêu nghiên cứu
 o Đề tài thực hiện nhằm giúp cho giáo viên cũng như học sinh hệ thống lại các 
 kiến thức về các thao tác trên kiểu dữ liệu xâu từ đó áp dụng cho các bài toán 
 cụ thể.
 o Giới thiệu một số phép toán trên kiểu dữ liệu xâu, đặc biệt phần này có cung 
 cấp thêm một số hàm, thủ tục chưa được giới thiệu trong bài 12 sách giáo khoa
 3 Phương pháp giải một số dạng bài tập về kiểu dữ liệu xâu trong đề thi HSG môn tin học
4. CHỦ ĐẦU TƯ TẠO RA SÁNG KIẾN
5. LĨNH VỰC ÁP DỤNG SÁNG KIẾN
 Đề tài được sử dụng để vận dụng giải các bài toán về kiểu dữ liệu xâu trong sách 
bài tập tin học lớp 11 và trong các đề thi học sinh giỏi tỉnh môn tin học.
 Khi vận dụng đề tài để giải các bài toán về kiểu dữ liệu xâu giúp:
 o Học sinh sau khi được giới thiệu một cách hệ thống các dạng bài tập về xâu 
 và quy trình giải quyết từng dạng đã có thể nhận biết yêu cầu của bài toán và 
 cách thức giải quyết chúng một cách hiệu quả.
 o Hình thành ở HS kỹ năng phân tích, xử lý các vấn đề liên quan đến bài tập 
 kiểu xâu, sử dụng thành thạo vòng lặp biết trước, thủ tục chuẩn vào/ra đơn 
 giản, bước đầu làm quen với 1 số chương trình con dạng thủ tục tạo điều kiện 
 thuận lợi cho việc tiếp thu kiến thức về cách viết chương trình có cấu trúc.
 o Mở rộng một số bài tập kiểu xâu để học sinh thấy được ứng dụng quan trọng 
 của kiểu dữ liệu xâu trong lập trình.
6. NGÀY SÁNG KIẾN ĐƯỢC ÁP DỤNG LẦN ĐẦU HOẶC ÁP DỤNG THỬ
 Đề tài được áp dụng vào ngày 20 tháng 02 năm 2019
7. MÔ TẢ BẢN CHẤT CỦA SÁNG KIẾN:
 NỘI DUNG SÁNG KIẾN
 CHƯƠNG I: CƠ SỞ LÍ LUẬN CỦA ĐỀ TÀI
 Trong bối cảnh toàn ngành GD-ĐT đang nỗ lực đổi mới phương pháp dạy học theo 
hướng phát huy tính tích cực chủ động của học sinh trong hoạt động học tập. Điều 24.2 
của Luật giáo dục đã nêu rõ: “Phương pháp giáo dục phổ thông phải phát huy tính tích 
cực, tự giác, chủ động, sáng tạo của học sinh, phù hợp với đặc điểm của từng lớp học, 
môn học; bồi dưỡng phương pháp tự học, rèn luyện kỹ năng vận dụng kiến thức vào 
thực tiễn, tác động đến tình cảm, đem lại niềm vui, hứng thú học tập cho học sinh ”.
Như vậy, chúng ta có thể thấy định hướng đổi mới phương pháp dạy học đã được khẳng
 5 Phương pháp giải một số dạng bài tập về kiểu dữ liệu xâu trong đề thi HSG môn tin học
 đánh chỉ số bắt đầu từ 1. Do vậy, để tham chiếu đến phần tử của xâu ta viết
 [chỉ số của kí tự];
 Ví dụ: s = ‘Tin hoc’ Muốn truy cập đến kí tự ‘i’ thì viết s[2] = ‘i’;
 1.2. Khai báo
 Var : string [ độ dài lớn nhất của xâu ]; 
 Ví dụ: var hoten : string[30];
 Chú ý: Độ dài lớn nhất của xâu có thể bỏ qua. Khi đó độ dài lớn nhất của xâu 
 sẽ nhận giá trị ngầm định là 255. Ví dụ var s : string;
 1.3. Các thao tác xử lý xâu:
 1.3.1. Phép ghép xâu
 Kí hiệu là dấu (+), đượ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 và biến xâu.
 Ví dụ: ‘Tin’ + ‘ Hoc’ = ‘Tin Hoc’;
 ‘6’ + ‘7’ = ‘67’;
 1.3.2. Phép so sánh
 o Sử dụng phép so sánh = , , , = và có thứ tự ưu tiên thấp 
 hơn phép ghép xâu.
 o Quy tắc so sánh:
 ➢ Xâu A là 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.
 Ví dụ: ‘207’ > ‘2007’;
 7 Phương pháp giải một số dạng bài tập về kiểu dữ liệu xâu trong đề thi HSG môn tin học
 ❖ Hàm length(s) Cho giá trị là độ dài xâu s
 Giá trị s Thao tác Kết quả
 ‘Tin hoc’ Length(s); 7
 ‘500 ky tu’ Length(s); 9
 ❖ Hàm pos (s1, s2) Cho vị trí xuất hiện đầu tiên của xâu s1 trong xâu s2
 Giá trị s2 Thao tác Kết quả
 ‘Tin hoc’ Pos(‘oc’,s2); 6
 ‘abcdef’ Pos(‘k’,s2); 0
 ❖ Hàm upcase(ch) Cho chữ cái in hoa ứng với chữ cái trong ch
 Giá trị ch Thao tác Kết quả
 ‘a’ Upcase(ch); ‘A’
 ‘A’ Upcase(ch); ‘A’
 ❖ Thủ tục chuyển xâu sang số val (s, v, c) Chuyển xâu s thành giá trị số lưu vào 
 v, c là vị trí gây ra lỗi trong quá trình chuyển đổi, c = 0 thì chuyển đổi thành 
 công
 Giá trị s Thao tác Kết quả
 ‘1234’ Val(s,i,c); i = 1234; c=0
 ‘12c’ Val(s,i,c); Cho c=3 là vị trí 
 ký tự c không hợp 
 lệ
 9 Phương pháp giải một số dạng bài tập về kiểu dữ liệu xâu trong đề thi HSG môn tin học
*Ý tưởng: Muốn đưa xâu ra theo thứ tự ngược lại thì phải đi từ cuối xâu đến kí tự liền 
cuối... => duyệt bằng câu lệnh for...downto....do.....đưa ra từng kí tự của s
 For i:=length(s) downto 1 do write(s[i]);
Bài 4(sgk): Kiểm tra xem xâu có là xâu đối xứng không?
Xâu đối xứng là xâu mà đọc từ cuối xâu ngược lên cũng giống đọc từ đầu xâu đến cuối
* Cách 1: Tạo 1 xâu đảo ngược từ xâu ban đầu (Cách tạo giống Bài 3) => So sánh hai 
xâu, nếu bằng nhau thì đối xứng ngược lại thì không đối xứng
{ Tạo xâu b đảo ngược từ xâu a}
b:=’’;
for i:= length(a) downto 1 do b:=b+a[i];
if a = b then write(‘Xau doi xung’) else write(‘xau khong doi xung’);
* Cách 2: Nhận xét nếu xâu a đối xứng thì: 
a[1] = a[n] ( Gán n = length(a));
a[2] = a[n-1]
a[3] = a[n-2]
.... Tổng quát lên a[i] = a[n-i+1] với i chạy từ 1 đên n div 2 
Sử dụng biến KT để KT tính đối xứng của a
Đoạn chương trình thực hiện kiểm tra đối xứng:
KT:= true;
for i:= 1 to n div 2 do if a[i] a[n-i+1] then KT:= false;
if KT then write(‘Xau doi xung’) else (‘xau khong doi xung’);
 11