SỞ GIÁO DỤC VÀ ĐÀO TẠO THANH HOÁ TRƯỜNG THPT THƯỜNG XUÂN SÁNG KIẾN KINH NGHIỆM XÂY DỰNG CÁC DẠNG BÀI TẬP KIỂU DỮ LIỆ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 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 2021 MỤC LỤC Mở đầu 1.1 Lí chọn đề tài .1 1.2 Mục đích nghiên cứu 1.3 Đối tượng nghiên cứu 1.4 Phương pháp nghiên cứu 1.5 Những điểm sáng kiến kinh nghiệm 2 Nội dung sáng kiến kinh nghiệm .2 2.1 Cơ sở lí luận sáng kiến kinh nghiệm 2.2 Thực trạng vấn đề trước áp dụng sáng kiến kinh nghiệm 2.3 Các giải pháp sử dụng để giải vấn đề 2.4 Hiệu sáng kiến 18 Kết luận, kiến nghị 18 Mở đầu 1.1 Lí chọn đề tài Người xưa nói: “Hiền tài nguyên khí quốc gia, ngun khí thịnh nước mạnh mà hưng thịnh, ngun khí suy nước yếu mà thấp hèn” [5] Vì Vậy bồi dưỡng học sinh giỏi nhiệm vụ quan trọng 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à nhiệm vụ chuyên môn quan trọng nhà trường Bồi dưỡng học sinh giỏi cơng việc khó khăn lâu dài, địi hỏi nhiều cơng sức thầy trò Trong thực tế 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 đề thi học sinh giỏi cấp tỉnh, cấp quốc gia kiểu liệu sử dụng nhiều đề thi học sinh giỏi kiểu liệu xâu Sau thời gian phân công bồi dưỡng học sinh giỏi trường THPT Thường Xuân 2, thân nhận thấy kiểu liệu xâu hay chuyển đổi số dạng toán kiểu liệu khác kiểu liệu để giải quyết, đặc biệt với dạng tốn có kiểu liệu số lớn phạm vi lưu trữ kiểu liệu số khơng chuyển kiểu xâu thuật tốn khó phức tạp, học sinh khó hiểu khơng nắm bắt được, xử lí kiểu xâu lại làm cho thuật toán đơn giản nhiều, học sinh dễ dàng vận dụng giải toán cách triệt để, để biết cách vận dụng linh hoạt thao tác xử lý kiểu liệu vào tốn cụ thể khơng phải dễ chưa có tài liệu hướng dẫn Với mong muốn phần giúp học sinh dễ dàng nhận diện dạng tập biết cách vận dụng kiến thức kiểu xâu để giải dạng tập cách dễ dàng hiệu quả, tơi tham khảo nhiều tài liệu từ nhiều nguồn khác như: qua sách, tài liệu ôn thi học sinh giỏi, đề học sinh giỏi năm gần tỉnh Thanh Hóa nói riêng nhiều tỉnh khác nước nói chung, nguồn tài liệu Internet, vốn kiến thức kinh nghiệm dạy học thân để viết tài liệu bồi dưỡng cho học sinh đội tuyển học sinh giỏi thấy có hiệu Với lí tơi chọn đề tài: “Xây dựng dạng tập kiểu liệ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 em học sinh có nguồn tài liệu tham khảo giáo viên bồi dưỡng học sinh giỏi trường THPT Thường xuân 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 dạy học Tin học 11 Trường THPT Thường Xuân nói riêng mơn tin học nói chung 1.3 Đối tượng nghiên - Kiểu liệu xâu dạng tập xử lý xâu - Học sinh đội tuyển học sinh giỏi tin học trường THPT Thường Xuân hai năm học 2019-2020 năm học 2020 – 2021 1.4 Phương pháp nghiên cứu - Xây dựng sở lý thuyết - Thu thập thông tin sách, báo, tài liệu ôn thi học sinh giỏi Internet, đề thi học sinh giỏi cấp tỉnh, kinh nghiệm q trình ơn thi học sinh giỏi - Sử dụng phần mềm FreePascal để viết chương trình 1.5 Những điểm sáng kiến kinh nghiệm - Bổ sung dạng tập thường gặp với kiểu liệu xâu chưa trình bày SKKN đánh giá năm 2019-2020 - Bổ sung 20 tập vận dụng cho dạng chuyên đề (SKKN năm 2019-2020 chưa xây dựng) - Bổ sung 10 tập ôn tập cho dạng chuyên đề (SKKN năm 20192020 chưa xây dựng) - Phần giải pháp thực xếp logic theo trình tự: Dạng tập, phương pháp giải chung, ví dụ áp dụng cuối tập vận dụng Nội dung sáng kiến kinh nghiệm 2.1 Cơ sở lí luận sáng kiến Kiểu xâu kiểu liệu có cấu trúc giới thiệu chương trình sách giáo khoa tin học 11_ “ 12 _Kiểu xâu” Sau học lý thuyết kiểu xâu đa số học sinh nắm bắt xâu gì? Độ dài xâu? Biết khai báo biến xâu Nhưng làm việc với xâu em cịn lúng túng với việc áp dụng hàm, thủ tục thao tác xử lý xâu để giải tốn thực tế, câu hỏi ‘23’+‘9’ = ‘239’, muốn thực phép tính ‘23’+ ‘9’ = 32 liệu có thực khơng? Muốn thực phải làm cách nào? Và nhiều câu hỏi tương tự khác Vậy làm để học sinh giải triệt để tốn liên quan đến kiểu liệu xâu chuyển kiểu liệu khác kiểu xâu để vận dụng xử lý tốn mang tính thực tế có đề thi học sinh giỏi Bản thân tơi tín nhiệm, tin tưởng nhà trường phân công bồi dưỡng học sinh giỏi, nên 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 tốt 2.2 Thực trạng vấn đề Trong đề thi học sinh giỏi cấp tỉnh, cấp quốc gia kiểu liệu xâu kiểu liệu có cấu trúc thường sử dụng 50 - 60% đề thi Tuy nhiên phần kiểu xâu được phân phối tiết chương trình sách giáo khoa Tin học 11 với vẻn vẹn tiết lý thuyết tiết thực hành Với lượng kiến thức cung cấp sách giáo khoa tin học 11 học sinh giải tập dạng xâu đơn giản Thế tập kiểu liệu xâu có đề thi lại khó đa dạng, với lượng kiến thức nhỏ cung cấp sách giáo khoa chưa đủ để giải tốn có đề thi Học sinh trường THPT Thường Xuân chiếm gần 80% 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ả tư chưa cao, em học máy móc, học vẹt nên việc tự lập trình giải tốn học sinh khó, lại khó khăn nhiều học sinh bắt buộc phải lập trình giải tốn u cầu mức độ tư cao đề học sinh giỏi Mặt khác kiến thức lập trình 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ư tốn học tốt, hiểu rõ chất ngơn ngữ lập trình viết chương trình hồn chỉnh, bên cạch mơn tin học khơng có chương trình thi THPT quốc gia nên học sinh phụ huynh xem tin học 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 mơn 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 việc khó bồi dưỡng học sinh giỏi tin học để có thành tích lại khó khăn Đặc biệt giảng dạy cho học sinh nội dung kiểu liệu xâu học sinh lúng túng, dẫn đến viết chương trình cho tốn cụ thể cịn chưa Tài liệu kiểu liệu xâu Internet chủ yếu kiến thức xử lí xâu dạng đơn giản, tập kiểu xâu chưa phân loại thành dạng kiến thức thường gặp kiểu liệu xâu đưa phương pháp giải chung cho dạng tập đó, đề thi học sinh giỏi cấp tỉnh Internet 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 học sinh đội tuyển nghiên cứu hạn chế 2.3 Các giải pháp sử dụng để giải vấn đề Với lí nên để giải vấn đề đặt ra, thực giải pháp sau: - Tìm hiểu kiến thức kiểu liệu xâu: Khái niệm xâu, cách khai báo, cách nhập xuất kiểu liệu xâu thao tác phép toán xử lý xâu - Xây dựng dạng thường gặp với kiểu xâu, đưa phương pháp chung để giải dạng tập sử dụng phần mềm FreePascal để viết code tham khảo cho ví dụ áp dụng đưa tập vận dụng, tập học sinh tự giải cho dạng Từ giúp học sinh biết vận dụng tự phân tích, định dạng tập, tự tìm lời giải thích hợp cho tốn cụ thể, kích thích tư phân tích, tổng hợp tư linh hoạt, sáng tạo học sinh lập trình Kiến thức kiểu liệu xâu thường quy dạng tập sau: • Dạng tập kiểu xâu đơn giản • Dạng tập mã hóa giải mã xâu • Dạng tập xử lý xâu • Dạng tập xâu đối xứng • Dạng tập xử lí số ngun kiểu liệu lớn phạm vi lưu trữ kiểu liêu số • Dạng tập tính tần số xuất kí tự ‘0’ ‘9’ ‘a’ ‘z ‘A’ ‘Z’ có xâu • Dạng tập ghép thành số lớn số nhỏ với phần tử mảng xâu kí tự • Dạng tập tìm cách xóa xâu S K kí tự để xâu cịn lại xâu có giá trị lớn xâu có giá trị nhỏ • Dạng tập tìm cách xóa xâu S số kí tự để xâu cịn lại xâu có K kí tự có giá trị lớn có giá trị nhỏ • Dạng tập tìm xâu chung dài tìm phần tử chung dài hai xâu S1 S2 NỘI DUNG CỤ THỂ: 2.3.1 Các kiến thức kiểu xâu [1] 2.3.1.1 Khái niệm Xâu dãy kí tự nằm mã ASCII Mỗi kí tự phần tử xâu Ví dụ: S= ‘Tin Hoc’ + Tên Xâu: S + Số phần tử xâu: 7= Độ dài xâu 2.3.1.2 Khai báo Var : String[độ dài lớn xâu]; + Tên biến xâu gồm nhiều biến xâu, nhiều biến xâu biến cách dấu phẩy + Độ dài lớn xâu 255 Trong trường hợp bỏ qua khai báo độ dài lớn xâu, độ dài lớn mặc định 255 Chú ý: Trong Free Pascal sử dụng kiểu liệu ansiString có kích thước gần 2GB=230B nên thường xem độ dài xâu không giới hạn 2.3.1.3 Nhập, xuất liệu kiểu xâu - Cách nhập hay xuất kiểu liệu xâu tương tự kiểu liệu khác thủ tục Read, Readln, Write, Writeln 2.3.1.4 Các thao tác xử lí xâu a Phép ghép xâu: Ví dụ: ‘HA’+ ‘NOI’= ‘HANOI’ b Phép so sánh xâu - Các phép so sánh: >, =, max then max:=Dau[ch]; writeln(g,BCNN(max,100000)); close(f); close(g); end Bài Kí tự khác (Đề HSG tỉnh Thanh Hóa năm 2016 -2017)[3] Cho xâu S gồm kí tự chữ tiếng anh chữ số (có phân biệt chữ in hoa, in thường) Yêu cầu: Hãy xác định số kí tự khác xâu S kí tự xuất lần Dữ liệu vào: Vào từ file văn KTKN.INP gồm dịng xâu kí tự S (có độ dài khơng q 255) Kết quả: Kết ghi file văn KTKN.OUT gồm: + Dòng đầu ghi số kí tự khác + Các dịng tiếp theo, dịng ghi kí tự xuất xâu S số lần xuất Các kí tự đưa theo thứ tự chữ in hoa, in thường, chữ số Các chữ cái, chữ số đưa theo thứ tự từ điển Ví dụ: KTKN.INP KTKN.OUT AzB1C9A1BC A2 B2 C2 z1 12 91 * Code tham khảo: Var s:ansistring; Dau1:array['a' 'z'] of longint; Dau2:array['A' 'Z'] of longint; Dau3:array['0' '9'] of longint; f,g:text; k,ch:char; i,max,dem,d1,d2,d3:longint; begin assign(f,'KTKN.INP'); reset(f); readln(f,s); assign(g,'KTKN.OUT'); rewrite(g); for ch:='a' to 'z' Dau1[ch]:=0; for ch:='A' to 'Z' Dau2[ch]:=0; for ch:='0' to '9' Dau3[ch]:=0; for i:=1 to length(s) if S[i] in ['a' 'z'] then inc(Dau1[S[i]]) else If S[i] in ['A' 'Z'] then inc(Dau2[S[i]]) else if S[i] in ['0' '9'] then inc(Dau3[S[i]]); d1:=0; d2:=0; d3:=0; for ch:='a' to 'z' Do if Dau1[ch]0 then inc(d1); for ch:='A' to 'Z' Do if Dau2[ch]0 then inc(d2); for ch:='0' to '9' Do if Dau3[ch]0 then inc(d3); Writeln(g,d1+d2+d3); for ch:='A' to 'Z' Do if Dau2[ch]0 then writeln(g,ch, ' ' ,Dau2[ch]); for ch:='a' to 'z' Do if Dau1[ch]0 then writeln(g,ch, ' ', Dau1[ch]); for ch:='0' to '9' Do if Dau3[ch]0 then writeln(g,ch, ' ', Dau3[ch]); close(f); close(g); end Bài Số thống kê [5] Cho số nguyên dương N hệ thập phân dạng xâu khơng q 500 chữ số khơng có số khơng có nghĩa đầu Số thống kê N xây dựng sau: - Tính tần số xuất chữ số N; - Viết liên tiếp tần số chữ số theo thứ tự tăng dần chữ số khác N Ví dụ: N=353, tần số xuất 2, tần số xuất Như số thống kê 2315 Dữ liệu vào: Từ tệp văn SOTK.INP gồm số nguyên dương N (không 500 chữ số) Kết quả: Ghi vào tệp văn SOTK.OUT số thống kê tìm Ví dụ: SOTK.INP 353 STK.OUT 2315 * Code tham khảo Var s:ansistring; Dau:array['0' '9'] of word; f,g:text; ch:char; i: Word; begin assign(f,'SOTK.INP'); reset(f); readln(f,s); assign(g,'SOTK.OUT'); rewrite(g); for ch:='0' to '9' Dau[ch]:=0; for i:=1 to length(s) Do inc(Dau[S[i]]); for ch:='0' to '9' if Dau[ch]>0 then write(g,dau[ch], ch); close(f); close(g); end 2.3.2.7 Dạng tập ghép thành số có giá trị lớn số nhỏ với phần tử mảng xâu kí tự - Phương pháp chung: Lưu số dạng mảng với phần tử kiểu xâu thực hiện: + Ghép số có giá trị lớn nhất: Sắp xếp mảng theo thứ tự tăng dần theo tiêu chí xếp phần tử a[i] đứng trước phần từ a[j] (a[i] + a[j]) > (a[j] +a[i]) For i:=1 To N-1 Do For j:=i+1 To N If a[i]+a[j]>a[j]+a[i] Then Xaucon:=copy(S,j,i); if KT(xaucon) then inc(dem); end; Write(g,dem);close(f); close(g); end Bài Xâu [5] Cho sâu s (độ dài không vượt 106) gồm kí tự ‘A’ ‘B’ Đếm số cách chọn cặp số(i,j) mà xâu liên tiếp từ kí tự thứ i đến kí tự thứ j (1≤i