Sáng kiến kinh nghiệm THPT: Rèn luyện kỹ năng lập trình với chủ đề xâu ký tự cho học sinh khá giỏi trong ngôn ngữ lập trình C++ và Python

SỞ GIÁO DỤC VÀ ĐÀO TẠO NGHỆ AN TRƯỜNG THPT YÊN THÀNH 3 ----------------------------------

SÁNG KIẾN

Đề tài:

RÈN LUYỆN KỸ NĂNG LẬP TRÌNH

VỚI CHỦ ĐỀ XÂU KÝ TỰ CHO HỌC SINH KHÁ GIỎI

TRONG NGÔN NGỮ LẬP TRÌNH C++ VÀ PYTHON

TÁC GIẢ:

ĐIỆN THOẠI:

Tô Thị Tường 0975905669 Toán – Tin

TỔ:

THỜI GIAN THỰC HIỆN: Năm học 2019 - 2020

Năm học 2020 - 2021

----------------------------------

1

Đề tài: “RÈN LUYỆN KỸ NĂNG LẬP TRÌNH VỚI CHỦ ĐỀ XÂU KÝ TỰ

CHO HỌC SINH KHÁ GIỎI

TRONG NGÔN NGỮ LẬP TRÌNH C++ VÀ PYTHON”

MỤC LỤC

NỘI DUNG Trang

3 Phần 1 - ĐẶT VẤN ĐỀ:

I - Lý do chọn đề tài. 3

II – Điểm mới của đề tài. 4

5 Phần 2 - NỘI DUNG.

I – CƠ SỞ LÝ LUẬN 5

1. Vai trò của việc rèn luyện kỹ năng lập trình cho học sinh 5 khá giỏi.

2. Sự cần thiết dạy học cho học sinh khá giỏi về ngôn ngữ lập 5 trình C++ và Python.

3. Tầm quan trọng của chủ đề Xâu ký tự trong dạy học lập 6 trình.

II – THỰC TRẠNG VẤN ĐỀ 6

1. Thực trạng dạy học ngôn ngữ lập trình C++, Python ở các 6 trường THPT.

2. Thực trạng dạy học ngôn ngữ lập trình C++, Python ở 7 trường chúng tôi.

3. Thực trạng dạy học chủ đề xâu dữ liệu cho đối tượng học 7 sinh khá giỏi.

III – GIẢI QUYẾT VẤN ĐỀ 8

8 1 – Một số đặc tính và kiến thức cơ bản về xâu dữ liệu trong NNLT C++ và Python

1.1 Một số đặc tính khác nhau giữa Xâu trong C++ và Xâu 8 trong Python

1.2 Tóm tắt một số thao tác xử lý xâu trong C++ 8

2

1.3 Tóm tắt một số thao tác xử lý xâu trong Python 10

11 2 – Rèn luyện kỹ năng lập trình với chủ đề Kiểu xâu

11 2.1 Ôn luyện kỹ năng sử dụng thao tác xử lý xâu qua một số bài toán cơ bản

19 2.2 Rèn luyện kỹ năng giải một số dạng bài tập phổ biến về xâu ký tự.

2.2.1 Dạng bài tập yêu cầu biến đổi xâu 19

2.2.2 Dạng bài tập có yêu cầu duyệt xử lý xâu con 23

2.2.3 Dạng bài tập có yêu cầu xử lý số lớn. 27

31 3 - Một số bài tập mở rộng và nâng cao

42 4 - Hiệu quả của sáng kiến

43 Phần 3. PHẦN KẾT LUẬN

I - Kết luận chung 43

II – Ý nghĩa của đề tài 43

III - Khả năng ứng dụng, mở rộng của đề tài 44

IV - Đề xuất 44

DANH MỤC CÁC CHỮ VIẾT TẮT TRONG SÁNG KIẾN

Nội dung Viết tắt

Giáo dục phổ thông GDPT

Phát triển năng lực. PTNL

Trung học phổ thông THPT

Giáo viên GV

Học sinh HS

Ngôn ngữ lập trình NNLT

Ngôn ngữ lập trình C++ C++

3

Ngôn ngữ lập trình Python Python

Phần 1. ĐẶT VẤN ĐỀ

I. LÝ DO CHỌN ĐỀ TÀI.

Giáo dục phổ thông nước ta đang thực hiện bước chuyển từ chương trình giáo dục tiếp cận nội dung sang chương trình giáo dục “định hướng năng lực”. Trong chương trình giáo dục phổ thông mới, bộ môn Tin học có rất nhiều điểm mới, trong đó Bộ GD-ĐT đã ban hành hướng dẫn điều chỉnh nội dung dạy học, cho phép và khuyến khích các cơ sở giáo dục dần loại bỏ ngôn ngữ lập trình Pascal lựa chọn giảng dạy các ngôn ngữ lập trình có tính cập nhật, hiện đại, và thông dụng như C++, Python…

Hưởng ứng thực hiện nhiệm vụ đổi mới của ngành ở trường chúng tôi đã triển khai dạy học ngôn ngữ lập trình C++ cho toàn bộ học sinh khối 11 thay thế Pascal và trong các hoạt động nhóm chuyên môn chúng tôi đã tổ chức nghiên cứu về ngôn ngữ Python, tổ chức Câu lạc bộ Tin học tập hợp các học sinh yêu thích, đam mê Tin học bước đầu triển khai cho học sinh có sân chơi bổ ích, lành mạnh, thu hút học sinh khá giỏi tham gia học tập, chia sẻ lẫn nhau nhằm khơi dậy niểm đam mê tin học đối với học sinh, đồng thời nâng cao năng lực chuyên môn của giáo viên, trang bị kiến thức, nghiệp vụ sẵn sàng thực hiện tốt nhiệm vụ đổi mới góp phần đi tới đạt mục tiêu chung của ngành.

Là một giáo viên bộ môn Tin học, bên cạch việc dạy học các kiến thức phổ thông về tin học thì việc bồi dưỡng học sinh khá giỏi cũng hết sức quan trọng; trách nhiệm của người giáo viên Tin học là tổ chức các hoạt động học tập cho học sinh để phát triển hệ thống năng lực mà một học sinh phổ thông cần phải có. Khi giảng dạy tôi thường phân tích những điểm ưu, nhược của các ngôn ngữ lập trình để các em có cái nhìn tổng quan, bao quát về một số ngôn ngữ lập trình như C++, Python để gieo niềm đam mê định hướng những học sinh có năng lực vào đội ngũ nhân lực CNTT chất lượng cao của đất nước.

4

Qua quá dạy học, tôi nhận thấy chủ đề “Xâu ký tự” là một nội dung rất quan trọng trong việc tiếp cận ngôn ngữ lập trình bậc cao, xử lý xâu ký tự cũng là yêu cầu thường gặp trong việc xây dựng các phần mềm ứng dụng thực tiễn, nhưng việc dạy học chủ để này ở một số trường THPT còn gặp nhiều khó khăn, hiệu quả chưa cao. Với niềm đam mê chuyên môn, ham học hỏi tôi luôn tìm tòi nghiên cứu và tôi đã có những giải pháp tốt nhất nhằm đem lại hiệu quả cao trong công tác bồi dưỡng học sinh khá giỏi và đã đạt được những kết quả mong đợi. Tôi xin chia sẻ sáng kiến chủ đề “Rèn luyện kỹ năng lập trình với chủ đề xâu ký tự cho học sinh khá giỏi trong ngôn ngữ lập trình C++ và Python” với mong muốn đưa ra được giải pháp nhằm nâng cao hiệu quả bồi dưỡng học sinh khá giỏi và giúp giáo viên có thêm một số cách thức để ôn luyện phù hợp. Qua đó, tôi cũng mong muốn mọi giáo viên Tin học luôn có ý thức tìm tòi, nghiên cứu nâng cao trình độ, năng lực chuyên môn, thực hiện tốt công cuộc đổi mới của ngành.

II. ĐIỂM MỚI CỦA ĐỀ TÀI

- Hiện nay Python là ngôn ngữ lập trình đang được sử dụng rộng rãi để tạo ra các ứng dụng Trí tuệ nhân tạo (AI), phân tích dữ liệu lớn (Big data), học máy (machine learning).... Trong chương trình GDPT mới 2018, python sẽ là một lựa chọn phù hợp để giảng dạy cho học sinh THPT vì câu lệnh đơn giản ngắn gọn, dễ viết, dễ tiếp cận. Với những lý do trên, trường chúng tôi đã triển khai dạy học ngôn ngữ lập trình C++ song song với ngôn ngữ lập trình Python cho học sinh khá giỏi thông qua các số hoạt động học tập như Sinh hoạt Câu lạc bộ Tin học, trong bồi dưỡng học sinh khá giỏi và nghiên cứu khoa học kỹ thuật.

- Sáng kiến này là sự đón đầu giúp giáo viên chuẩn bị kiến thức chuyên môn nghiệp vụ để triển khai chương trình chương trình GDPT 2018 một cách hiệu quả nhất.

- Sáng kiến đã xây dựng các bài toán thành một hệ thống theo một trình tự logic có sự sắp đặt của phương pháp và quy trình giải toán, giúp học sinh dễ dàng tiếp cận với nội dung và rèn luyện tư duy thuật toán .

- Sáng kiến đã chọn lọc hệ thống các bài tập thích hợp, sắp xếp một cách logic, hợp lí từ dễ đến khó nhằm giúp học sinh củng cố kiến thức, rèn luyện kỹ năng phát triển tư duy và biết áp dụng Tin học vào thực tiễn.

5

- Thông qua việc hướng dẫn giải các bài toán giáo viên rèn luyện kỹ năng lựa chọn thuật toán cho học sinh bằng cách định hướng, uốn nắn, trau chuốt từng lời giải từng bài tập, qua đó góp phần tạo niềm tin và hứng thú học tập.

Phần 2. NỘI DUNG

I - CƠ SỞ LÝ LUẬN:

1. Vai trò của việc rèn luyện kỹ năng lập trình cho học sinh khá giỏi.

Trong thời công nghệ 4.0, ngành công nghệ thông tin (CNTT) nói chung và Tin học nói riêng đang phát triển một cách mạnh mẽ. Mọi ngành nghề, lĩnh vực hay hoạt động nào trong xã hội hiện đại cũng cần tới sự góp mặt của CNTT, ở đâu ứng dụng của CNTT cũng vô cùng quan trọng. Vì vậy, nhu cầu về nguồn nhân lực CNTT là rất lớn và vẫn còn tiếp tục tăng vọt trong những năm tiếp theo, việc nâng cao chất lượng nguồn nhân lực CNTT để đáp ứng yêu cầu phát triển và hội nhập kinh tế quốc tế của đất nước là một nhiệm vụ hết sức cấp thiết hiện nay. Là một giáo viên bộ môn Tin học, bên cạch việc dạy học các kiến thức phổ thông về tin học ứng dụng thì việc dạy học lập trình cũng hết sức quan trọng; trách nhiệm của người giáo viên Tin học là giúp học sinh hiểu hơn về sự hoạt động của máy tính, am hiểu về khoa học kỹ thuật, góp phần định hướng những học sinh có năng lực và đam mê Tin học vào đội ngũ nhân lực CNTT chất lượng cao của đất nước.

2. Sự cần thiết dạy học cho học sinh khá giỏi về ngôn ngữ lập trình C++

và Python.

Ngôn ngữ lập trình C++ và Python là ngôn ngữ lập trình phù hợp cho việc dạy học trong trường phổ thông, đều có thể sử dụng trong kỳ thi học sinh giỏi tỉnh Nghệ An vừa qua; đây cũng là hai trong những ngôn ngữ đang được sử dụng phổ biến hiện nay trong việc thiết kế, xây dựng các phần mềm ứng dụng thực tiễn và có những ưu thế riêng nhất định.

Ngôn ngữ lập trình C++ rất phù hợp để rèn luyện cho học sinh hiểu sâu về thuật toán cũng như phân tích, đánh giá chính xác hiệu suất thuật toán. Trong lập trình thi đấu ở chương trình trung học phổ thông, ngôn ngữ C++ là ngôn ngữ được lựa chọn hàng đầu.

Ngôn ngữ lập trình Python khá đơn giản giúp học sinh dễ học, dễ viết nhưng việc thực thi chương trình rất chậm không phù hợp với lập trình thi đấu trong giai đoạn hiện nay nhưng lại phù hợp hơn với định hướng giáo dục Stem của bộ môn Tin học (Sở GD&ĐT Nghệ An đã có công văn số 1677/SGD&ĐT- GDTrH ngày 26/8/2020 về hướng dẫn thực hiện giáo dục STEM trong trường trung học từ năm học 2020-2021)

6

Việc dạy học cho đối tượng học sinh khá giỏi cả 2 ngôn ngữ giúp các em thấy được sự đa dạng phong phú trong lĩnh vực lập trình; giúp các em có cái nhìn tổng quát, toàn diện hơn; biết ưu, nhược điểm của mỗi ngôn ngữ từ đó kích thích sự tìm tòi, khám phá thúc đẩy niềm đam mê say sưa với Tin học; giúp các em có định hướng nghề nghiệp sớm hơn và phấn đấu để đạt mục tiêu của mình.

3. Tầm quan trọng của chủ đề Xâu ký tự trong dạy học lập trình.

Chủ đề “Xâu dữ liệu” là một nội dung rất quan trọng trong việc tiếp cận ngôn ngữ lập trình bậc cao và cũng là yêu cầu thường gặp khi xây dựng các phần mềm ứng dụng thực tiễn.

Trong việc dạy học lập trình, giáo dục Stem, bồi dưỡng học sinh khá giỏi ở trường phổ thông, chủ đề Xâu dữ liệu là một nội dung trọng tâm. Học sinh cần nắm được các thao tác xử lý trên xâu, có kỹ năng tốt trong việc phân tích bài toán và lựa chọn phương pháp phù hợp để có chương trình tốt hơn cả về độ sáng sủa của thuật toán lẫn thời gian thực hiện chương trình. Để đạt được điều đó, giáo viên cần lựa chọn các ví dụ, bài tập đảm bảo tính mục đích, tính khả thi, tính hiệu quả; các bài toán đưa ra chứa đựng những mâu thuẫn cần giải quyết, gợi ra cho học sinh nhiều hướng suy nghĩ, nhiều cách giải quyết vấn đề. Thiết kế trình tự thực hiện các bài toán cũng được xem là cơ sở quan trọng trong việc truyền tải kiến thức và kỹ năng, cần chú ý vận dụng linh hoạt cho từng trường hợp cụ thể để đạt mục đích dạy học.

II - THỰC TRẠNG VẤN ĐỀ

1. Thực trạng dạy học ngôn ngữ lập trình C++, Python ở các trường THPT.

Ngôn ngữ lập trình C++, Python là ngôn ngữ được định hướng dạy học trong chương trình GDPT 2018 và được khuyến khích triển khai dạy học trong giai đoạn chuyển tiếp hiện nay nhưng việc thực hiện còn có một số khó khăn nhất định:

+ SGK hiện hành dùng ngôn ngữ lập trình Pascal để minh họa nên học sinh không có sách phù hợp để làm tài liệu học tập. Việc tìm kiếm tài liệu dạy học phù hợp trình độ học sinh rất vất vả.

+ Đối với giáo viên việc trao đổi, chia sẻ, học hỏi kinh nghiệm gặp nhiều khó khăn do hầu hết đội ngũ giáo viên đều quen với ngôn ngữ lập trình Pascal, chưa mạnh dạn chuyển sang dạy ngôn ngữ khác có tính ưu việt hơn.

+ Kiến thức về lập trình không nằm trong nội dung thi THPT quốc gia nên hầu hết học sinh không coi trọng, ít học bài và làm bài tập chỉ những học sinh đã yêu thích, đam mê mới đầu tư thời gian cho việc học lập trình. Vì thế lượng giáo viên đam mê chuyên môn, đầu tư thời gian trăn trở nghiên cứu cải tiến cách dạy, cách học không nhiều.

7

+ Thời lượng dành cho dạy học ngôn ngữ lập trình 1,5 tiết/tuần, để mô tả thuật toán giải các bài toán trên máy tính là rất ít để có thể hiểu rõ ràng và áp dụng thành thạo ngôn ngữ lập trình. Thêm vào đó, cơ sở vật chất chưa đáp ứng được nhu cầu học tập nên việc triển khai dạy học chỉ có thể giúp học sinh hiểu được cơ bản quá trình giải một bài toán trên máy tính, còn để tất cả học sinh tự giải một bài hoàn chỉnh là rất khó.

2. Thực trạng dạy học ngôn ngữ lập trình C++, Python ở trường chúng tôi.

Từ năm học 2018 - 2019 chúng tôi đã được tham dự các lớp tập huấn do sở GD & ĐT Nghệ An tổ chức về lập trình trên ngôn ngữ lập trình C++. Năm học 2019 – 2020 tiếp tục tham dự tập huấn và được khuyến khích triển khai dạy học ngôn ngữ C++ thay Pascal. Hào hứng thực hiện nhiệm vụ đổi mới của ngành, chúng tôi đã mạnh dạn đưa C++ vào dạy học ở một số lớp. Đến năm học 2020 – 2021, trường chúng tôi đã triển khai cho toàn bộ học sinh khối 11 trong chương trình chính khóa.

Trong năm học 2019-2020, chúng tôi đã tập hợp những học sinh có học lực khá giỏi, yêu thích lập trình, truyền cảm hứng cho các em, thành lập Câu lạc bộ Tin học. Bước đầu tổ chức cho các em học tập, trao đổi về lập trình trên 3 ngôn ngữ lập trình là C++, Scratch và Python. Đối với những em học sinh lớp 10 mới tham gia chúng tôi cho làm quen với ngôn ngữ lập trình Scratch để kích thích hứng thú và giúp các em làm quen với tư duy máy tính, sau đó chúng tôi cho tiếp cận dần với ngôn ngữ lập trình C++ và Python.

Trong quá trình triển khai thực hiện chúng tôi đã gặp rất nhiều khó khăn vướng mắc cả về kiến thức chuyên môn lẫn nghiệp vụ sư phạm. Với sự yêu nghề, nhiệt huyết với học sinh, tôi đã không ngừng tìm tòi, nghiên cứu trau dồi kiến thức đồng thời tích cực kết bạn với các đồng nghiệp trên mọi miền tổ quốc để giao lưu, học hỏi nâng cao trình độ. Qua quá trình này tôi cũng đã có những sáng kiến đem áp dụng mang lại kết quả rất khả quan, đã đúc rút thành những kinh nghiệm đáng chia sẻ.

3. Thực trạng dạy học chủ đề xâu dữ liệu cho đối tượng học sinh khá giỏi.

+ Chủ đề Xâu dữ liệu trong C++, Python có hệ thống khái niệm, câu lệnh, hàm xử lý đa dạng phong phú mà tài liệu tham khảo lại rất ít ỏi. Nên việc tìm tòi tài liệu, bài tập phù hợp với trình độ học sinh đã gặp rất nhiều khó khăn, việc tổng hợp bài tập và đề thi thành các dạng bài tập phục vụ giảng dạy mất rất nhiều thời gian. Đặc biệt đối với những giáo viên ít tham gia bồi dưỡng thì còn vất vả hơn nhiều.

+ Qua dạy học chủ đề Xâu dữ liệu những năm trước, tôi đã khảo sát các cấp độ nhận thức của học sinh cho kết quả như sau: Đa số học sinh chỉ đạt ở mức độ biết và hiểu, vận dụng được thì không đến 50% học sinh. Trong khi đó đối với học sinh khá giỏi yêu cầu cao hơn như viết được chương trình một số bài toán đơn giản; liên hệ được kiến thức về xâu với các tình huống trong thực tiễn và vận dụng dữ liệu kiểu xâu vào giải bài toán ứng dụng cụ thể.

8

Lo lắng trước thực tế đó, tôi đã đầu tư thời gian, không ngừng học hỏi, nghiên cứu xây dựng nội dung, lựa chọn phương pháp, kỹ thuật phù hợp để kích thích đam mê, hứng thú giúp học sinh hình thành kiến thức và phát triển các kỹ năng, năng lực lập trình một cách tốt nhất. Kết quả trong kỳ thi HSG những năm gần đây, học sinh của tôi đã đạt được kết quả đáng tự hào.

III – GIẢI PHÁP

1 – MỘT SỐ ĐẶC TÍNH VỀ XÂU VÀ HỆ THỐNG KIẾN THỨC CỐT LÕI.

1.1 Một số đặc tính khác nhau giữa Xâu trong C++ và trong Python.

Xâu trong C++ Xâu trong Python

- Là chuỗi ký tự trong bảng mã ASCII.

- Python hỗ trợ hoàn toàn cho bảng mã Unicode.

- Tên kiểu dữ liệu: str - Tên kiểu dữ liệu: string

- Các ký tự của xâu được đặt trong cặp nháy kép.

- Các ký tự của xâu được đặt trong cặp nháy đơn hoặc kép. Xâu trên nhiều dòng được đặt trong cặp 3 nháy đơn hoặc 3 nháy kép.

- Các ký tự trong xâu được đánh chỉ số từ trước ra sau bắt đầu từ 0 và đảo chiều âm từ sau về trước bắt đầu từ -1. - Các ký tự trong xâu được đánh chỉ số từ trước ra sau bắt đầu từ 0; không đánh chỉ số ngược.

- Khai báo: Trong Python không cần khai báo, để tạo biến xâu ta chỉ cần gán xâu cho biến đó. - Khai báo: Để sử dụng cần khai báo biến xâu: string ;

- Trong Python, xâu là bất biến, không thể thực hiện các thao tác làm thay đổi giá trị của xâu - Trong C++ có thể thực hiện các thao tác làm thay đổi giá trị của xâu

- Python không có kiểu dữ liệu ký tự, một ký tự cũng thuộc kiểu xâu.

- Trong C++ có kiểu dữ liệu ký tự: char - Có thể thực hiện xóa, hoặc chèn ký tự theo chỉ số - Không thể thực hiện xóa, chèn ký tự theo chỉ số nhưng vẫn cho phép truy xuất ký thự theo chỉ số

- Không cho phép thực hiện phép nhân xâu với một số nguyên. - Cho phép thực hiện phép nhân xâu với một số nguyên.

1.2 Tóm tắt một số thao tác xử lý xâu trong C++

* Một số thao tác cơ bản với xâu trong C++

- Phép ghép nối xâu: +

- Phép so sánh: >, >=, <, <=, ==, !=

9

- Hàm lấy độ dài xâu s: s.length() hoặc s.size();

- Hàm sao chép trong xâu s từ chỉ số VT lấy n ký tự: s.substr(VT, n);

- Hàm chèn thêm vào xâu x vào xâu s tại vị trí VT: s.insert(VT, x);

- Hàm xóa trong xâu s từ chỉ số VT xóa đi n ký tự: s.erase(VT, n);

- Hàm tìm kiếm: tìm vị trí đầu tiên xuất hiện xâu x trong xâu s: s.find(x). Nếu xâu x không có trong xâu S thì kết quả = -1

- Hàm tìm kiếm ngược: tìm vị trí cuối cùng xuất hiện xâu x trong xâu s: s.rfind(x). Nếu xâu x không có trong xâu S thì kết quả = -1

- Hàm thay thế n ký tự từ vị trí VT của xâu s bởi xâu x: s.replace(VT,n,x);

- Hàm đổi ký tự thành ký tự hoa: toupper(ch);

- Hàm đổi ký tự thành ký tự thường: tolower(ch)

* Một số thao tác mở rộng với xâu trong C++

- Hàm chuyển xâu s thành số n kiểu int: n = atoi(s.c_str());

- Hàm chuyển xâu s thành số n kiểu long: n = atol(s.c_str());

- Hàm chuyển xâu s thành số n kiểu long long: n = atoll(s.c_str());

- Hàm chuyển xâu s thành số n kiểu float: n = atof(s.c_str());

- Hàm chuyển số n thành xâu s:

stringstream convert; covert << n; s = convert.str();

- Hàm s.size(); lấy chiều dài của xâu s.

- Hàm s.insert(VT, s1, n); Thêm n ký tự vào xâu s từ chuỗi s1 vào vị trí Vt. Nếu n có độ dài lớn hơn độ dài chuỗi s1 thì tiếp tục thêm vào 1 khoảng trắng và sau đó lại tiếp tục thêm các ký tự của s1cho đủ n ký tự.

- Hàm s.insert(VT, n, 'z'); Thêm n lần ký tự z vào vị trí VT.

- Hàm s.insert(s.begin() + x, s2.begin() + y, s2.begin() + z); Thêm chuỗi ký

tự con của chuỗi s2 bắt đầu từ vị trí y cho đến vị trí z - 1 vào vị trí x trong xâu s.

- Hàm s.erase(S.begin() + x); Xóa đi trong xâu S ký tự tại vị trí x.

- Hàm s.erase(s.begin() + x, s.begin() + y); Xóa đi các ký tự từ chỉ số x đến

chỉ số y – 1.

- s.find(x, vt): Tìm kiếm vị trí đầu tiên xuất hiện xâu x trong xâu s.

- s.rfind(x, vt): Tìm kiếm vị trí cuối cùng xuất hiện xâu x trong xâu s.

- Transform(s.begin(), s.end(), s.begin(), ::toupper); hàm chuyển tất cả các

ký tự trong xâu s thành chữ hoa.

- Transform(s.begin(), s.end(), s.begin(), ::tolower); hàm chuyển tất cả các

ký tự trong xâu s thành chữ thường.

10

- .....

1.3 Tóm tắt một số thao tác xử lý xâu trong Python

* Một số thao tác cơ bản với xâu trong Python

- Phép ghép nối xâu: +

- Phép so sánh: >, >=, <, <=, ==, !=

- Phép toán a in b: cho kết quả = True nếu a là xâu con của b, ngược lại thì

kết quả là False

- Thao tác cắt trích: s[start : end : step] lần lượt duyệt và trích các phần tử thuộc phạm vi từ vị trí start đến vị trí end-1 sau mỗi lần lấy một phần tử trong phạm vi thì di chuyển con trỏ với bước nhảy có độ rộng step. Các tham số trên có thể vắng mặt: nếu thiếu start thì mặc định là bắt đầu từ đầu xâu, thiếu end thì mặc định đến hết xâu, thiếu step thì mặc định là 1

- Hàm lấy độ dài xâu s: len(s);

- Sao chép trong xâu s: ta sử dụng thao tác cắt trích xâu để gán cho biến

khác.

- Chèn và Xóa xâu: Trong python không cho phép chèn vào xâu. Ta có thể

sử dụng hàm replace() hoặc thao tác cắt trích kết hợp ghép nối để xử lý.

- Hàm tìm kiếm: tìm vị trí đầu tiên xuất hiện xâu x trong xâu s: s.find(x).

Nếu xâu x không có trong xâu S thì kết quả = -1

- Hàm tìm kiếm ngược: tìm vị trí cuối cùng xuất hiện xâu x trong xâu s:

s.rfind(x). Nếu xâu x không có trong xâu S thì kết quả = -1

- Hàm thay thế: s.replace(s1, s2) thay thế xâu con s1 của xâu s bởi xâu s2

trả về một xâu mới.

- Hàm ord(ch): cho mã ASCII thập phân của ký tự ch.

- Hàm chr(x): cho ký tự có mã ASCII là x

- Hàm tạo xâu in hoa từ xâu s: s.upper()

- Hàm tạo xâu in thường từ xâu s: s.lower()

* Một số thao tác mở rộng với xâu trong Python

- Hàm tìm kiếm: s.find(sub, [start], [end]), với ý nghĩa tìm xâu con sub trong xâu s, vị trí bắt đầu tìm kiếm là start và vị trí kết thúc tìm kiếm là end, nếu vắng start thì mặc định bắt đầu tìm là vị trí 0 (cận trái) và nếu vắng end thì mặc định vị trí kết thúc tìm kiếm là cuối xâu. Nếu không tìm thấy thì kết quả = -1

- s.rfind(x, [start], [end]): Tìm kiếm vị trí cuối cùng xuất hiện xâu x trong

xâu s bắt đầu từ vị trí end-1, trở về vị trí start.

- Hàm thay thế: s.replace(s1, s2) để thay thế phần xâu con s1 bằng một xâu

11

s2, trả về một xâu mới.

- Hàm capitalize() viết hoa ký tự đầu tiên trong xâu, các chữ còn lại viết

thường

- Hàm s.strip(ch): trả về xâu mới có giá trị bằng xâu s đã xóa ký tự ch bên

trái, bên phải hoặc xóa ký tự bên trái, bên phải.

- Hàm s.startswith(x) Dùng để kiểm tra chuỗi s có bắt đầu bằng chuỗi con x

hay không

- Hàm s.endswith(x) Dùng để kiểm tra chuỗi s có kết thúc bằng chuỗi con x

hay không

- Hàm s.count(x) sẽ trả về số lần xuất hiện của chuỗi con x trong chuỗi mẹ s.

- Hàm ds = s.split(x): cắt xâu s thành nhiều chuỗi con, dựa vào tiêu chí ngăn cách để cắt là xâu x lưu vào list có tên ds. Nếu vắng mặt xâu x thì việc cắt dựa vào xâu con các dấu cách.

- Hàm s=x.join(ds): nối các xâu trong list ds thành xâu s bởi xâu gắn kết x.

2. RÈN LUYỆN KỸ NĂNG LẬP TRÌNH VỚI CHỦ ĐỀ KIỂU XÂU

Rèn luyện kỹ năng lập trình cho học sinh cần xây dựng các bài toán thành một hệ thống theo một trình tự logic có sự sắp đặt của phương pháp và quy trình giải toán, giúp học sinh dễ dàng tiếp cận với nội dung bài học, đồng thời có thể phát triển tư duy cũng như tạo ra niềm vui và sự hứng thú trong học tập.

2.1 Ôn luyện kỹ năng sử dụng thao tác xử lý xâu qua một số bài toán cơ bản

Để giúp học sinh ghi nhớ, khắc sâu và vận dụng linh hoạt các thao tác xử lý cơ bản trên xâu, tôi thường đưa ra các bài tập cơ bản rồi cho học sinh phân tích, tìm các cách giải quyết khác nhau. Những bài toán này không yêu cầu cao về mặt thuật toán mà cần huy động hết vốn kiến thức để có càng nhiều giải pháp càng tốt. Chương trình giải bài toán có nhiều cách diễn đạt khác nhau, giáo viên có thể yêu cầu các em diễn đạt hết các cách để rèn luyện kỹ năng diễn đạt câu lệnh.

Bài luyện tập 1:

Mục tiêu: Rèn luyện kỹ năng sử dụng các phép toán: ghép xâu, lấy độ dài

xâu, đảo xâu, duyệt thuận, duyệt ngược xâu:

Bài toán 1: Viết chương trình nhập vào một xâu ký tự S, đưa ra xâu đó

nhưng được viết theo chiều ngược lại.

Ý tưởng giải thuật:

Cách 1: Sử dụng phép toán ghép nối (+): Khởi tạo biến kq= “” Duyệt lần lượt các ký tự của xâu ghép nối vào xâu kq (việc duyệt

12

và ghép nối có thể có rất nhiều cách diễn đạt)

Cách 2: Sử dụng hàm đảo Xâu: trong C++ sử dụng hàm reverse, trong

Python dùng thao tác cắt trích s[start : end : step] .

Chương trình tham khảo viết bằng C++:

Ý tưởng sư phạm: Thông qua các chương trình nhấn mạnh cho học sinh các thao tác đã được vận dụng trong bài toán này và ý nghĩa, kỹ thuật sử dụng các thao tác.

- Hàm s.length(): lấy độ dài xâu s, ngoài ra s.size() cũng cho độ dài xâu s.

- Phép cộng (+): Ghép nối xâu.

- Hàm reverse(s.begin(), s.end()): Đảo xâu.

13

Chương trình tham khảo viết bằng Python:

Ý tưởng sư phạm:

Thông qua các chương trình nhấn mạnh cho học sinh các thao tác đã được vận dụng trong bài toán này và ý nghĩa, kỹ thuật sử dụng các thao tác trong Python.

- Hàm len(): lấy độ dài xâu s.

- Phép cộng (+): Ghép nối xâu.

- Thao tác Cắt trích: s[start : end : step]

Ý nghĩa là, lần lượt duyệt và trích các phần tử thuộc phạm vi từ vị trí start đến vị trí end-1 sau mỗi lần lấy một phần tử trong phạm vi thì di chuyển con trỏ với bước nhảy có độ rộng step. Các tham số trên có thể vắng mặt: nếu thiếu start thì mặc định là bắt đầu từ đầu xâu, nếu thiếu end thì mặc định đến hết xâu, nếu thiếu step thì mặc định là 1.

Bài luyện tập 2:

Mục tiêu:

Rèn luyện kỹ năng sử dụng thao tác ghép nối, tìm kiếm, thay thế; thao tác

xóa trong C++;

Bài toán 2:

Viết chương trình nhập vào một xâu ký tự S, đưa ra xâu đó nhưng loại bỏ

các dấu cách trống.

Ý tưởng giải thuật:

Cách 1: Sử dụng thêm biến kq để lưu kết quả:

Duyệt các phần tử, nếu gặp phần tử khác cách ‘ ’ thì nối sang xâu

kết quả.

Cách 2: Duyệt tìm các dấu cách trống rồi xóa khỏi xâu.

* Trong C++:

- Ta có thể duyệt từ sau ra trước bằng lệnh for hoặc while để

tìm và xóa dấu cách.

- Dùng hàm find tìm và xóa dấu cách bằng lệnh delete hoặc

lệnh replace.

* Trong Python: (không thể xóa phần tử theo chỉ số)

- Dùng hàm replace để thực hiện

- Dùng phép toán cắt trích kết hợp ghép nối.

14

Chương trình tham khảo bằng C++:

Ý tưởng sư phạm:

Thông qua bài tập rèn luyện cho học sinh sự nhìn nhận đa hướng, mỗi bài toán có rất nhiều cách giải quyết; nhấn mạnh, khắc sâu ý nghĩa, kỹ thuật sử dụng các thao tác xử lý xâu:

- Lưu ý hàm s.length() và hàm s.size() cùng cho độ dài xâu s.

- Hàm tìm kiếm:

+ s.find(x, vt): Tìm kiếm vị trí đầu tiên xuất hiện xâu x trong xâu s. bắt đầu từ vị trí vt trở đi, nếu không có tham số vt thì bắt đầu tìm từ đầu xâu. Nếu không tìm thấy thì kết quả = -1

15

+ s.rfind(x, vt): Tìm kiếm vị trí cuối cùng xuất hiện xâu x trong xâu s. bắt đầu từ vị trí vt trở về, nếu không có tham số vt thì bắt đầu tìm từ cuối (tìm ngược từ sau về đầu). Nếu không tìm thấy thì kết quả = -1

- Hàm thay thế:

+ s.replace(vt, n, x): thay thế n ký tự trong xâu s, tính từ vị trí vt bởi

xâu x.

Chương trình tham khảo viết bằng Python:

Ý tưởng sư phạm:

Thông qua bài tập này nhấn mạnh, khắc sâu ý nghĩa, kỹ thuật sử dụng các

thao tác xử lý xâu như phép ghép nối xâu, cắt trích xâu và hàm tìm kiếm, thay thế:

+ s.find(x, [start], [end]): Tìm kiếm vị trí đầu tiên xuất hiện xâu x trong xâu s. bắt đầu từ vị trí start, kết thúc ở vị trí end-1, nếu vắng start thì mặc định bắt đầu tìm là vị trí 0 và nếu vắng end thì mặc định vị trí kết thúc tìm kiếm là cuối xâu. Nếu việc tìm kiếm không có kết quả thì hàm trả về giá trị -1

+ s.rfind(x, [start], [end]): Tìm kiếm vị trí cuối cùng xuất hiện xâu x

- Hàm tìm kiếm:

trong xâu s bắt đầu từ vị trí end-1, trở về vị trí start. - Hàm thay thế:

+ s.replace(s1, s2) để thay thế phần xâu con s1 bằng một xâu

mới s2.

Bài luyện tập 3:

Mục tiêu: Rèn luyện kỹ năng sử dụng thao tác sao chép, chèn, xóa, tìm

kiếm, thay thế trong C++; thao tác cắt trích, ghép nối, thay thế trong Python.

Bài toán 3:

Viết chương trình nhập vào từ bàn phím xâu ký tự s, tìm và thay thế tất cả

các cụm ký tự s1 thành s2.

Ví dụ:

16

Xâu nhập vào: Xâu kết quả: s = “anh oi, anh dang o đau” s1= “anh”; s2= “em”; S = “em oi, em dang o đau”

Ý tưởng giải thuật: Cách 1:

- Trong C++: Dùng hàm tìm kiếm s.find(s1) để xác định vị trí xuất hiện xâu s1 trong xâu s: vt = s.find(s1) Nếu vt != -1 tức là có xâu s1 trong xâu s thì thay thế xâu s1 bởi xâu s2 bằng hàm s.replace(vt,l1,s2); hoặc thay thế bằng lệnh xóa và chèn: s.erase(vt,l1); s.insert(vt,s2);

Lưu ý: Trong xâu có thể có rất nhiều cụm từ cần thay thế nên ta phải sử

dụng lệnh while để thay thế hết: trong khi s.find(s1) != -1 thì tiếp tục thay thế

- Trong Python: Sử dụng thao tác cắt trích, so sánh và ghép nối để thực hiện ý tưởng trên.

Cách 2: - Trong C++:

Để duyệt hết tất cả các khả năng cần thay thế ta sử dụng lệnh for kết hợp lệnh s.substr() để sao chép từng đoạn con có độ dài bằng độ dài xâu s1 rồi so sánh với s1. Nếu kết quả bằng s1 thì ta tiến hành thay thế bằng các câu lệnh tương tự cách 1.

- Trong Python: Dùng hàm replace để thực hiện.

Chương trình tham khảo bằng C++ Chương trình 1: Chương trình 2:

Ý tưởng sư phạm:

Thông qua bài tập rèn luyện nhấn mạnh, khắc sâu ý nghĩa, kỹ thuật sử dụng

17

các thao tác xử lý xâu.

Chương trình tham khảo bằng Python:

Ý tưởng sư phạm:

Thông qua bài tập này nhấn mạnh, khắc sâu kỹ thuật sử dụng các thao tác cắt

trích, thay thế.

Bài luyện tập 4:

Mục tiêu: Rèn luyện kỹ năng xử lý ký tự theo mã ASCII, kỹ thuật đếm

phân phối trên mảng với kiểu chỉ số tương ứng các ký tự.

Bài toán 4: Đếm số lần xuất hiện mỗi loại ký tự.

Cho xâu s (có độ dài không vượt quá 103) chỉ gồm các ký tự từ 'A' đến 'Z'. Cho biết có bao nhiêu loại ký tự xuất hiện trong s và đưa ra một ký tự xuất hiện nhiều nhất trong s cùng với số lần xuất hiện của ký tự đó

Ý tưởng giải thuật:

- Các ký tự từ 'A' đến 'Z' có mã ASCII tương ứng từ 65 đến 90. Nên ta sử dụng mảng T gồm 91 phần tử với kiểu chỉ số từ 0 đến 90, kiểu giá trị int để lưu số lần xuất hiện: T[65] …T[90] tương ứng số lần xuất hiện ký tự ‘A’… ‘Z’.

- Lần theo các giá trị của mảng T trên đoạn từ 65 đến 90 ta được số lượng các ký tự khác nhau (tức số lượng phần tử có giá trị khác 0 trong mảng T) và tìm giá trị lớn nhất của mảng T ta sẽ tìm được ký tự xuất hiện nhiều lần nhất.

Về nguyên tắc, ta chỉ cần sử dụng mảng với 26 phần tử kiểu int với chỉ số từ 0 đến 25, khi đó với mỗi ký tự ta chuyển sang mã ASCII rồi dịch chuyển chỉ số 65 đơn vị. Chương trình tham khảo trong Python (cách 1) sau được viết với ý tưởng này.

18

Ngoài ra, trong Python ta có thể sử dụng lệnh count để đếm số lần xuất hiện không chồng lấn của một ký tự hay xâu con bên tròn xâu lớn. Chương trình tham khảo trong Python (cách 2) sau được viết với ý tưởng này.

Chương trình tham khảo:

Chương trình viết bằng Python (cách 1)

Chương trình viết bằng C++

Chương trình viết bằng Python (cách 2)

Ý tưởng sư phạm:

19

Thông qua bài tập này nhấn mạnh cách thức sử dụng bảng mã ASCII, cách chuyển đổi qua lại giữa mã thập phân và ký tự, kỹ thuật đếm phân phối trên mảng với kiểu chỉ số tương ứng các ký tự. Ngoài ra, cần nhấn mạnh lệnh khởi tạo toàn bộ phần tử của mảng = 0, trong chương trình trên là lệnh memset, lệnh nhân (*). Lưu ý thêm lệnh ý nghĩa và cách sử dụng lệnh count trong Python.

2.2 - Rèn luyện kỹ năng giải một số dạng bài tập phổ biến về xâu ký tự:

Việc phân loại dạng bài tập chỉ mang tính tương đối, một bài tập ở dạng này hay dạng kia còn phụ thuộc rất nhều vào cách nhìn nhận đa chiều của người lập trình. Trong phạm vi đề tài này mục tiêu của tôi là rèn luyện cho học sinh một số định hướng để giúp học sinh cái nhìn tổng quan hơn, nên mỗi bài toán có thể được đề xuất nhiều cách giải từ đó học sinh có thể phân tích, lựa chọn giải pháp tốt hơn để giải quyết bài toán. (Các giải pháp được đề xuất chỉ là các cách giải quyết, chưa hẳn đã là giải pháp tối ưu để giải bài toán)

2.2.1 Dạng bài tập yêu cầu biến đổi xâu

Đâ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 thao tác, các hàm xử lý trên kiểu dữ liệu xâu để vận dụng một cách linh hoạt vào từng bài tập cụ thể.

Bài tập 1: Chuyển đổi phông chữ:

Khi soạn thảo và trình bày văn bản, việc chuyển đổi đoạn văn chữ hoa

sang thường hay chữ thường sang chữ hoa là một nhu cầu rất phổ biến.

Em hãy viết chương trình nhập vào 1 xâu s chỉ chứa dấu cách và các ký tự thuộc bảng chữ cái tiếng Anh, Hãy tạo xâu s1 chứa các tự trong xâu s nhưng ở dạng chữ hoa, tạo xâu s2 chứa các tự trong xâu s nhưng ở dạng chữ thường. Xuất kết quả xâu s1, s2 ra màn hình.

Ý tưởng giải thuật:

Cách 1: Duyệt và chuyển đổi từng ký tự:

Trong C++: Dùng hàm toupper(), tolower() để chuyển đồi từng ký tự hoặc biến

đổi qua mã ASCII.

Trong Python: Sử dụng hàm ord() và chr() để thực hiện.

Cách 2: Dùng hàm chuyển đổi đồng loạt

Trong C++: Dùng hàm transform() để chuyển đồi tất cả các ký tự.

+ transform(s.begin(), s.end(), s.begin(), ::toupper); chuyển xâu s sang chữ hoa

+ transform(s.begin(), s.end(), s.begin(), ::tolower); chuyển xâu s sang chữ thường

Trong Python: Dùng hàm upper(), lower().

+ s.upper() Hàm này trả lại xâu s sau khi chuyển tất cả các ký tự thành chữ hoa.

20

+ s.lower() Hàm này trả lại xâu s sau khi chuyển tất cả các ký tự thành chữ thường.

* Chương trình tham khảo trong C++:

Chương trình 2: Chương trình 1:

* Chương trình tham khảo trong Python:

Ý tưởng sư phạm: Rèn luyện kỹ năng vận dụng hàm chuyển đổi ký tự sang ký tự hoa toupper(), ký tự thường tolower(), hàm chuyển đổi đồng loạt sang chữ hoa, chữ thường tranform() trong C++.

Trong Python chuyển đổi chữ hoa, chữ trường dựa vào mã ASCII và hàm

21

chuyển đổi xâu sang in hoa, in thường upper(), lower().

Bài tập 2: Xóa dấu cách thừa:

Khi soạn thảo và trình bày văn bản, một số bạn thường mắc lỗi gõ nhiều

dấu cách giữa các từ.

Em hãy viết chương trình nhập vào 1 xâu s, Hãy đưa ra xâu đã loại dấu

cách thừa.

Ý tưởng giải thuật:

Ta hoàn toàn có thể duyệt xâu rồi xóa các ký tự cách liền nhau như chúng ta thường làm trong ngôn ngữ lập trình Pascal. Nhưng ở đây ta sringstream của C++ và thao tác split(), join() trong Python để chương trình đơn giản hơn.

* Chương trình tham khảo:

Chương trình viết bằng C++ Chương trình viết bằng Python

Ý tưởng sư phạm:

Rèn luyện kỹ năng vận dụng stringstream trong C++ và thao tác tách split(), nối join(). Thao tác này rất hữu ích trong việc giải quyết một số bài toán về xâu.

Bài tập 3: Mã hóa Xê Da (sách bài tập tin học 11)

22

Để giữ bí mật người ta phải mã hóa các thông tin trước khi truyền đi hoặc lưu trữ. Một trong những cách mã hóa sớm nhất được sử dụng rộng rãi thời cổ đại là cách mã hóa do Xê Da đề xuất: trong thông điệp, người ta thay đổi chữ cái bằng chữ cái đứng sau nó K vị trí trong bảng chữ cái. Việc tìm kiếm thay thế được tiến hành vòng tròn theo bảng chữ cái. Nếu bảng chữ cái có N chữ, thì sau chữ cái thứ N-1 là chữ cái N, sau chữ cái N là chữ cái thứ nhất,… Cách mã hóa này gọi là mã Xê Da. Các kí tự ngoài bảng chữ cái vẫn được giữ nguyên.

Ví dụ, bảng chữ cái tiếng Anh có 26 chữ cái. Nếu K = 2 thì có nghĩa là a được thay thế bằng c, b được thay thế bằng d, . . ., y được thay thế bằng a, z được thay thế bằng b. Các chữ cái in hoa sẽ được thay thế bằng chữ cái in hoa tương ứng. Trong trường hợp này, từ ‘TIN HOC’ sẽ được mã hóa thành ‘VKP JQE’ .

Hãy lập trình: Nhập vào từ bàn phím số nguyên K (1

Ý tưởng giải thuật:

Để dễ xử lý hơn khi dịch k ký tự theo vòng tròn, ta dùng thêm 2 biến phụ

S1 để lưu 2 lần bảng chữ cái in hoa. S2 lưu 2 lần bảng chữ cái in thường.

Duyệt từng ký tự trong xâu s, tìm vị trí xuất hiện của nó trong xâu s1, s2.

Nếu tìm thấy thì ta lấy ký tự cách nó k ký tự trên mảng tương ứng.

Chương trình tham khảo:

Chương trình viết bằng C++ Chương trình viết bằng Python

Ý tưởng sư phạm:

23

Rèn luyện kỹ năng sử dụng bảng mã ASCII để giải quyết một số bài toán. Qua đây nhấn mạnh cho học sinh cách chuyển đổi ký tự sang mã thập và từ mã thập phân sang ký tự. Trong C++ ta ép kiểu, trong Python ta dùng hàm ord(), chr(), qua ví dụ này nhấn mạnh hơn với học sinh về phép toán nhân (*) xâu.

2.2.2 Dạng bài tập có yêu cầu duyệt xử lý xâu con.

Duyệt xâu con trên xâu ký tự là một yêu cầu thường gặp khi giải các bài toán, có nhiều cách thực hiện duyệt khác nhau, để giải quyết các bài toán dạng này học sinh phải có kỹ năng nhận dạng, phân tích bài toán rồi lựa chọn thuật toán thích hợp để giải quyết.

Bài tập 1: Xâu con dài nhất

Cho xâu S, tìm xâu con liên tục dài nhất của xâu S mà không chứa chữ số nào. Kết quả đưa ra vị trí đầu và xâu con đó. Nếu có nhiều xâu con dài nhất thì đưa ra xâu đầu tiên.

Ý tưởng giải thuật:

Có rất nhiều giải thuật để duyệt tìm xâu con dài nhất thỏa mãn một điều

kiện nào đó.

Cách 1: Duyệt vét cạn thử với mọi xâu con để tìm xâu con dài nhất.

Sử dụng hai vòng for lồng nhau duyệt từ đầu đến hết xâu với mỗi cặp chỉ số đầu i và chỉ số j. Ta kiểm tra có thỏa mãn điều kiện hay không, rồi so sánh tìm xâu con thỏa mãn dài nhất.

Cách 2: Duyệt theo các xâu con với độ dài từ lớn đến bé.

Ta duyệt các xâu con với độ dài từ độ dài xâu mẹ giảm dần. Khi gặp xâu con đầu tiên thỏa mãn điều kiện thì đây chính là xâu cần tìm và ta kết thúc việc duyệt bằng lệnh break;

Cách 3: Duyệt phát triển xâu con:

Lần lượt duyệt lần lượt các ký tự trong xâu, dùng biến lmax để lưu độ dài xâu lớn nhất đã tìm được, nếu gặp ký tự thỏa mãn (không phải số) ta tăng dần độ dài xâu con. Khi gặp ký tự không thỏa mãn (ký tự số) thì ta thu được một xâu con thỏa mãn điều kiện, đem độ dài xâu này so sánh với lmax đã lưu để cập nhật lại lmax mới.

Đây là 3 cách duyệt xâu con, đoạn con dài nhất phổ biến. với từng bài toán cụ thể các mô tả về xâu con, đoạn con lại khác nhau và lúc đó phương pháp duyệt tốt nhất lại khác nhau, ta cần phân tích cân nhắc kỹ càng để lựa chọn thuật toán tốt nhất.

Với bài toán này ta sử dụng cách 3 duyệt theo phát triển xâu con với độ

phức tạp o(n).

24

Các chương trình tham khảo sau được viết theo ý tưởng này:

Chương trình viết bằng C++ Chương trình viết bằng Python

Ý tưởng sư phạm: Qua bài tập này phân tích cho học sinh:

+ Một số hướng giải dạng bài toán tìm xâu con dài nhất thỏa mãn một điều kiện nào đó, đây cũng là một dạng toán thường gặp trong các đề thi. Việc lựa chọn thuật giải nào còn phụ thuộc vào điều kiện cụ thể.

+ Lưu ý học sinh về cách sử dụng các hàm: isdigit(), isalpha()

Bài tập 2: Đảo từ trong xâu

Cho xâu ký tự s, từ là một xâu con liên tiếp không chứa dấu cách. Một

xâu ký tự có thể gồm nhiều từ.

Em hãy viết chương trình nhập vào xâu ký tự s. Đưa ra xâu đó với các từ

được viết theo chiều ngược lại.

Ví dụ: s = “di xe dap” thì kết quả là: kq =“dap xe di”

Ý tưởng giải thuật:

25

Cách 1: Duyệt trên từng ký tự của xâu: Duyệt ngược xâu từ sau ra trước, mỗi lần tìm thấy dấu cách hoặc ký tự đầu tiên của xâu, thì đọc các ký tự từ vị trí đó đến vị trí dấu cách đã gặp trước đó.

Cách 2: Duyệt tìm vị trí chứa các dấu cách copy xâu con giữa 2 dấu cách

rồi nối vào xâu kết quả.

Cách 3: (dành riêng cho Python) tách xâu thành các xâu con lưu vào list,

sau đó thực hiện đảo chiều list rồi nối lại thành xâu kết quả

Chương trình tham khảo:

Sau đây là chương trình thể hiện ý tưởng cách 2 bằng C++ và cách 3 bằng

Chương trình cách 3 bằng Python

Python

Ý tưởng sư phạm:

Qua bài toán này lưu ý học sinh:

+ Khi diễn tả thuật toán ta cần chú ý trau chuốt từng câu lệnh để chương trình trở nên ngắn gọn, sáng sủa hơn. Ví dụ trong chương trình trên việc nội thêm dấu cách vào trước và sau xâu nhập vào đã giúp việc diễn tả trở nên đơn giải hơn.

+ Khi dùng hàm find() trong vòng lặp chúng ta cần cân nhắc lựa chọn có hay không tham số vị trí bắt đầu tìm, vì một số trường hợp có thể dẫn đến việc máy phải tìm đi tìm lại một đối tượng trên xâu nhiều lần do nguyên lý hoạt động của hàm find(). Chúng ta cần giám sát để khéo léo loại tình huống đó.

+ Cũng qua bài toán này ta thấy việc sử dụng linh hoạt các hàm của

26

Python có thể thu được chương trình rất ngắn gọn, sáng sủa.

Bài tập 3: Đếm xâu con (có chồng lấn và không chồng lấn lên nhau)

Viết chương trình nhập vào 2 xâu ký tự s1, s2. Hãy cho biết số lần xuất hiện xâu s2 trong xâu s1 không chồng lấn và số lần xuất hiện xâu s2 trong s1 có chồng lấn. Ví dụ: Kết quả:

s1= “ababababaab” S2= “aba” Số lần xuất hiện không chồng lấn là: 2 Số lần xuất hiện có chồng lấn là: 4

Ý tưởng giải thuật:

Cách 1: Sử dụng hàm tìm kiếm sự xuất hiện xâu s2 trong xâu s1. Khi tìm thấy s2 trong s1, ta xóa (hoặc thay thế bởi xâu “”) toàn phần tìm thấy hoặc 1 ký tự tại vị trí tìm thấy rồi tìm tiếp. Nếu dung câu lệnh find() có tham số vị trí bắt đầu thì không cần xóa.

Cách 2: Ta có thể dùng lệnh while duyệt sao chép đoạn con của s1 có độ dài bằng l2 (độ dài xâu s2) để so sánh với s2, trong yêu cầu 1 nếu tìm thầy thì ta nhảy qua l2 vị trí tiếp theo.

Ngoài ra trong Python ta có thể sử dụng lệnh count() để đếm số lần xuất

Chương trình cách 1 bằng C++

Chương trình cách 2 bằng Python

27

hiện không chồng lấn.

Ý tưởng sư phạm: Qua bài toán này tôi muốn nhấn mạnh với học sinh:

+ Có thể cùng một ý tưởng giải thuật nhưng có rất nhiều cách diễn tả. Cần trau chuốt từng câu lệnh để chương trình chạy nhanh hơn, sáng sủa hơn. Ở đây tôi cố ý diễn đạt với nhiều cách khác nhau để học sinh thấy rõ hơn về vấn đề này. + Qua bài này học sinh biết thêm về câu lệnh count() trong Python có chức năng đếm số lần xuất hiện không chồng lấn của một xâu ký tự hay xâu con bên trong một xâu lớn.

2.2.3 Dạng bài tập có yêu cầu xử lý số lớn.

Có rất nhiều bài toán cho dưới dạng số nhưng nếu chỉ dùng số hoặc mảng số thì việc xử lý nó rất khó khăn thậm chí không thể thực hiện được, trong khi đó nếu ta biết cách dùng xâu để xử lý thì công việc trở nên thuận lợi hơn rất nhiều.

Bài tập 1: Cho số nguyên dương N (số chữ số của N không quá 106). Hãy tính tổng các số chẵn trong dãy.

Ý tưởng: Số nguyên N có giá trị quá lớn nên ta không thể xử lý N theo kiểu số. vì vậy ta đọc N vào xâu ký tự để giải quyết. Để kiểm tra tính chẵn lẻ và tính tổng các chữ số, ta xử lý trên mã ASCII của các ký tự số.

Chương trình viết bằng C++

Chương trình viết bằng Python

Chương trình tham khảo:

Ý tưởng sư phạm: Thông qua bài toán:

+ Lưu ý với học sinh một số tình huống cần sử dụng dữ liệu kiểu xâu giải

quyết bài toán kiểu số.

+ Trong C++ khi thực hiện các phép toán trên ký tự nó sẽ hiểu là thực

28

hiện tính toán với mã ASCII của ký tự đó.

Bài tập 2: Xóa số:

Cho 2 số nguyên dương N và k (số chữ số của N không quá 106, k nhỏ hơn số chữ số của N) Yêu cầu: Hãy tìm cách xóa k chữ số của N để các chữ số còn lại (vẫn dữ nguyên thứ tự) tạo thành một số có giá trị lớn nhất.

Ý tưởng:

Vì giá trị của N quá lớn nên ta phải giải quyết với kiểu dữ liệu kiểu xâu. Việc xóa đi k chữ số để lấy các chữ số còn lại thì kết quả cũng tương đương với việc chọn N-k chữ số đúng trật tự để thu được kết quả là số lớn nhất.

Để tìm chữ số lớn nhất cần lấy, ta xây dựng hàm vtm(i,j) đưa vào vị trí đầu và cuối i-j, lấy ra vị trí phần tử lớn nhất đầu tiên thuộc đoạn i-j. Lần đầu tiên lấy phần tử max chỉ số vt trong đoạn [0, k], sau đó tìm max với chỉ số đầu [vt+1, k+1]…

Chương trình tham khảo như sau:

Chương trình viết bằng C++ Chương trình viết bằng Python

29

Ý tưởng sư phạm: Thông qua bài toán trên, lưu ý với học sinh về 2 chương trình con tìm vị trí max ở trên được xây dựng với 2 ý tưởng thiết kế khác nhau. Việc sử dụng xâu phụ so= “9876543210” có thể mang lại lợi ích nhất định trong một số tình huống.

Bài tập 3: Ghép số

Cho n số nguyên dương a1, a2, . . .,an (1 < n ≤ 100), mỗi số không vượt quá 109 . Từ các số này người ta tạo ra một số nguyên mới bằng cách ghép tất cả các số đã cho, tức là viết liên tiếp các số đã cho với nhau. Ví dụ, với n = 4 và các số 123, 124, 56, 90 ta có thể tạo ra các số mới sau: 1231245690, 1241235690, 5612312490, 9012312456, 9056124123,... Có thể dễ dàng thấy rằng, với n = 4, ta có thể tạo ra 24 số mới. Trong trường hợp này, số lớn nhất có thể tạo ra là 9056124123.

Yêu cầu: Cho n số nguyên số a1, a2, . . .,an nằm trên cùng 1 dòng. Hãy

xác định số lớn nhất có thể tạo ra khi ghép các số đã cho thành một số mới.

Ý tưởng:

Lưu các số dưới dạng mảng kiểu xâu, thực hiện sắp xếp mảng theo thứ tự tăng dần theo tiêu chí sắp xếp là phần tử a[i] đứng trước phần từ a[j] khi (a[i] ghép với a[j]) > (a[j] ghép với a[i]).

Chương trình tham khảo như sau:

Chương trình viết bằng C++ Chương trình viết bằng Python

30

Ý tưởng sư phạm: Thông qua bài toán trên, nhấn mạnh với học sinh về nguyên tắc so sánh 2 xâu, câu lệnh swap tráo đổi giá trị 2 xâu trong C++ và câu lệnh gán đồng thời để tráo đổi giá trị trong Python.

Bài tập 4: SỐ MỘT

Xét các số nguyên dương K có dạng biểu diễn ở hệ thập phân có N chữ

số và chỉ bao gồm các chữ số 1, ví dụ với N = 2 có K = 11, N = 3 có K = 111.

Yêu cầu: Với N cho trước, tính K2 ( 1 ≤ N ≤ 103)

Ví dụ: Với N = 9 thì K =111111111 Kết quả: K2 = 12345678987654321

Ý tưởng:

Vì số lượng chữ số N của số K là rất lớn, nên ta không thể xử lý theo dữ

liệu kiểu số mà phải xử lý theo dữ liệu kiểu xâu.

Nhớ nguyên tắc thực hiện phép nhân một số với số có nhiều chữ số: ta lấy số đó nhân lần lượt với mỗi chữ số của số nhân từ phải sang trái, với mỗi kết quả ta đặt dịch sang trái thêm một hàng, cộng dọc các kết quả theo hàng từ phải sang trái ta có kết quả. Với bài toán này số K chỉ gồm các chữ số 1, nên kết quả của hàng i (i tăng dần từ 1 đến n sau đó giảm dần từ n-1 về 1) chính là tổng của i số 1 và giá trị nhớ của hàng bên trái.

Chương trình tham khảo như sau:

Chương trình viết bằng C++ Chương trình viết bằng Python

Ý tưởng sư phạm:

31

Thông qua bài bài toán này nhấn mạnh nguyên tắc thực hiện các phép toán số học với kiểu dữ liệu xâu, sau đó yêu cầu học sinh viết chương trình cụ thể để thực hiện phép toán số học trên 2 số nguyên lớn (lưu trử với kiểu xâu).

3 - MỘT SỐ BÀI TẬP MỞ RỘNG VÀ NÂNG CAO

Việc rèn luyện kỹ năng lập trình cho học sinh cần thực hiện thường xuyên, liên tục. Các bài tập để học sinh rèn luyện thường lấy từ ba nguồn chính: Thứ nhất: Hệ thống bài tập do giáo viên tự phát biểu, xây dựng, chọn lọc

và chỉnh sửa với mục đích, ý đồ sư phạm cụ thể trong mỗi bài.

Thứ hai: Hệ thống đề thi học sinh giỏi các cấp. Nguồn bài tập này thường có bộ test chuẩn, phân loại được độ phức tạp của thuật toán và đã được các tổ chức phê duyệt. Sau khi học sinh giải đề thì tiến hành chấm bài tự động bằng phần mềm Themis của thầy Lê Minh Hoàng để phân tích, đánh giá và rút kinh nghiệm.

Thứ ba: Hệ thống bài tập từ các website giải bài trực tuyến, với các trang website này có hệ thống bài tập đa dạng, phong phú. Có phân loại theo dạng và mức độ. Học sinh có thể viết chương trình trên nhiều ngôn ngữ lập trình khác nhau và tiến hành chấm bài tự động online.

Có rất nhiều trang cho học sinh làm bài tập và chấm bài như:

http://thptchuyen.ntucoder.net/; https://vnoi.info/problems/list/;

http://laptrinhphothong.vn/; http://vinhdinhcoder.net/; http://ntucoder.net/; …..

Trong quá trình học sinh luyện tập giáo viên cần theo dõi, hướng dẫn phân tích, nhận xét đánh giá bài làm của học sinh không chỉ về vấn đề thuật toán mà uốn nắn cả những tiểu tiết cải tiến chương trình.

Sau đây là một số bài tập và gợi ý giải để học sinh luyện tập: một số bài được lấy trong các đề thi cấp tỉnh; một số đề do giáo viên biên soạn, lựa chọn và chỉnh lý theo mục đích sư phạm; một số bài tập lấy trên trang giải bài tập và chấm bài trực tuyến:

Bài 1. LT0103 - PASSWORD

(http://laptrinhphothong.vn/Problem/Details/5839)

Yêu cầu: Cho một mật khẩu là một chuỗi các kí tự. Hãy đánh giá độ bảo

mật của mật khẩu đó.

Biết một mật khẩu hợp lệ có ít nhất 5 kí tự, chỉ bao gồm chữ cái và chữ

số (không phân biệt chữ thường hay in hoa).

Nếu mật khẩu hợp lệ in ra độ dài của chuỗi là độ bảo mật của mật khẩu.

Nếu không in ra "Error!".

Dữ liệu: Một dòng là xâu kí tự S có độ dài nhỏ hơn 1000 ký tự.

Kết quả: Độ bảo mật của mật khẩu hoặc "Error!". Ví dụ

Input Output

32

provip123 9

Gợi ý:

Trước hết kiểm tra độ dài xâu, nếu độ dài xâu dưới 5 ký tự thì in ra "Error!" rồi kết thức chương trình. Ngược lại thì ta kiểm tra trong xâu có tồn tại ký tự ngoài bảng chữ cái, chữ số.

Để kiểm tra ký tự không thuộc bảng chữ cái, chữ số ta có thể sử dụng mã

ASCII hoặc dùng hàm isalpha(), isdigit() để xác định.

Bài 2. Rút gọn xâu (Đề thi HSG lớp 12 tỉnh Nghệ An năm 2009-2010)

Cho một xâu S chỉ gồm các chữ cái in thường với độ dài tối đa 250 ký tự. Em hãy viết chương trình để tạo ra xâu SG từ xâu S bằng cách xóa các ký tự liên tiếp giống nhau trong xâu S và chỉ để lại một kí tự đại diện trong đoạn đó.

Dữ liệu vào: Đọc từ file văn bản XAUGON.INP chứa xâu S chỉ gồm các

chữ cái in thường.

Kết quả: Ghi ra file văn bản XAUGON.OUT là xâu SG tìm được.

Ví dụ:

XAUGON.INP XAUGON.OUT

hhooocccsssiiiiinnnhhh hocsinh

* Gợi ý:

Sử dụng xâu S để lưu xâu đầu vào, xâu phụ kq để lưu kết quả dầu ra. Duyệt các ký tự từ đầu xâu đến cuối xâu, nếu gặp 2 ký tự liên tiếp khác nhau S[i]!=S[i+1] thì ghép nối S[i] vào xâu kết quả.

Bài 3. Xâu con ĐỒNG NHẤT

Xâu ký tự được gọi là đồng nhất khi tất cả các ký tự trong xâu đều giống

nhau.

Cho tệp văn bản Dong_nhat.INP gồm 1 dòng chứa xâu ký tự S với độ dài không quá 104 ký tự. Hãy đưa ra xâu con đồng nhất có độ dài lớn nhất của xâu S. Nếu có nhiều xâu con thỏa mãn thì đưa ra xâu đầu tiên tính từ trái sang phải.

Kết quả ghi vào tệp Dong_nhat.OUT gồm 1 dòng là xâu con tìm được.

Ví dụ:

Dong_nhat.Inp Dong_nhat.OUT

hooocc ooo

* Gợi ý:

Khi 1 xâu đồng nhất thì các xâu con của nó cũng đồng nhất nên ta sẽ vận

33

dụng phương pháp phát triển xâu con để duyệt và tìm xâu con dài nhất.

Sử dụng biến lmax để lưu lại độ dài lớn nhất, biến luui để chỉ vị trí cuối cùng của xâu con dài nhất đã tìm được, biến dem để đếm số lượng các phần tử đồng nhất đang xét. Lần lượt duyệt các ký tự trong xâu, nếu gặp ký tự thỏa mãn (S[i] = S[i+1]) ta tăng dem. Khi gặp ký tự S[i]!=S[i+1] thì ta so sánh dem với lmax, nếu dem > lmax thì cập nhật lại lmax mới và lưu lại vị trí cuối luui=i rồi khởi tạo dem=0 để bắt đầu tìm đoạn đồng nhất mới. Khi duyệt hết xâu, kết quả chính là xâu con từ chỉ số luui-lmax+1 đến luui của xâu S.

Bài 4. NÉN XÂU (Đề thi HSG tỉnh lớp 12 năm học 2011 – 2012)

Một xâu ký tự có thể nén lại bằng 1 xâu mới bằng cách nén các ký tự giống nhau đứng cạnh nhau. Ví dụ trong xâu AAAA sẽ nén thành 4A. Hãy lập trình để nén 1 xâu ký tự in hoa theo cách trên.

Dữ liệu: Vào từ file văn bản NENXAU.INP một xâu, mà các ký tự là chữ

cái in hoa.

Kết quả: Ghi vào xâu văn bản NENXAU.OUT một xâu ký tự sau khi

nén.

Ví dụ:

NENXAU.INP MMAABBBEEEEZH NENXAU.OUT 2M2A3B4EZH

* Gợi ý:

Bài toán này ta có điểm tương tự bài toán 2 ở trên, ta vận dụng phương pháp phát triển xâu con để giải quyết bài toán. Khi kết thúc đoạn đồng nhất ta chuyển dem sang dạng xâu rồi thêm vào ký tự S[i] sau đó nối vào xâu kết quả. Khi duyệt hết các ký tự trong xâu, ta thu được xâu cần tìm.

Bài 5. Xâu ĐỐI XỨNG

Xâu đối xứng là xâu đọc giống nhau nếu ta đọc từ trái qua phải hoặc từ

phải qua trái.

Ví dụ: xâu RADAR là xâu đối xứng.

Kiểm tra xem một xâu có phải là xâu đối xứng hay không, nếu đối xứng

thì thông báo là 1, nếu không đối xứng thì thông báo là 0.

Dữ liệu: Vào từ file văn bản BAI2.INP, gồm:

- Dòng đầu tiên ghi một số nguyên N.

- N dòng tiếp theo mỗi dòng ghi các xâu cần kiểm tra.

Kết quả: Ghi ra file văn bản BAI2.OUT: gồm N dòng, mỗi dòng ghi 0 nếu

xâu tương ứng không đối xứng hoặc ghi 1 nếu xâu tương ứng đối xứng.

34

Giới hạn: 0 < N < 30000; Các xâu có độ dài không quá 255 kí tự.

Ví dụ:

BAI2.INP 3 AFHFA ACDDB ACRTT BAI2.OUT 1 0 0

* Gợi ý:

Với yêu cầu của đề bài ta thấy cần kiểm tra đối xứng của nhiều xâu, nên ta xây dựng làm KTDX(s) đầu vào là 1 xâu ký tự s, lấy ra là 1 nếu xâu đó đối xứng, lấy ra 0 nếu xâu đó không đối xứng.

Để kiểm tra xâu S có độ dài l có đối xứng hay không, ta dùng vòng for biến i duyệt các phần tử từ 0 đến l/2. Với mỗi i ta so sánh S[i] với S[l-i-1], khi gặp cặp ký tự này khác nhau, thì return 0, nếu hết vòng for không gặp cặp ký tự nào khác nhau thì return 1.

Đọc số nguyên n (lưu ý sau khi đọc n phải có lệnh xuống dòng)

Lần lượt đọc mỗi dòng trong n dòng vào xâu s rồi ghi kết quả KTDX(s)

vào tệp kết quả.

Bài 6. Xâu con chung dài nhất (Đề thi HSG tỉnh lớp 12 năm học 2012 – 2013)

Xâu S được gọi là xâu con chung của xâu S1 và xâu S2 nếu xâu S là một

dãy các ký tự liên tiếp trong S1 và cũng là dãy các ký tự liên tiếp trong S2.

Yêu cầu: Cho hai xâu kí tự S1 và S2 (có không quá 255 ký tự). Hãy tìm một xâu con chung S dài nhất của hai xâu S1 và S2. Ví dụ: S1 = ‘Ky thi học sinh gioi Tinh môn Tin hoc’, S2 = ’hoc sinh gioi mon Tin hoc’ thì S =‘hoc sinh gioi '.

Dữ liệu vào từ file văn bản Bai2.inp:

Dòng đầu tiên ghi xâu S1;

Dòng thứ hai ghi xâu S2.

Kết quả ghi ra file văn bản Bai2.out: Chỉ một số duy nhất là độ dài của xâu con chung dài nhất S. (Nếu hai xâu S1, S2 không có kí tự nào chung thì ghi số 0).

Ví dụ:

Bai2.inp 14

Bai2.inp Ky thi hoc sinh gioi Tinh mon tin hoc hoc sinh gioi mon Tin hoc

35

Gợi ý: Đây là bài toán tìm xâu con dài nhất của một xâu trong xâu còn lại. Ta sẽ sử dụng cách duyệt theo phương pháp kiểm tra độ dài để kiểm tra sự xuất hiện của xâu con ở xâu ngắn hơn trong xâu còn lại

Bài 7: Chuẩn hóa văn bản:

Một văn bản được gọi là văn bản chuẩn nếu:

- Hai từ liền nhau có duy nhất một dấu cách trống.

- Dấu ngắt câu (dấu chấm, dấu phẩy, dấu chấm phẩy, dấu chấm hỏi, dấu

chấm than) được đặt sát vào từ ngay trước nó, sau đó mới đến dấu cách trống.

- Dấu mở ngoặc đặt sát vào phía bên trái của từ bắt đầu mở ngoặc.

- Dấu đóng ngoặc đặt sát bên phải từ cuối cùng được đóng ngoặc.

Hãy viết chương trình nhập vào 1 xâu văn bản, đưa ra xâu đó ở dạng văn

bản chuẩn.

Gợi ý:

- Xóa các dấu cách thừa: thực hiện như bài tập 2 của mục 2.2.1 hoặc có

thể dùng lệnh for lùi duyệt để tìm và xóa.

- Xử lý với các dấu câu:

+ Dùng xâu phụ để chứa các dấu câu: s1=".,;?!)";

+ Duyệt từng ký tự i của xâu s:

+/ Nếu s[i] có mặt trong xâu s1 thì xóa dấu cách phía trước nếu có và

thêm dấu cách phía sau nếu chưa có.

+/ Nếu s[i] là dấu ngoặc mở thì xóa dấu cách phía sau nếu có và thêm dấu

cách phía trước nếu chưa có.

Bài 8. ĐOẠN MAX (Đề thi HSG tỉnh lớp 12 năm học 2013 – 2014)

Cho chuỗi kí tự S gồm toàn các chữ cái in hoa (A…Z) với độ dài không

vượt quá 104.

Yêu cầu: Hãy tìm đoạn con các kí tự liên tiếp dài nhất sao cho không có kí tự nào xuất hiện nhiều hơn một lần. Trong trường hợp có nhiều hơn một đoạn con có cùng chiều dài dài nhất, hãy chỉ ra đoạn xuất hiện đầu tiên trong chuỗi S.

Dữ liệu: Vào từ văn bản DOANMAX.INP:

- Gồm một dòng duy nhất chứa chuỗi S.

Kết quả: Ghi ra file văn bản DOANMAX.OUT

- Chỉ một dòng duy nhất chứa số nguyên P và L tương ứng là vị trí và

chiều dài của đoạn con dài nhất tìm được.

Ví dụ:

DOANMAX.INP DOANMAX.OUT

36

ABABCDAC 3 4

Gợi ý:

Với bài toán này ta sử dụng phương pháp kiểm tra theo độ dài.

Vì đoạn con yêu cầu các ký tự xuất hiện không lớn hơn một lần nên ta chỉ

cần kiểm tra các xâu có độ độ dài từ 26 trở xuống.

Để kiểm tra tính duy nhất của mỗi ký tự trong dãy con, ta xây dựng hàm KT(i,j) trả về giá trị True khi mỗi ký tự trong đoạn i,j là duy nhất. Ta có thể sử dụng mảng đánh dấu với chỉ số tương ứng từ A-Z để phát hiện một ký tự trong đoạn con đã xuất hiện để trả nhanh về giá trị false.

Bài 9: Quản lý thi:

Trong công tác tổ chức các kỳ thi, để đảm bảo tính khách quan, công bằng cho các thí sinh, một công đoạn hết sức quan trọng là lập danh sách dự thi và đánh số báo danh. Để đánh số báo danh, danh sách thí sinh phải được sắp xếp với tên theo bảng chữ cái.

Em hãy viết chương trình giúp cán bộ làm công tác thi sắp xếp danh sách

thí sinh theo bảng chữ cái.

Dữ liệu: Vào từ file văn bản THISINH.INP, gồm:

- Dòng đầu tiên ghi một số nguyên N.

- N dòng tiếp theo mỗi dòng ghi một xâu là họ và tên của thí sinh.

Kết quả: Ghi ra file văn bản THISINH.OUT: gồm N dòng, mỗi dòng ghi

họ tên của một thí theo thứ tự tên đã được sắp xếp theo bảng chữ cái.

Giới hạn: 0 < N < 30000;

Ví dụ:

THISINH.INP THISINH.OUT

3 Tran Thi An

Hoang Thi Hoa Hoang Thi Hoa

Nguyen Van Thuy Nguyen Van Thuy

Tran Thi An

Gợi ý:

- Dùng mảng hoten dùng để lưu danh sách thí sinh: hoten[i] ghi họ và tên

thí sinh i.

- Với mỗi thí sinh i, tách lấy phần tên lưu vào mảng: ten[i].

- Sắp xếp mảng tên theo thứ tự tăng dần, với mỗi lượt tráo đổi 2 phần tử

trong mảng tên thì tráo đổi luôn 2 phần tử tương ứng trong mảng hoten.

37

- Xuất ra kết quả là danh sách thí sinh trong mảng hoten sau khi sắp xếp.

Bài 10. SỐ ĐƠN ĐIỆU

(Đề thi HSG tỉnh lớp 11 năm học 2013 – 2014)

Số a1, a2, …, an được gọi là số đơn điệu nếu ai < ai+1 > ai+2 hoặc ai > Số có một chữ số; số có hai chữ số khác nhau cũng i=

ai+1 < ai+2 ( được gọi là số đơn điệu lần lượt có độ dài bằng 1; 2.

Ví dụ: Các số 5, 58, 3748, 32435465768 là số đơn điệu vì:

Số 5 có 1 chữ số

Số 58 có 2 chữ số khác nhau.

Số 3748 có: 3 < 7 > 4 < 8

Số 32435465768 ta thấy: 3 > 2 < 4 > 3 < 5> 4 < 6 > 5 < 7 > 6 < 8

Yêu cầu: Viết chương trình xác định số chữ số lớn nhất tạo thành số đơn điệu của một số cho trước.

Dữ liệu:

Vào từ file văn bản SDD.INP: Gồm một số nguyên dương N có không

quá 75 chữ số.

Kết quả:

Ghi ra file văn bản SDD.OUT: Chứa số nguyên là số chữ số lớn nhất tạo

thành đoạn số đơn điệu của số N.

Ví dụ:

SDD.INP SDD.OUT

3748 4

Gợi ý:

Số nguyên N có thể có 75 chữ số nên ta không thể xử lý bằng kiểu dữ liệu số. Ta sẽ đọc số nguyên N vào 1 xâu ký tự và xử lý theo các thao tác xử lý xâu. Ta đưa bài toán về dạng tìm xâu con dài nhất của xâu tạo thành dãy đơn điệu (các ký tự trong dãy tăng, giảm đan xen). Ta có thể biểu diễn diễn tính đơn điệu của một phần tử s[i] bằng biểu thức s[i]-s[i-1]*s[i]-s[i+1] <0.

Khi đó yêu cầu của bài toán trở thành tìm độ dài k của xâu con dài nhất chứa mà mọi phần tử i trong xâu con đều thỏa mãn s[i]-s[i-1]*s[i]-s[i+1] <0 và lúc đó kết quả cần in ra là k+2.

38

Bài toán yêu cầu tìm xâu con dài nhất nhưng xâu đơn điệu có tính chất: mọi xâu con của xâu đơn điệu đều đơn điệu nên ta sử dụng phương pháp phát triển xâu con sẽ tốt hơn phương pháp kiểm tra theo độ dài.

Bài 11. CENSOR (Đề thi HSG tỉnh lớp 11 năm học 2015 – 2016)

Cho một xâu S có độ dài tối đa là 106 ký tự. Trong xâu S người ta loại bỏ sự xuất hiện của một xâu con T có độ dài ≤ 100 ký tự. Để làm điều này, người ta tìm sự xuất hiện của T lần đầu tiên trong S và xóa nó. Sau đó cứ lặp đi lặp lại quá trình này cho đến khi không còn sự xuất hiện của T trong S. Lưu ý rằng việc xóa một lần xuất hiện có thể tạo ra một sự xuất hiện mới của T chưa từng tồn tại trước đó. Hãy xác định nội dung cuối cùng của xâu S.

Dữ liệu: Vào từ file văn bản CENSOR.INP:

Dòng đầu tiên chứa xâu S.

Dòng thứ hai chứa xâu T. Chiều dài của xâu T bé hơn chiều dài của S, và

tất cả các kí tự của S và T đều là ký tự thường (trong phạm vi từ a..z).

Kết quả: Ghi ra file văn bản CENSOR.OUT chỉ một dòng chứa xâu S sau khi đã xóa bỏ hết T. Đảm bảo rằng S sẽ không trở nên xâu rỗng trong quá trình xóa.

Ví dụ

CENSOR.OUT whatthefun

CENSOR.INP whatthemomooofun moo

Gợi ý:

Ta nếu ta sử dụng lệnh find() kết hợp câu lệnh while để tìm các xâu T trong xâu S rồi xóa thì kết quả vẫn đúng nhưng sẽ không đảm bảo được thời gian nên ta sẽ dùng cách sau:

- Dùng thêm biến X để chứa kết quả, ban đầu X là xâu rổng; biến ls,lt, lx

lần lượt lưu độ dài của xâu S, T, X.

- Lần lượt duyệt từng ký tự S[i] của xâu S:

+ Nối S[i] vào X, nếu lx>=lt thì sao chép lt ký tự cuối của xâu x và biến tg.

+ Nếu tg = T thì xóa trong lt ký tự cuối của xâu X.

- Sau khi duyệt hết các ký tự của xâu S thì xâu X chứa kết quả cần tìm.

Bài 12. ITOA - Chuyển số thành xâu.

(http://thptchuyen.ntucoder.net/Problem/Details/7011)

Viết chương trình nhập vào các cặp số (a,b). Tính tổng a+b và ghép chúng

thành một xâu ký tự. Kiểm tra xem xâu ký tự đó có đối xứng hay không?

39

Dữ liệu nhập: - Dòng 1 ghi n là số cặp (ai,bi) (n<=109) ; - n dòng kế tiếp ghi 2 số nguyên a,b (0

Dữ liệu xuất: - Ghi YES nếu xâu biểu diễn cuối cùng là đối xứng, ghi NO nếu xâu

không đối xứng

Ví dụ

2

output input

12 12 21 21

yes

Với n=2 ta có 2 cặp (a,b) có tổng tương ứng là: 12+12=24 và 21+21=42.

Ta ghép lại thành một xâu 2442 là một xâu đối xứng.

Gợi ý:

- Xây dựng hàm KTĐX(string s) đưa vào xâu s, lấy ra giá trị true nếu xâu

đó đối xứng, giá trị false nếu xâu không đối xứng.

- Đọc số lượng dòng vào n, đọc từng dòng vào cặp số vào a, b; tính tổng a,b sau đó chuyển tổng sang dạng xâu rồi nối vào kết quả. Gọi hàm KTĐX trên xâu kq để ghi đáp án.

Bài 13. RADIO(Đề thi HSG tỉnh lớp 11 năm học 2015 – 2016)

Một đài phát thanh cần phát một thông tin quan trọng tới người dân. Để chắc chắn mọi người đều nghe được thông tin nên đài sẽ phát đi phát lại thông tin đó nhiều lần. Cho một chuỗi các ký tự mà một người dân nghe được. Hãy xác định chuỗi ngắn nhất các ký tự mà có thể là thông tin cần phát. Chính xác hơn là hãy xác định chuỗi S’ từ chuỗi S đã cho sao cho S có trong chuỗi lặp lại S’+S’+…..+S’.

Dữ liệu: Vào từ file RADIO.INP Dòng đầu chứa một số nguyên L là độ dài chuỗi S. (1 < L < 1000000) Dòng thứ 2 chứa đúng L ký tự của chuỗi S. S chỉ chứa các ký tự từ a..z. Kết quả: Ghi ra file RADIO.OUT Độ dài L’ của xâu S’. Lưu ý L’ phải nhỏ nhất có thể. Ví dụ:

RADIO.INP RADIO.OUT

3

8 cabcabca

Giải thích test: Các thông tin có thể là abc, cab, abcabc, thông tin ngắn

nhất là 3 ký tự.

40

Hạn chế: Có 60% test có L < 100.

Gợi ý: Gọi l1 là độ dài của xâu S’ thỏa mãn điều kiện.

Ta duyệt l1 lần lượt từ 1 đến L (độ dài từ nhỏ đến lớn) nếu gặp trường họp

thỏa mãn thì ta dừng việc duyệt và khi đó l1 là kết quả cần tìm.

Để kiểm tra độ dài l1 có thỏa mãn hay k, ta kiểm tra các cặp ký tự cách nhau l1 đơn vị, nếu chỉ cần phát hiện 1 cặp khác nhau thì nó đã không thỏa mãn.

Bài 14: ĐẾM TỪ (Đề thi HSG tỉnh lớp 11 năm học 2019 – 2020)

Bessie đã gặp một dòng văn bản hấp dẫn được khắc vào một tảng đá lớn ở giữa vùng chăn thả bò yêu thích của cô. Ý nghĩa của dòng văn bản dường như là từ một ngôn ngữ cổ xưa bí ẩn liên quan đến một bảng chữ cái chỉ gồm ba ký tự C, O, và W. Mặc dù Bessie không thể giải mã văn bản nhưng COW là mẫu từ yêu thích của cô, và cô tự hỏi có bao nhiêu lần COW xuất hiện trong dòng văn bản.

Bessie không phiền lòng nếu có những kí tự khác xen kẽ trong COW, miễn rằng các kí tự xuất hiện theo thứ tự đúng là C, O, W. Cô cũng không ngại nếu các lần xuất hiện khác nhau của COW có chung một số chữ cái. Ví dụ, COW xuất hiện một lần trong CWOW, hai lần trong CCOW, và tám lần trong CCOOWW.

Bạn hãy vui lòng giúp Bessie đếm xem có bao nhiêu lần COW xuất hiện

trong dòng văn bản đã gặp.

Dữ liệu: Vào từ file văn bản COW.INP: Dòng đầu tiên gồm một số nguyên duy nhất N ≤ 105. Dòng thứ hai chứa một chuỗi gồm N ký tự C, O, hay W. Kết quả: Ghi ra file văn bản COW.OUT chỉ một số nguyên duy nhất là số lần COW xuất hiện như một dãy con (các kí tự không nhất thiết phải liên tục) trong chuỗi input.

Lưu ý rằng các kết quả có thể rất lớn, vì vậy để chắc chắn hãy sử dụng số

nguyên 64 bit để làm các phép tính của bạn.

Ví dụ:

COW.INP 6 COOWWW COW.OUT 6

Hạn chế: Có 50% số test có N < 255.

Gợi ý: - Dùng: + Biến slC để lưu số lượng ký tự C tính từ đầu đến vị trí đang xét.

+ Biến slCO để lưu số lượng cách ghép thành cặp ký tự CO tính từ đầu

đến vị trí đang xét.

+ Biến kq để lưu số lượng cách ghép các ký tự thành COW tính từ đầu

41

đến vị trí đang xét.

- Duyệt các ký tự trong xâu từ trái sang phải:

+ Nếu gặp ký tự C ta tăng slC lên 1.

+ Nếu gặp ký tự O: Thì ta lấy các ký tự C ghép với ký tự O này ta có thêm

slC cách ghép, vậy slCO = slCO + slC;

+ Nếu gặp ký tự W: Thì ta lấy các cặp ký tự CO phía trước ghép với ký tự

W này ta có thêm slCO cách ghép, vậy kq = kq + slCO.

Như vậy, khi duyệt xong đáp số của bài toán được lưu trong biến kq.

Bài 15. Mật Khẩu (http://vinhdinhcoder.net/Problem/Details/4783)

Một xâu ký tự được gọi là mật khẩu “an toàn” nếu xâu có độ dài ít nhất

bằng 6 và chứa ít nhất một chữ cái in hoa, một chữ cái thường, một chữ số.

Ví dụ, ‘a1B2C3’, ‘tinHoc6’ là hai mật khẩu “an toàn”. Còn ‘a1B2C’,

’a1b2c3’, ‘A1B2C3’, ‘tinHoc’ đều không phải là mật khẩu “an toàn”.

Một lần, Sắn nhìn thấy một xâu S, chỉ gồm các loại ký tự: chữ cái in hoa, chữ cái thường và chữ số. Sắn muốn tự kiểm tra khả năng đoán nhận mật khẩu bằng cách đếm xem có bao nhiêu cặp chỉ số (i, j) thỏa mãn điều kiện: 1 ≤ i < j ≤ length(S) và xâu con gồm các ký tự liên tiếp từ i đến j của S là mật khẩu “an toàn”.

Cho xâu S, các bạn hãy tính số lượng cặp chỉ số (i, j) thỏa mãn điều kiện

nêu trên.

Dữ liệu nhập: - Một dòng chứa xâu S có độ dài không quá 106. Kết quả: - In ra một số nguyên duy nhất là số cặp chỉ số (i, j) tìm được. Ví dụ:

Input OutPut

abc3456789PQ abc123 6 0

Gợi ý:

- Dùng biến c1,c2,c3 để đánh dấu sử có mặt lần lượt các loại ký tự hoa,

thường, số; các biến =0 nếu k có mặt, bằng 1 nếu có mặt loại ký tự này.

- Xây dựng hàm KTMK(long i,j) đưa vào xâu con từ I đến j, lấy ra giá trị

true nếu nó thỏa mãn mật khẩu, false nếu k phải là mật khẩu.

42

- Duyệt xét các xâu con để tính số lượng xâu thỏa mãn. Lưu ý nếu đoạn từ j đến j thỏa mãn thì mọi đoạn con phủ đoạn từ i đến j đều thỏa mãn, ta dùng công thức để tích số cách chọn, sau đó bỏ qua các đoạn con đã được tính, rồi duyệt các chỉ số đầu tiếp theo…

IV - HIỆU QUẢ CỦA SÁNG KIẾN.

Sau khi áp dụng đề tài rèn luyện kỹ năng lập trình về chủ đề xâu ký tự trên đối tượng học sinh khá giỏi, đã thu được một số kết quả tích cực, đáng ghi nhận sau:

* Kết quả khảo sát, thực nghiệm tại đơn vị:

Tiến hành khảo sát kỹ năng giải quyết các bài tập chủ đề xâu dữ liệu qua quá trình giảng dạy và các bài kiểm tra có 88% học sinh giải được 95% bài tập mức độ dễ; 86% học sinh giải được 90% bài tập mức độ trung bình; 76% học sinh giải được 70% bài tập mức độ khó;

Khảo sát mức độ hứng thú, yêu thích môn học, mong muốn theo ngành CNTT qua việc lấy ý kiến trước và sau khi áp dụng đề tài. Có 89% học sinh yêu thích lập trình; 72% học sinh được hỏi có mong muốn học tập lâu dài và theo đuổi ngành công nghệ thông tin;

Qua khảo sát cho thấy việc áp dụng đề tài vào dạy học rất là cần thiết.

* Đối với học sinh đã có sự tiến bộ rõ rệt về các mặt sau:

+ Năng lực phân tích, nhận dạng và lựa chọn được thuật toán thích hợp để

giải quyết các bài toán về xâu ký tự.

+ Khả năng đánh giá độ phức tạp của thuật toán.

+ Khả năng tư duy thuật toán, phát huy tính sáng tạo.

+ Năng lực vận dụng các kiến thức đã học vào giải quyết vấn đề.

+ Trình bày thuật toán, diễn đạt chương trình rõ ràng, chuẩn xác.

+ Mức độ yêu thích, say mê học tập với môn học tăng lên rõ rệt, hầu hết các em đều hứng thú và mong muốn được học tập chuyên sâu để làm việc trong ngành CNTT.

43

+ Trong năm học này các em đã có những thành tích đáng tự hào. Trong kỳ thi học sinh giỏi tỉnh khối 12 học sinh của tôi đã đạt giải Nhì và có em học sinh khối 11 đã xây dựng được phần mềm ứng dụng thực tiễn đạt giải Ba trong kỳ thi khoa học kỹ thuật cấp tỉnh.

Phần 3: KẾT LUẬN:

I - KẾT LUẬN CHUNG:

Trong quá trình nghiên cứu các tài liệu về chương trình môn Tin học trong chương trình giáo dục phổ thông 2018 và các tài liệu để nâng cao chuyên môn nghiệp vụ, nghiên cứu về các ngôn ngữ lập trình thích hợp hơn trong chương trình mới với hai định hướng chính là STEM và Algorithm với NNLT C++ và Python, tôi đã chú trọng nghiên cứu chủ đề Xâu ký tự và hiệu quả dạy học chủ đề xâu ký tự trên đối tượng học sinh khá giỏi ở trường THPT.

Kể từ năm học 2019 - 2020 tôi đã sưu tầm, đọc tài liệu tham khảo, nghiên cứu các văn bản liên quan đến các vấn đề của đề tài này. Điều tra, khảo sát về thực trạng và chất lượng dạy học bộ môn Tin học trong giai đoạn vừa qua đã làm nảy sinh Sáng kiến này.

- Tôi hoàn thành nội dung đề tài, báo cáo thành chuyên đề trong các lần họp tổ chuyên môn để cùng đồng nghiệp bổ sung những thiếu sót của đề tài. Giao lưu học hỏi, trao đổi kinh nghiệm với các đồng môn ở các trường bạn.

- Thực nghiệm dạy học, hướng dẫn học sinh nghiêm túc nghiên cứu và thực hiện đề tài nhằm nâng cao khả năng vận dụng kiến thức bộ môn vào giải quyết bài toán thực tiễn.

- Đề tài đã được áp dụng vào việc dạy học trong bồi dưỡng học sinh khá giỏi và trong sinh hoạt Câu lạc bộ Tin học ở trường chúng tôi. Trong quá trình thực nghiệm sư phạm chúng tôi đã quan sát, thống kê, phân tích, tổng hợp, so sánh, đối chiếu, đánh giá về hiệu quả của đề tài và tiếp tục bổ sung, hoàn thiện.

II- Ý NGHĨA CỦA ĐỀ TÀI

- Với bản thân nghiên cứu đề tài sáng kiến kinh nghiệm là việc làm tốt để nghiên cứu khoa học làm quen với phương pháp làm khoa học tuy chỉ trong phạm vi hẹp nhưng với nỗ lực của bản thân và sự giúp đỡ của đồng nghiệp đã có những đề tài khoa học tốt, lý thú và hiệu quả.

- Đề tài có thể làm tài tiệu tham khảo hữu ích đối với các đồng nghiệp trong việc thực hiện chương trình giáo dục phổ thông mới, góp phần nâng cao chất lượng, hiệu quả công tác giảng dạy môn Tin học.

- Nội dung đề tài có thể làm tài liệu tham khảo quý cho học sinh các trường Trung học phổ thông, góp phần nâng cao kiến thức, kỹ năng giải các bài tập. Tạo niềm đam mê môn học cũng như yêu thích ngành Công nghệ thông tin.

44

- Cũng qua đề tài, tôi muốn cùng đồng nghiệp trao đổi, trau dồi chuyên môn nhằm góp phần nâng cao trình độ chuyên môn nghiệp vụ và khả năng mở rộng kiến thức.

III – PHẠM VI ỨNG DỤNG, MỞ RỘNG CỦA ĐỀ TÀI:

- Sáng kiến này có thể áp dụng để dạy học cho đối tượng học sinh yêu thích, học sinh khá, giỏi bộ môn tin học, giáo viên Tin học không chỉ ở trường tôi trong những năm học tới mà có thể ứng dụng ở bất cứ địa phương nào, ngôi trường nào.

- Đề tài có thể ứng dụng vào giải quyết các bài toán thực tiễn, có thể phát

triển, mở rộng đề tài để giải quyết các bài toán phức tạp hơn.

- Có thể áp dụng tư tưởng, cách thức, phương pháp của đề tài vào các

phần nội dung khác, chủ đề khác của chương trình Tin học.

IV – ĐỀ XUẤT:

* Đối với tư tưởng suy nghĩ của giáo viên và học sinh:

- Giáo viên cần tích cực xây dựng nội dung khoa học, lựa chọn phương

pháp phù hợp, tạo sự hứng thú, tạo động cơ học tập cho học sinh.

- Tăng cường trao đổi học tập kinh nghiệm lẫn nhau, tích cực đổi mới phương pháp, kỹ thuật dạy học, vận dụng kiến thức bộ môn để giải quyết các vấn đề của thực tiễn cuộc sống.

- Đối với tổ bộ môn phải nhận thấy được kiến thức chủ đề Xâu dữ liệu đặc biệt quan trọng và tính ứng dụng thực tiễn rất cao cần đầu tư thời gian chú trọng hơn vào chủ đề này.

* Đối với các tổ chức quản lí chỉ đạo.

- Các nhà trường cần chỉ đạo loại bỏ NNLT Pascal , triển khai đưa NNLT

C++ và Python vào dạy học.

- Tạo điều kiện để giáo viên được giao lưu với các đơn vị trên địa bàn

thông qua các cuộc hội thảo chuyên đề.

- Chỉ đạo các giáo viên tích cực nghiên cứu, đổi mới dạy học, nâng cao

trình độ chuyên môn, nghiệp vụ.

- Cần giới thiệu, triển khai, mở rộng ứng dụng các sáng kiến.

Lời cảm ơn: Đề tài của tôi hoàn thành nhờ vào sự giúp đỡ của các bạn bè và đồng nghiệp. Tôi xin chân thành cám ơn thầy cô, các bạn bè đồng nghiệp và các em học sinh đã giúp tôi hoàn thành sáng kiến này. Rất mong được sự đóng góp, tham gia ý kiến để khắc phục những khuyết điểm và hạn chế để đề tài của tôi được hoàn thiện và thực sự hữu ích hơn.

Nghệ An, ngày 15 tháng 03 năm 2021

45

Tác giả đề tài

TÀI LIỆU THAM KHẢO

1. Bộ Giáo dục và Đào tạo, Chương trình giáo dục phổ thông môn Tin học

2018. Thông tư số 32/2018/TT-BGDĐT, Hà Nội.

2. Hồ Sỹ Đàm, Sách giáo khoa Tin học 10 (2011). Nhà xuất bản giáo dục,

Hà Nội.

3. Hồ Sỹ Đàm, Sách giáo khoa Tin học 11 (2011). Nhà xuất bản giáo dục,

Hà Nội.

4. Hồ Sỹ Đàm, Sách bài tập Tin học 11 (2011). Nhà xuất bản giáo dục,

Hà Nội

5. Bùi Việt Hà, Python cơ bản, Nhà xuất bản Đại Học Quốc Gia Hà Nội 6.

6. Bùi Việt Hà – Bùi Vũ Huy, Lời giải bài tập Python cơ bản, Nhà xuất

bản Đại Học Quốc Gia Hà Nội

7. Một số tài liệu, trang mạng liên quan:

46

http://laptrinhphothong.vn/; http://thptchuyen.ntucoder.net/; http://vinhdinhcoder.net/; https://vnoi.info/problems/list/; http://ntucoder.net/; …..