(SKKN HAY NHẤT) 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

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 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 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 2021

LUAN VAN CHAT LUONG download : add [email protected]

MỤC LỤC

1. 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

1.5 Những điểm mới của sáng kiến kinh nghiệm........................................................................2

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.................................................................................................................18

3. Kết luận, kiến nghị............................................................................................................................18

2

LUAN VAN CHAT LUONG download : add [email protected]

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” [5] . 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 kiểu dữ liệ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, tài liệu ôn thi học sinh giỏi, 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 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 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 bài tập 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 trong hai năm học 2019-2020 và năm học 2020 – 2021.

1.4. Phương pháp nghiên cứu

1

LUAN VAN CHAT LUONG download : add [email protected]

- Xây dựng cơ sở lý thuyết.

- Thu thập thông tin trong sách, báo, các tài liệu ôn thi học sinh giỏi trên

Internet, các đề thi học sinh giỏi cấp tỉnh, kinh nghiệm trong quá 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 mới của sáng kiến kinh nghiệm

- Bổ sung 5 dạng bài tập thường gặp với kiểu dữ liệu xâu chưa được trình

bày trong SKKN đã được đánh giá năm 2019-2020.

- Bổ sung 20 bài tập vận dụng cho các dạng trong chuyên đề (SKKN năm

2019-2020 chưa xây dựng).

- Bổ sung 10 bài tập ôn tập cho các dạng trong chuyên đề (SKKN năm 2019-

2020 chưa xây dựng).

- Phần giải pháp thực hiện được sắp xếp logic theo trình tự: Dạng bài tập,

phương pháp giải chung, ví dụ áp dụng và cuối cùng bài tập vận dụng.

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

2

LUAN VAN CHAT LUONG download : add [email protected]

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ó, lại khó khăn hơn rất nhiều khi học sinh bắt buộc phải

lập trình giải các bài toán yêu cầu mức độ tư duy cao trong các đề học sinh giỏi.

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, bài tập kiểu xâu 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 xâu và đưa ra phương pháp giải chung cho các dạng bài tập đó,

các đề thi học sinh giỏi cấp tỉnh trên 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 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 ví dụ áp dụng và đưa ra các bài tập vận dụng, bài tập học sinh tự giải

cho từng 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.

Kiến thức kiểu dữ liệu xâu thường được quy về một trong các dạng bài tập sau:

Dạng bài tập kiểu xâu đơn giản

Dạng bài tập mã hóa và giải mã

xâu Dạng bài tập xử lý các xâu con

Dạng bài tập xâu đối xứng

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ố

Dạng bài tập tính tần số xuất hiện của các kí tự ‘0’.. ‘9’ hoặc ‘a’ .. ‘z

hoặc ‘A’ .. ‘Z’ có trong xâu

Dạng bài tập ghép thành số lớn nhất hoặc số nhỏ nhất với các phần tử

của mảng là xâu kí tự

3

LUAN VAN CHAT LUONG download : add [email protected]

Dạng bài tập tìm cách xóa trong xâu S K kí tự để xâu còn lại là xâu có

giá trị lớn nhất hoặc xâu có giá trị nhỏ nhất

Dạng bài tập tìm cách xóa trong xâu S một số kí tự để xâu còn lại là xâu

có K kí tự có giá trị lớn nhất hoặc có giá trị nhỏ nhất

Dạng bài tập tìm xâu chung dài nhất hoặc tìm các phần tử chung dài nhất

của hai xâu S1 và S2

NỘI DUNG CỤ THỂ:

2.3.1 Các kiến thức cơ bản về kiểu xâu [1]

2.3.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

2.3.1.2 Khai báo

Var <Tên biến xâu>: 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.

2.3.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.

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: >, <, =, <>, >=,

<= - 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.

c. Các hàm và thủ tục xử lí xâu.

- Thủ tục Delete(S,vt,N) xóa trong xâu S từ vị trí vt, N kí tự. -

Thủ tục Insert(S1,S2,vt) chèn xâu S1 vào xâu S2 từ vị trí vt.

- Thủ tục 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.

- Thủ tục 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.

4

LUAN VAN CHAT LUONG download : add [email protected]