Tài liệu 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

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