Sáng kiến kinh nghiệm THPT: Ứng dụng lớp bài toán kiểu dữ liệu danh sách trong bồi dưỡng học sinh giỏi

SỞ GIÁO DỤC VÀ ĐÀO TẠO NGHỆ AN

Đề tài:

ỨNG DỤNG ỚP ÀI TOÁN IỂU D IỆU DANH SÁCH T ONG

ỒI D ỠNG H C SINH GI I

: Tin học : Toán Tin

ĩnh vực Tổ

Nghệ An - 2024

SỞ GIÁO DỤC VÀ ĐÀO TẠO NGHỆ AN

T ỜNG THPT THÁI HOÀ

Đề tài:

ỨNG DỤNG ỚP ÀI TOÁN IỂU D IỆU DANH SÁCH T ONG

ỒI D ỠNG H C SINH GI I

ĩnh vực Tên tác giả Tổ Điện thoại

: Tin học : Châu Đức Vinh : Toán Tin : 0942 910 226

Nghệ An - 2024

ỤC ỤC

PHẦN I. ĐẶT VẤN ĐỀ .......................................................................................... 2 1. ý do chọn đề tài. ............................................................................................. 2 2. ục đích nghiên cứu. ...................................................................................... 3 3. Nhiệm vụ và phạm vi nghiên cứu. .................................................................. 3 3.1. Nhiệm vụ nghiên cứu: ................................................................................. 3 3.2. Phạm vi nghiên cứu. .................................................................................... 3 4. Đối tượng nghiên cứu ...................................................................................... 3 5. Phương pháp nghiên cứu. ............................................................................... 3 5.1. Nhóm phương pháp nghiên cứu lý luận ...................................................... 3 5.2. Nhóm phương pháp nghiên cứu thực tiễn ................................................... 4 5.3. Phương pháp thực nghiệm ........................................................................... 4 6. Tính mới và đóng góp của đề tài .................................................................... 4 PHẦN II. NỘI DUNG ............................................................................................. 4 1. Cơ sở lý luận ..................................................................................................... 4 1.1. Lý luận về chương trình phổ thông mới ...................................................... 4 1.2. Lý luận dạy học về dạy học lập trình Python .............................................. 5 2. Cơ sở thực tiễn ................................................................................................. 6 Thực trạng chung:............................................................................................... 6 3. Giải pháp thực hiện ......................................................................................... 7 3.1. Một số kiến thức cơ bản về kiểu dữ liệu danh sách .................................... 7 a. Khởi tạo danh sách ( list) ................................................................................ 7 b. Nhập dữ liệu từ bàn phím vào list .................................................................. 8 3.2. Sự giống và khác nhau kiểu dữ liệu danh sách trong Python và kiểu mảng trong C++. ........................................................................................................ 10 3.3. Các dạng bài toán ...................................................................................... 11 3.4. Lớp các bài tập về kiểu dữ liệu danh sách ................................................ 13 4. hảo sát sự cấp thiết và tính khả thi của giải pháp đề xuất ...................... 27 4.1. Mục đích khảo sát...................................................................................... 27 4.2. Nội dung và phương pháp khảo sát ........................................................... 28 4.3. Đối tượng khảo sát .................................................................................... 28 4.4. Kết quả khảo sát về tính cấp thiết và tính khả thi của các giải pháp đã đề xuất ................................................................................................................... 29 5. ết quả đạt được ............................................................................................ 33 5.1. Đối với học sinh ........................................................................................ 33 5.2. Đối với giáo viên ....................................................................................... 33 5.3. Khả năng mang lại lợi ích thiết thực của sáng kiến .................................. 33 PHẦN 3: ẾT UẬN ........................................................................................... 33 1. ết luận ........................................................................................................... 33 2. Đề xuất phạm vi ............................................................................................. 34 TÀI IỆU THA HẢO .................................................................................... 34

1

PHẦN I. ĐẶT VẤN ĐỀ

1. Lý do chọn đề tài.

Bồi dưỡng học sinh giỏi luôn là một trong những mối quan tâm hàng đầu của

các trường trung học sơ sở cũng như trung học phổ thông.

Đối với môn tin học chương trình phổ thông 2018 sách giáo khoa viết về lập trình bậc phổ thông sử dụng ngôn ngữ lập trình Python. Tuy nhiên mấy năm nay trong công tác bồi dưỡng học sinh giỏi hầu hết tất cả các trường đều giải quyết các bài toán lập trình bằng ngôn ngữ C++, do ngôn ngữ này có rất nhiều điểm mạnh từ kiểu dữ liệu, thư viện hàm có sẵn và tốc độ xử lý phù hợp đáp ứng trong thi học sinh giỏi tỉnh.

Chương trình giáo dục phổ thông mới 2018 có nhiều sự thay đổi về nội dung cũng như phương pháp dạy học. Nhưng sự thay đ i nhất phải nói đến môn tin học. Môn tin học là môn bắt buộc của bậc tiểu học và bậc trung học cơ sở. Đối bậc trung học phổ thông là giai đoạn giáo dục hướng nghề nghiệp nên ngay từ lớp 10 đã đưa vào Chủ đề F: “Giải quyết vấn đề với sự trợ giúp của máy tính” trong đó có đưa ngôn ngữ lập trình Python để học sinh làm quen với cách lập trình bằng ngôn ngữ này.

Python là ngôn ngữ lập trình bậc cao có rất nhiều ưu điểm trong lập trình cũng như trong xây dựng các thư viện đồ họa. Nó hoàn toàn có thể sử dụng để giải quyết các bài toán khó. Hiện nay, học sinh khối 10, 11 đang học chương trình mới với sách giáo khoa bằng ngôn ngữ Python. Vậy khi các em học lập trình bằng ngôn ngữ Python tham gia học sinh giỏi trường, tỉnh thì các em sẽ giải quyết bài toán lập trình bằng ngôn ngữ nào để cùng thuật toán có thể đảm bảo thời gian chạy 1 giây cho 1 test? Đây luôn là n i lo lắng của nhiều giáo viên.

Trong quá trình giảng dạy chúng tôi luôn cố gắng tìm tòi, học hỏi, đúc rút kinh nghiệm để giúp các học sinh tiếp cận các nội dung một cách dễ dàng hơn, tạo nhiều đam mê cho học sinh. Với sự cố gắng không ngừng nhiều năm qua trong công tác bồi dưỡng học sinh giỏi bản thân đã có những thành tích đáng ghi nhận.

Với nhiều năm nghiên cứu cấu trúc đề thi học sinh giỏi của tỉnh Nghệ An cũng như các tỉnh thành khác, tôi thấy hầu hết trong tất cả các đề thi đều có đến 1 hoặc 2 bài dạng về kiểu danh sách. Với mong muốn giúp học sinh có thêm tài liệu để bồi dưỡng học sinh giỏi với kiểu dữ liệu danh sách trong Python để giải quyết bài toán tối ưu nhất.

Với những lý do trên tôi đã đưa ra đề tài “Ứng dụng lớp bài toán kiểu dữ

2

liệu danh sách trong bồi dưỡng học sinh giỏi”

2. Mục đích nghiên cứu.

- Thứ nhất, tìm ra những điểm mạnh của ngôn ngữ lập trình Python khi giải

quyết bài toán có độ phức tạp O(n)

- Thứ 2, trao đổi cùng với các đồng nghiệp về việc vận dụng ngôn ngữ

Python trong bồi dưỡng học sinh giỏi.

- Thứ 3, giải quyết được lớp bài toán kiểu dữ liệu danh sách bằng ngôn ngữ

lập trình Python một cách tối ưu nhất

- Thứ 4, đề tài có thể làm tài liệu cho giáo viên phục vụ giảng dạy, bồi dưỡng

học sinh giỏi.

3. Nhiệm vụ và phạm vi nghiên cứu.

3.1. Nhiệm vụ nghiên cứu:

- Nghiên cứu ngôn ngữ lập trình Python trong công tác bồi dưỡng học sinh

giỏi

- Đề tài nghiên cứu hệ thống lớp các bài toán dạng kiểu dữ liệu danh sách.

- Giải và đánh giá các bài toán kiểu dữ liệu danh sách trên ngôn ngữ Python

3.2. Phạm vi nghiên cứu.

Đề tài được nghiên cứu trong quá trình dạy đội tuyển học sinh giỏi tỉnh tại trường THPT Thái Hòa.

Đề tài có khả năng áp dụng rộng rãi vào giảng dạy, bồi dưỡng học sinh giỏi

Tin học cho giáo viên và học sinh THCS, THPT trên địa bàn toàn tỉnh Nghệ An.

4. Đối tượng nghiên cứu

- Chương trình giáo dục phổ thông mới.

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

- Cấu trúc đề thi học sinh giỏi tỉnh môn tin tỉnh Nghệ An

- Đối tượng học sinh đội tuyển tin học sinh giỏi trường và tỉnh.

- Kiểu dữ liệu danh sách trong Python.

- Các bài tập vận dụng kiểu dữ liệu danh sách.

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

5.1. Nhóm phương pháp nghiên cứu lý luận

- Nghiên cứu các Nghị quyết của Đảng, Nhà nước, Bộ giáo dục và đào tạo, Sở

giáo dục và đào tạo của tỉnh liên quan đến đề tài nghiên cứu.

- Các tài liệu về lý luận dạy học Tin học, tài liệu hướng dẫn chuyên môn.

3

- Các tài liệu dạy lập trình

5.2. Nhóm phương pháp nghiên cứu thực tiễn

- Phân tích tổng hợp và rút kinh nghiệm từ thực tiễn.

5.3. Phương pháp thực nghiệm

- Thực nghiệm tại các nhóm học sinh giỏi ở trường THPT nơi tôi công tác

giảng dạy.

6. Tính mới và đóng góp của đề tài

- Giúp học sinh tìm hiểu một dạng bài tập kiểu danh sách trong Python, đáp

ứng một phần yêu cầu trong kiến thức luyện thi học sinh giỏi.

- Đánh giá, so sánh kiểu dữ liệu danh sách trong ngôn ngữ lập trình Python

với kiểu dữ liệu mảng trong ngôn ngữ lập trình C++.

- Giúp giáo viên đa dạng hóa về việc áp dụng các dạng dữ liệu tập trong ngôn

ngữ lập trình để giải quyết một bài toán phù hợp với tình hình thực tế hiện nay.

- Nâng cao kiến thức bộ môn, đóng góp một phần nhỏ bé vào việc nâng cao

được chất lượng dạy học bồi dưỡng học sinh giỏi.

- Giúp học sinh đam mê học môn Tin học.

PHẦN II. NỘI DUNG

1. Cơ sở lý luận

1.1. ý luận về chương trình phổ thông mới

Mục tiêu cấp trung học phổ thông: Chương trình môn Tin học ở cấp trung học phổ thông giúp học sinh củng cố và nâng cao năng lực tin học đã được hình thành, phát triển ở giai đoạn giáo dục cơ bản, đồng thời cung cấp cho học sinh tri thức mang tính định hướng nghề nghiệp thuộc lĩnh vực tin học hoặc ứng dụng tin học, cụ thể là:

- Giúp học sinh có những hiểu biết cơ bản về hệ thống máy tính, một số kĩ thuật thiết kế thuật toán, tổ chức dữ liệu và lập trình; củng cố và phát triển hơn nữa cho học sinh tư duy giải quyết vấn đề, khả năng đưa ra ý tưởng và chuyển giao nhiệm vụ cho máy tính thực hiện.

- Giúp học sinh có khả năng ứng dụng tin học, tạo ra sản phẩm số phục vụ cộng đồng và nâng cao hiệu quả công việc; có khả năng lựa chọn, sử dụng, kết nối các thiết bị số, dịch vụ mạng và truyền thông, phần mềm và các tài nguyên số khác.

4

- Giúp học sinh có khả năng hoà nhập và thích ứng được với sự phát triển của xã hội số, ứng dụng công nghệ thông tin và truyền thông trong học và tự học; tìm kiếm và trao đổi thông tin theo cách phù hợp, tuân thủ pháp luật, có đạo đức, ứng xử văn hoá và có trách nhiệm; có hiểu biết thêm một số ngành nghề thuộc lĩnh

vực tin học, chủ động và tự tin trong việc định hướng nghề nghiệp tương lai của bản thân.

1.2. ý luận dạy học về dạy học lập trình Python

- Python là một ngôn ngữ lập trình kịch bản (scripting language) do Guido van Rossum , lập trình viên nổi tiếng người Hà Lan viết, phiên bản đầu tiên được phát hành vào năm 1991.Hiện nay, Python đã phát triển đến các phiên bản 3.x.x. Python là một ngôn ngữ lập trình cấp cao, cực kỳ linh hoạt, chạy trên nhiều nền tảng khác nhau như Windows, Mac OS, Linux, Raspberry Pi, ... Một số tính năng khiến Python trở nên thông dụng bao gồm:

+ Cú pháp Python rất đơn giản chính vì vậy mà nó khá dễ sử dụng. Một số người cho rằng cách tốt nhất để học Python cơ bản là bắt đầu viết luôn chương trình. Hầu hết những cú pháp Python có tính logic cao đủ để giúp bạn bắt đầu viết được luôn chương trình của mình.

+ Hầu hết những nhà lập trình viên cho rằng Python là một ngôn ngữ dễ học

và nó được giảng dạy phổ biến nhất trong các trường học trên toàn thế giới.

Những tính năng trên đã khiến Python trở nên phổ biến trên toàn thế giới.



Nó được sử dụng trong nhiều lĩnh vực khác nhau như:



Phát triển trang web Back-end



Phát triển trò chơi.



Khoa học dữ liệu và phân tích.



Phát triển ứng dụng di động.

Robot và AI (Trí tuệ nhân tạo)

Cùng với một số ưu điểm thì Python có một số hạn chế trong lĩnh vực hiệu

suất. Sau đây là một một số nhược điểm của Python:

+ Tốc độ thực thi chậm: Python là một ngôn ngữ thông dịch, có nghĩa là nó hoạt động với trình thông dịch, không phải với trình biên dịch. Do đó, nó thực thi tương đối chậm hơn C, C++, Java và nhiều ngôn ngữ khác.

+ Tiêu thụ bộ nhớ lớn: Các cấu trúc của Python đòi hỏi nhiều không gian bộ nhớ hơn. Ngôn ngữ này không thích hợp để sử dụng cho sự phát triển trong điều kiện bộ nhớ hạn chế.

5

+ Khó kiểm tra: Vì nó là một ngôn ngữ dựa trên trình thông dịch, rất khó để chạy các bài kiểm tra trên mã được viết bằng Python. Tất cả các l i chỉ xuất hiện trong thời gian chạy, điều này khiến việc kiểm tra các đoạn mã được viết bằng Python rất khó khăn.

2. Cơ sở thực tiễn

Thực trạng chung:

a, Đối với học sinh

Với cấu trúc đề thi học sinh giỏi hướng tới thi tốt nghiệp trung học phổ thông Quốc gia môn tin được sánh vai với các môn học khác khi các em có quyền được lựa chọn môn thi tốt nghiệp. Và theo cấu trúc đề thi minh hoạ của Bộ giáo dục và đào tạo thì các câu hỏi nhiều lựa chọn ở phần I và câu hỏi đúng sai ở phần II. Như vậy khi các em cần nắm vững kiến thức các chủ đề để làm tốt bài thi. Cùng với đó Sở giáo dục đào tạo Nghệ An cũng có dự thảo về phương án cấu trúc đề thi học sinh giỏi tỉnh theo cấu trúc mới gồm 3 phần: Phần I ( Câu hỏi nhiều lựa chọn); phần II ( Lựa chọn đúng/ sai); phần III ( Tự luận). Trong đó bài toán về số và dãy số được ứng dụng nhiều. Vì vậy học sinh cần hiểu rõ được thuật toán đồng thời cần nắm vững cấu trúc của câu lệnh với các kiểu dữ liệu phù hợp. Tuy nhiên đa số học sinh ở cấp THCS biết đến với ngôn ngữ lập trình nâng cao C++. Trong đó dữ liệu cấu trúc bên C++ khác với Python, nhất là dữ liệu kiểu danh sách.

- cấp THCS các em đang học chương trình cũ, một số trường có dạy tin học cho lớp 8 và lớp 9 với ngôn ngữ lập trình Pascal hoặc C++. Tuy nhiên một số trường cơ sở vật chất còn hạn chế lớp 8 và lớp 9 không lựa chọn học môn tin nên các em sẽ không biết đến ngôn ngữ lập trình bậc cao. Học sinh khối 10, 11 học chương trình mới các em đa số đã làm quen với ngôn ngữ Python. Vậy với học sinh đã biết một số ngôn ngữ như Pascal hay C++ khi tiếp cận ngôn ngữ Python các em thường đặt ra câu hỏi là khi giải quyết bài toán ngôn ngữ nay các kiểu dữ liệu cấu trúc này như thế nào có dễ viết, dễ sử dụng. Còn đối với học sinh đội tuyển các em lại băn khoăn trong ngôn ngữ Python có kiểu dữ liệu mảng như trong C++ để giải quyết các bài toán dạng dãy có cùng giá trị. Và trường hợp dãy không có các giá trị cùng kiểu thì sẽ giải quyết thế nào?

- Các em học sinh đều có cách nhìn chung là môn tin lập trình khó. Vừa phải biết ngôn ngữ, vừa phải hiểu bản chất toán học. Đồng thời biết tìm ra thuật toán tối ưu cho bài toán.

b, Đối với giáo viên

- Giáo viên dạy đội tuyển cơ bản đã đầu tư tìm tòi. Tuy nhiên việc tiếp cận

các ngôn ngữ Python của giáo viên cũng chưa nhiều nên gặp khó khăn.

- Dựa vào cấu trúc đề thi học sinh giỏi cấp huyện, cấp tỉnh. Có rất nhiều chuyên đề giáo viên cần bồi dưỡng cho học sinh. Một trong các chuyên đề thường có trong các đề thi học sinh giỏi môn tin là chuyên đề về dãy các giá trị cùng kiểu hoặc khác kiểu. Đó là các lớp bài toán dạng danh sách trong các đề thi.

- Tài liệu về ôn thi đội tuyển thật sự rất khó tìm để phù hợp cả học sinh và

6

giáo viên

Chương trình phổ thông mới đã lựa chọn ngôn ngữ lập trình Python để dạy và học lập trình. Nên giáo viên dạy đã được tiếp cận với ngôn ngữ này. Tuy nhiên giáo viên cơ bản trong quá trình vừa dạy, vừa tìm hiểu ngôn ngữ.

- Kiểu dữ liệu danh sách trong Python gồm các giá trị cùng kiểu dữ liệu và cũng có thể là các giá trị không cùng kiểu. Vì vậy khi xử lý các giá trị khác kiểu dữ liệu khác nhau sẽ có các phép toán khác nhau. Nên sẽ cần nắm rõ các phép toán trong xử lý. Đây là cái khó cho cả giáo viên và học sinh.

- Môn tin học lần đầu tiên thực hiện lựa chọn thi tốt nghiệp và đại học. Nên

cả học sinh, giáo viên còn nhiều bỡ ngỡ chưa có kinh nghiệm.

Muốn đạt kết quả cao trong các kì thi học sinh giỏi tỉnh và cấp huyện thì giáo viên ngoài cần phải trang bị đầy đủ, chi tiết kiến thức phần lí thuyết cho tất cả các chủ đề. Còn phải biết vận dụng cao để giải quyết bài toán thực tiễn ở phần tự luận. Do đó giáo viên cần đưa ra các bài tập phù hợp để cũng cố, trang bị kiến thức, cũng như nâng cao kĩ năng vận dụng trong những bài cụ thể. Nhất là tìm ra được những lợi thế của ngôn ngữ Python lựa chọn để dạy đội tuyển.

3. Giải pháp thực hiện

3.1. ột số kiến thức cơ bản về kiểu dữ liệu danh sách

3.1.1.Kiểu dữ liệu danh sách

- Python cung cấp một số cấu trúc dữ liệu đặc biệt gọi là cấu trúc tuần tự. Đặc thù của loại cấu trúc này là chứa nhiều phần tử, m i phần tử được đánh số thứ tự để dễ truy xuất.

- Danh sách là một trong những kiểu dữ liệu tuần tự được sử dụng phổ biến

nhất của Python.

- Danh sách (list) là một kiểu dữ liệu đa năng trong python có thể chứa một

danh sách các phần tử ( Có thể khác kiểu)

3.1.2. Các thao tác trong kiểu dữ liệu danh sách (list)

a. hởi tạo danh sách ( list)

a.1. Dạng liệt kê:

= [, ,…,]

Ví dụ: Tạo xâu r ng s1

s1 = “”

Tạo xâu s2

s2 = “Viet Nam” . Có s2[0] = “V”, s2[1] = “i”, …., s2[7] = “m”

- Duyệt qua từng phần tử của xâu: s = “Ha Noi Viet Nam”

7

for i in s: print(i,end=“ “)

Xuất ra màn hình dòng chữ: H a N o i V i e t N a m

Lưu ý:

– Hàm len() trả về số phần tử của danh sách

Ví dụ:

A=[1, 2, 3, 4]; B =[]; C=[3, 5, 7, 8]

len(A) = 4, len(B) = 0, len(C) = 4

– Phép toán:

+ Nối danh sách: +

Ví dụ: list = A +C thì list gồm 8 phần tử

+ Nhân bản phần tử: *

Ví dụ: lits1 = A * 3 thì list1 gồm 12 phần tử

a.2. Dạng mô tả (list comprehension):

[ for in ]

ưu ý: ở đây có thể là list, range hoặc str

Ví dụ 1: A = [1, 2, 3, 4]

- Tạo danh sách A gồm 4 phần tử và A[0] = 1, A[1] =2, A[2] = 3, A[3] = 4

Ví dụ 2: D = [x**2 for x in A]

- Tạo danh sách D gồm 4 phần tử, D[0] = 2, D[1] = 4, D[2] = 9, D[3] = 16

Ví dụ 3: s = “2 3 5 8 10”

c = [int(x) for x in s.split()]

-Tạo danh sách c gồm 5 phần tử, có giá trị là 2, 3, 5, 8, 10

Ví dụ 4: d = [x for x in range(0,11,2)]

-Tạo danh sách d gồm 6 phần tử, có giá trị lần lượt là 0, 2, 4, 6, 8, 10

Ví dụ 5: s = "12345"

e = [int(x) for x in s]

Tạo danh sách e gồm 5 phần tử, có giá trị lần lượt là 1, 2, 3, 4, 5

Ví dụ 6: s = “2 3 5 8 10”

d = list(map(int,s.split()))

Tạo danh sách d gồm 5 phần tử, có giá trị là 2, 3, 5, 8, 10

b. Nhập dữ liệu từ bàn phím vào list

8

b.1. Dạng nhập từng phần tử (thường biết trước số phần tử của mảng)

Ví dụ: Nhập dữ liệu vào danh sách số nguyên a gồm có n phần tử từ bàn phím

- Nhập số phần tử của danh sách

n = int(input(“Mời nhập số phần tử: “));

-Khởi tạo danh sách r ng

a = []

- Xuất dòng thông báo

for i in range(0,n):

print(“Phần tử thứ”,i+1,”là:”,end=“ “)

- Lấy giá trị nhập vào và chuyển sang kiểu số nguyên

temp = int(input())

- Thêm phần tử vào vị trí cuối cùng của danh sách

a.append(temp)

b.2. Dạng nhập toàn bộ phần tử của danh sách (thường chưa biết trước số phần tử của danh sách)

Ví dụ: Nhập dữ liệu vào danh sách số nguyên a từ bàn phím (các số cách nhau dấu cách)

a = list(map(int,input(“Mời nhập các phần tử của danh sách: ”).split()))

3.1.3. Một số lệnh làm việc kiểu danh sách

Hàm Ý nghĩa Ví dụ

append a.append(<đối tượng>)

Bổ sung <đối tượng> vào cuối của một danh sách

clear a.clear() Xóa dữ liệu, đưa danh sách a thành r ng

copy a.copy()

Trả về một danh sách có giá trị giống a (một bản sao của a)

extend a.extend(<đối tượng>) Mở rộng <đối tượng> vào cuối danh sách a

index a.index()

Trả về chỉ số index đầu tiên trong danh sách của

insert

a.insert(,<đối tượng>) Chèn <đối tượng> vào danh sách ở trước vị trí index

remove a.remove()

9

Xóa đi phần tử đầu tiên có giá trị bằng

reverse a.reverse()

Trả lại danh sách có các phần tử ngược với phần tử a

sort a.sort(reverse=True/False)

Sắp xếp lại danh sách a theo thứ tự giảm, tăng dần giá trị của các phần tử

3.2. Sự giống và khác nhau kiểu dữ liệu danh sách trong Python và kiểu mảng trong C++.

* Giống nhau:

- ưu trữ nhiều phần tử: Cả hai đều được sử dụng để lưu trữ nhiều phần tử trong một cấu trúc dữ liệu duy nhất.

- Truy cập phần tử: Cả hai đều cho phép truy cập vào các phần tử trong danh sách/mảng thông qua chỉ số.

- Phép toán cơ bản: Cả hai h trợ các phép toán cơ bản như thêm, xóa, cập nhật phần tử.

* Khác nhau:

- iểu dữ liệu phần tử:

+ Python: Danh sách trong Python có thể chứa các phần tử với các kiểu dữ liệu khác nhau, kể cả các danh sách khác.

+ C++: Mảng trong C++ thường chỉ chứa các phần tử cùng kiểu dữ liệu. Có thể sử dụng các mảng 2 chiều để mô phỏng cấu trúc dữ liệu tương tự như danh sách trong Python, nhưng nó không phải là mặc định.

- ích thước động:

+ Python: Danh sách trong Python có thể thay đổi kích thước linh hoạt theo nhu cầu mà không cần khai báo trước kích thước.

+ C++: Mảng trong C++ cần phải khai báo kích thước tĩnh hoặc sử dụng các cấu trúc dữ liệu động như std::vector để có thể thay đổi kích thước.

- Điều chỉnh động:

+ Python: Danh sách trong Python h trợ các phương thức như append, remove, pop,... để điều chỉnh nội dung của danh sách một cách linh hoạt.

10

+ C++: Mảng trong C++ thường cần phải triển khai các hàm riêng để thêm, xóa phần tử. Mặc dù có thể sử dụng các cấu trúc dữ liệu như std::vector, nhưng vẫn cần sự can thiệp của thư viện chuẩn.

3.3. Các dạng bài toán

3.3.1. Các bài toán về kiểu dữ liệu danh sách cùng kiểu dữ liệu

- Có rất nhiều bài toán và thuật toán liên quan đến kiểu dữ liệu danh sách (hay còn gọi là mảng, vector) trong lập trình. Dưới đây là một số ví dụ:

Bài toán 1: Cho một dãy số nguyên gồm N phần tử và 1 số nguyên k bất kỳ. Tìm xem trong dãy đó có phần tử nào có giá trị bằng K hay không. Nếu có đưa ra vị trí có giá trị bằng k. Nếu không đưa ra -1.

Hàm linear_search tìm kiếm giá trị k trong mảng arr bằng phương pháp tìm kiếm tuần tự. Nếu tìm thấy, nó trả về chỉ số của phần tử đó. Nếu không tìm thấy, nó trả về -1.

Trong hàm main, chúng ta nhập dãy số nguyên và giá trị k từ người dùng, sau đó gọi hàm linear_search để tìm kiếm giá trị k trong dãy. Kết quả được hiển thị ra màn hình.

Chương trình:

def linear_search(arr, k):

for i in range(len(arr)):

if arr[i] == k:

return i

return -1

arr = list(map(int, input("Nhập dãy số nguyên, cách nhau bởi dấu cách: ").split()))

k = int(input("Nhập giá trị k cần tìm: "))

result = linear_search(arr, k)

if result != -1:

print(f"Phần tử {k} được tìm thấy tại vị trí {result}.")

else:

print(f"Phần tử {k} không được tìm thấy trong dãy.")

Bài toán 2: Viết chương trình nhập vào từ bàn phím danh sách số nguyên a; đếm và đưa ra màn hình số lượng phần tử lớn hơn phần tử đứng ngay trước và phần tử đứng ngay sau nó.

print(" Nhập một dãy số nguyên:")

a=[int(i) for i in input().split()]

dem=0

11

for i in range(1, len(a)-1):

if a[i-1]a[i+1]:

dem=dem+1

print(dem)

Bài toán 3: Có n đôi giày cùng loại chỉ khác nhau về kích thước được xếp thành một hàng thứ tự ngẫu nhiên. Chủ trò bí mật rút một chiếc giày và giấu đi, sau đó yêu cầu người chơi cho biết chiếc giày được giấu là chiếc giày trái hay phải và có số là bao nhiêu?

Ý tưởng: Cách làm thông thường để tìm ra chiếc giày còn thiếu là đi ghép các đôi giày, tuy nhiên cách làm này sẽ mất nhiều thời gian. Một cách làm đơn giản là dựa trên nhận xét: Nếu dãy không thiếu chiếc giày nào thì tổng số bằng 0, nên có thể xác định chiếc giày còn thiếu khi biết tổng các số trong dãy.

print(" Nhập một dãy số size giày:")

a=[int(i) for i in input().split()]

sum=0

for i in range(len(a)):

sum=sum+a[i]

if sum>0:

print(“ chiếc giày bên trai, kich cỡ”, sum)

else:

print(“ Chiếc giày bên phải, kích thước”,sum)

Và rất nhiều bài toán kiểu dữ liệu danh sách như bài toán sắp xếp các phần tử trong danh sách; Phân loại mảng (sort array by parity); chia mảng thành phần tử chẵn và lẻ.; Tìm kiếm số lần xuất hiện; Đếm số lần xuất hiện của một phần tử trong mảng. Bài toán con lớn nhất: ( Tìm dãy con liên tục có tổng lớn nhất (maximum subarray sum); Tìm dãy con không liên tục có tổng lớn nhất). Xóa phần tử trùng lặp; Xoá và chèn phần tử.

3.3.2. Các bài toán về kiểu danh sách khác kiểu dữ liệu

- Danh sách chứa các số nguyên cùng kiểu dữ liệu

a = [1, 2, 3, 4] ; print(a)

- Danh sách chứa các chu i cùng kiểu

b = ['dammio', 'sammi', 'helmi'] ; print(b)

-Danh sách chứa các phần tử có giá trị bất kỳ ( giá trị khác kiểu)

c = ['hello', 1, 100.7] ; print(c)

12

* Ghép các danh sách thành một danh sách

A=[1,2,3,4]

B=[“Hồng”,”Cúc”, “Lan”]

C=A+B

print(C)

Và kết quả danh sách C là: [1,2,3,4, “Hồng”, “ Cúc”, “Lan”]

- Một số bài toán cụ thể:

Bài toán 1: Hãy viết một chương trình Python thực hiện các bước sau:

Khai báo hai tập hợp A và B. Kiểm tra xem hai tập hợp có phần tử chung nào không. Nếu có phần tử chung, hiển thị các phần tử đó.

Chương trình:

A = {1, 2, 3, "Một", 5}

B = {4, 5, 6, 7, "Một"}

common_elements = A & B # hoặc A.intersection(B)

if common_elements:

common_elements_str = ", ".join(map(str, common_elements))

print("Các phần tử chung của hai tập hợp: " + common_elements_str)

else:

print("Không có phần tử chung giữa hai tập hợp.")

Bài toán 2: Hãy viết một chương trình Python thực hiện các bước sau:

Khai báo hai tập hợp set1 và set2 dưới dạng đã cho. Loại bỏ các phần tử không chung giữa hai tập hợp (set1 và set2) khỏi tập hợp set1. In kết quả ra màn hình.

Chương trình:

set1 = {10, 20, "Hà", 40, 50}

set2 = {"Hà", 40, 50, 60, 70}

elements_to_remove = set1 - set2

set1.difference_update(elements_to_remove)

print("Tập hợp set1 sau khi loại bỏ các phần tử không chung:", set1)

3.4. ớp các bài tập về kiểu dữ liệu danh sách

3.4.1. Các bài tập mức độ A (Nhận biết, Thông hiểu)

Bài 1: Viết chương trình nhập n từ bàn phím, tạo và in ra màn hình dãy số A bao gồm n số tự nhiên chẵn đầu tiên.

13

A = []

n = int(input("Nhập số tự nhiên n:"))

if n<1:

n = int(input("Nhập lại số tự nhiên n:"))

for i in range (0,n):

A.append(i*2)

print ("Dãy số A là:", A)

Bài 2: Cho trước dãy số A. Viết chương trình thực hiện công việc sau:

- Xóa đi một phần tử ở chính giữa dãy nếu số phần tử của dãy là số lẻ.

- Xóa đi hai phần tử ở chính giữa của dãy nếu số phần tử là số chẵn.

A = [11, 50, 26, 87, 59]

C = len(A)

if C%2 != 0:

A. remove (A[C//2])

else:

A. remove (A[C//2])

C = C - 1

A. remove(A[C//2])

print (A)

3.4.2. Các bài tập mức độ B ( Vận dụng thấp)

Bài 1: Viết chương trình nhập vào từ bàn phím danh sách số nguyên N. Tính số lượng các số dương liên tiếp nhiều nhất.

print(“ nhập dãy số nguyên:”)

a=[int(i) for i in input().split()]

d=len(a)

i=0

maxd=0

while i

if a[i]>0:

max1=0

j=i

14

while a[j]>0:

max1+=1

j+=1

if j==d: break

if max1>maxd:

maxd=max1

i=j

i+=1

print('So duong lien tiep dai nhat =',maxd)

Bài 2: Viết chương trình Python tính số lượng các số dương liên tiếp có tổng lớn nhất.

print(“ nhập dãy số nguyên:”)

a=[int(i) for i in input().split()]

tong_max = 0

tong1 = 0

for n in a:

if n > 0:

tong1 += n

else:

tong1 = 0

if tong1 > tong_max:

tong_max=tong1

if tong_max == 0:

print("Không tìm thấy đoạn con có các số hạng dương liên tiếp.")

else:

print("Tổng đoạn con dương lớn nhất: ",tong_max)

Bài 3: Viết chương trình Python tính số lượng các phần tử liên tiếp đan dấu nhiều nhất (dãy phần tử liên tiếp được gọi là đan dấu nếu tích hai phần tử liên tiếp âm).

print(“ nhập dãy số nguyên:”)

a=[int(i) for i in input().split()]

d=len(a)

i=0

15

maxdd=0

for i in range(d-1):

max1=0

while a[i]*a[i+1]<0:

max1+=1

i+=1

if i==d-1:break

if max1>maxdd: maxdd=max1

if maxdd>0: maxdd+=1

print('Day so dan dau dai nhat =',maxdd)

Bài 4: Viết chương trình Python tính số lượng các phần tử không tăng nhiều nhất.

count = 1

max_count = 1

for i in range(1, len(a)):

if a[i] <= a[i-1]:

count += 1

max_count = max(max_count, count)

else:

count = 1

print(max_count)

Bài 5: Viết chương trình Python tìm vị trí bắt đầu đoạn con dương liên tiếp có nhiều phần tử nhất.

current_count = 0

max_count = 0

start_index = -1

for i in range(len(a)):

if a[i] > 0:

current_count += 1

if current_count > max_count:

max_count = current_count

start_index = i - max_count + 1

16

else:

current_count = 0

print(start_index)

Bài 6: Viết chương trình Python tìm đoạn con có các số hạng dương liên tiếp có tổng lớn nhất. (Nếu có nhiều đoạn con thoả mãn thì đưa ra màn hình: Số đoạn con thoả mãn và các đoạn con đó).

d=len(a)

i=0

sum_max=0

vtri=[] # danh sách lưu vị trí bắt đầu các đoạn con dương có tổng lớn nhất

while i

if a[i]>0:

sum1=0

j=i

while a[j]>0:

sum1+=a[j]

j+=1

if j==d: break

if sum1>sum_max:

sum_max=sum1

vtri=[i]

elif sum1==sum_max:

vtri.append(i)

i=j

i+=1

if len(vtri)==0:

print('Không có đoạn con dương')

else:

print('Các đoạn con dương có tổng lớn nhất là:')

for i in vtri:

while a[i]>0:

print(a[i],end=' ')

17

i+=1

if i==d:

break

print()

Bài 7: Viết chương trình Python chuyển các phần tử dương của danh sách lên đầu danh sách và in danh sách ra màn hình.

ds_duong = []

ds_am = []

for i in a:

if i >= 0:

ds_duong.append(i)

else:

ds_am.append(i)

ds_moi = ds_duong+ds_am

print(ds_moi)

Bài 8: Viết chương trình Python tìm số phần tử là số nguyên tố của danh sách và vị trí của nó trong danh sách.

def so_nto(n):

if n <= 1:

return False

for i in range(2, n//2+1):

if n % i == 0:

return False

return True

ds_nto = []

for i in a:

if so_nto(i):

ds_nto.append(i)

print("Danh sách số nguyên tố:", ds_nto)

# Tìm vị trí của các số nguyên tố

ds_vtri = []

for i in range(len(a)):

18

if so_nto(a[i]):

ds_vtri.append(i)

print("Vị trí số nguyên tố:", ds_vtri)

* ột số dạng bài tập tương tự

Bài 1: Viết chương trình Python chèn một số m (m nhập vào từ bàn phím ) vào đầu danh sách, cuối danh sách và vị trí thứ 5 của danh sách.

Bài 2: Viết chương trình Python chèn danh sách [1,2,3] vào vị trí đầu, cuối và thứ 5 của danh sách.

Bài 3: Viết chương trình Python xóa phần tử thứ k (k nhập từ bàn phím) trong danh sách.

Bài 4. Viết chương trình Python sắp xếp danh sách theo thứ tự tăng dần, giảm dần.

Bài tập 5: Dãy số Fibonacci được xác định như sau:

F0 = 0; F1 = 1;Fn = Fn−1 + Fn−2 (với n≥2).

Viết chương trình nhập n từ bàn phím, tạo và in ra màn hình dãy số A bao gồm n số hạng đầu của dãy Fibonacci.

3.4.3. Các bài tập mức độ C ( Vận dụng nâng cao)

BÀI 1: HOÁN VỊ SỐ

Trong một cuốn sách cổ có ghi lại rất nhiều các con số bí ẩn mà chúng có mối liên hệ với số 30. Sau một thời gian nghiên cứu, các chuyên gia đã tìm được cách giải mã các số đó: hoán vị các chữ số của số bí ẩn để thu được một bội số lớn nhất của 30.

Yêu cầu: Hãy viết chương trình để giúp các chuyên gia giải mã các số bí ẩn

đó.

Dữ liệu: vào tệp văn bản BAI2.INP Gồm một dòng duy nhất chứa số nguyên dương N, với N có tối đa 107 chữ

số là số cần giải mã.

ết quả: ghi vào tệp vào tệp văn bản BAI2.OUT

tưởng:

Một số chia hết cho 30 khi và chỉ khi có tổng các chữ số chia hết cho 3 và có

số 0 ở cuối cùng.

Với N ban đầu, đặt sum_digit= tổng chữ số của N.

Nếu sum_digit chia hết cho 3 và số N có chứa chữ số 0 thì bài toán có

nghiệm, ngược lại thì vô nghiệm.

Trong trường hợp có nghiệm ta cần sắp xếp các chữ số theo thứ tự lớn đến

19

nhỏ để được một số lớn nhất.

Vì số lượng các chữ số của N có thể lớn đến 107 chữ số ( cần lưu giá trị N dưới dạng xâu ký tự), để tráng việc bị vượt quá thời gian chạy chương trình ta sử dụng phương pháp sắp xếp bằng đếm phân phối.

Chương trình minh họa b ng ngôn ngữ lập trình Python :

fi = open("bai2.inp","r")

fi.readline()

s = s.replace("\n", "")

fi.close()

sum_digit = 0

digit = [0] * 10

for k in s:

sum_digit += ord (k) = 48

digit[ord(k) - 48] += 1

fo = open("bai2.out", "w")

if (sum_digit % 3 != 0 or digit[0] == 0):

fo.write(str(-1))

else:

for i in range (9,-1,-1):

for j in range(1, digit[i]+1):

fo.write(str(i))

fo.close()

ÀI 2: TỔNG ỚC CHUNG ỚN NHẤT CỦA HAI SỐ HẠNG IÊN TIẾP

Cho dãy số nguyên dương gồm N số hạng A1, A2,..., AN. Gọi Ui là ước

chung lớn nhất của Ai và Ai+1 với i=1, 2, ...N-1.

Yêu cầu: Tính tổng U1+U2+...+UN-1.

Dữ liệu cho trong file văn bản UC N.Inp gồm:

• Dòng thứ nhất ghi số nguyên dương N.

• Dòng thứ hai ghi N số nguyên dương A1, A2, ..., AN.

ết quả ghi ra file văn bản UC N.Out một số nguyên là tổng

U1+U2+...+UN-1.

20

tưởng:

Duyệt cặp số hạng liên tiếp, tìm UCLN của m i cặp rồi cộng tổng chúng lại

với nhau.

Chương trình minh họa b ng ngôn ngữ lập trình Python :

import math

fi = open(“ucln.inp”,”r”)

n = int(fi.readline())

a = list(map(int,fi.readline().split()))

fi.close()

sum = 0

for i in range(1,len(a)):

sum+= math.gcd(a[i-1],a[i])

fo = open(“ucln.out”,”w”)

fo.write(str(sum))

fo.close()

ÀI 3: SỐ ĐẶC IỆT

Tùng đang học về số học. Cậu ta rất yêu thích những con số có tính chất đặc biệt. Số đặc biệt là số nguyên dương có đúng 3 ước nguyên dương. Với một số nguyên dương n, Tùng muốn biết có bao nhiêu số đặc biệt trong các số 1, 2, 3, ...,n.

Dữ liệu: vào từ tệp văn bản SPNUM.INP một số nguyên dương n

ết quả : ghi vào tệp văn bản SPNUM.OUT một số duy nhất là số lượng số

đặc biệt trong các số 1, 2, 3, ..., n

Giới hạn: Subtask 1: 50 các test có n 104 Subtask 2: 25 các test có n 106 Subtask 3: 25 các test có n 1012

SPNUM.INP 6 123 SPNUM.OUT 1 5

tưởng:

Một số x có đúng 3 ước nguyên dương khi và chỉ khi x là số chính phương

và căn bậc hai của x là một số nguyên tố.

Bài toán yêu cầu đếm số lượng số đặc biệt (số có đúng 3 ước) nhỏ hơn hoặc bằng n tương ứng với việc đếm xem có bao nhiêu số nguyên tố nhỏ hơn hoặc bằng căn bậc hai của n. Để tăng tốc độ kiểm tra số nguyên tố , ta sử dụng thuật toán sàng 21

số nguyên tố.

Chương trình minh họa b ng ngôn ngữ lập trình Python :

import math

def sang_nt(n):

global prime

prime[1]=0

k=int(math.sqrt(n))

for i in range(2, k+1):

if (prime[i]==1):

for j in range(i*i, n+1,i):

prime[j]=0

fi=open("spnum.inp","r")

n=int(fi.readline())

fi.close()

x=int(math.sqrt(n))

prime[1]*(x+1)

sang_nt(x)

ans=0

for i in range(2, x+1):

if (prime[i]==1): ans+=1

fo=open("spnum.out","w")

fo.write(str(ans))

fo.close()

ÀI 4: CHIA HẾT CHO 3

Cho dãy a gồm n số nguyên dương. Hãy cho biết có bao nhiêu cặp số trong dãy có tổng chia hết cho 3. Nói cách khác, bạn phải đếm xem có bao nhiêu cặp chỉ số i, j (1 ≤i

Dữ liệu: • Dòng 1: Một số nguyên duy nhất n(1≤n≤105). • Dòng 2: Ghi n số nguyên dương a1, a2, ..., an (1≤ a ≤105, i=1→ n) là các

phần tử của dãy.

22

Kết quả: Một dòng duy nhất ghi số lượng cặp số của dãy a có tổng chia hết

cho 3.

DIV3.OUT Giải thích 3

6

Ví dụ: DIV3.INP 3 3 4 2 3 4 4 3 6 9 12 3 cặp số tìm được có chỉ số là: (1,4) (1,4) (2,3) (3,5) 6 cặp số tìm được có chỉ số là: (1,2) (1,3), (1,4), (2,3) (2,4) (3,4)

tưởng:

Sử dụng đếm phân phối để lưu số c[a[i]] lần xuất hiện của m i phần tử trong

dãy a[i]. Dễ thấy được dãy c chỉ gồm 3 phần tử c[0], c[1], c[2]

kq=c[0]*(c[0]-1)/2+c[1]*c[2]

Chương trình minh họa b ng ngôn ngữ lập trình Python :

file = open("div3.inp","r")

n = int(file.readline())

a = list (map(int, file.readline().split()))

c = [0,0,0]

for x in a:

c[x % 3] += 1

file.close()

res = (c[0]*(c[0]-1))//2+ c[1]*c[2]

file = open("div3.out", "w")

file.write(str(res))

file.close()

BÀI 5. SỐ AY ẮN

Để khởi động cho một buổi học căng thẳng, giờ sinh hoạt 15 phút đầu m i buổi học của lớp 10 Tin K30 các bạn đã tổ chức trò chơi tạo hứng thú trong học tập. Người đứng ra tổ chức trò chơi là Phan Mạnh Tài, bạn là học sinh giỏi và đam mê Tin học của lớp. Hội thi Tin học trẻ toàn quốc vừa qua Tài cũng mang về cho mình một giải thưởng cá nhân. Trò chơi có tên "Tìm số may mắn" như sau: Đầu tiên Tài sử dụng máy tính sinh ra một dãy A gồm n số nguyên a1, a2, ..., an. Sau đó thực hiện Q lần chơi tìm các số may mắn, m i lần chơi máy tính sẽ đưa ra số nguyên x. Tài định nghĩa số may mắn là số xuất hiện của x trong dãy A nói trên.

Yêu cầu: Gồm Q lần chơi, m i lần chơi là một số nguyên x, bạn hãy tìm số

may mắn trong m i lần chơi tương ứng.

23

Dữ liệu: Vào từ file LUCKY.INP

Dòng 1: Một số nguyên duy nhất n (i

Các số trên cùng một dòng ghi cách nhau bởi dấu cách.

ết quả: Ghi ra file LUCKY.OUT gồm Q dòng, m i dòng là một số may

mắn với số x tương ứng.

àng buộc: Có 40 test tương ứng 40 điểm của bài toán thoả mãn Q=1,n≤103 Có 30 test tương ứng 30 điểm của bài toán thỏa mãn Q≤103, n≤103

Có 30 test cuối cùng tương ứng 30 điểm của bài không có ràng buộc gì thêm.

0 2 1

Số 5 xuất hiện 0 lần trong dãy Số 2 xuất hiện 2 lần trong dãy Số 1 xuất hiện 1 lần trong dãy

Ví dụ: LUCKY. INP LUCKY.OUT Giải thích 6 1 2 2 3 4 6 3 5 2 1

Chương trình minh họa b ng ngôn ngữ lập trình Python :

fi = open( “lucky.inp”,”r”)

fo = open (“lucky.out”,”w”)

n = int(fi.readline())

a = list(map(int,fi.readline().split()))

dic = {}

for x in a:

if (dic.get(x) == None):

dic[x] = 1

else: dic[x] +=1

q = int(fi.readline())

for i in range(q):

x = int(fi.readline())

24

if (dic.get(x) == None):

fo.write(“0\n”)

else: fo.write(str(dic[x]) + „\n‟)

fi.close()

fo.close()

ÀI 6: ẾP I VÀO HỘP

Vinh có N viên bi được xếp thành một hàng ngang, các viên bi được đánh số thứ tự từ 1 đến N (theo thứ tự từ trái sang phải). M i viên trong N viên bi có màu trắng hoặc màu đen, viên bi thứ i (i=1, 2, 3, ..., N) có khối lượng là Ai. Vinh sẽ lần lượt chọn các viên bi có thứ tự i=1, 2, 3, ..., N để xếp chung vào các hộp. Các viên bi được xếp trong một hộp phải thỏa mãn:

+ Tổng khối lượng các viên bi không quá M.

+ Các viên bi đều phải cùng màu.

Yêu cầu: Cho biết M, hãy tính xem, Vinh cần ít nhất bao nhiêu hộp để xếp hết N viên bi mà Vinh đang có.

Dữ liệu: Cho trong file văn bản XepBi.inp gồm:

+ Dòng thứ nhất ghi 2 số nguyên dương N và M

+ Dòng thứ hai ghi N số nguyên A1, A2, ..., AN (1≤Ai≤M)

+ Dòng thứ ba ghi N số nguyên C1, C2, ..., CN mô tả màu của N viên bi, nếu Ci=0 thì viên bi thứ i có màu trắng, nếu Ci=1 thì viên bi thứ i có màu đen.

ết quả ghi ra file văn bản XepBi.out gồm một số nguyên là số hộp ít nhất để Vinh có thể xếp hết N viên bi. XepBi.out XepBi.inp 3 4 7 1 2 4 5 0 0 1 1

Giải thích N=4 Khối lượng 1 2 4 5 Hộp 1: Xếp 2 viên bi thứ 1 và thứ 2 có cùng màu trắng, tổng khối lượng bằng 3. Hộp 2: Xếp 1 viên bi thứ 3 Hộp 3: Xếp 1 viên bi thứ 4.

tưởng

Xét hai viên bi liên tiếp, nếu chúng không thể xếp chung cùng một hộp thì

tăng số hộp thêm 1 đoen vị.

Điều kiện để 2 viên bi liên tiếp không thể xếp cùng 1 hộp là:

25

+ Hoặc 2 viên bi liên tiếp khác màu

+ Hoặc 2 viên bi liên tiếp cùng màu và tổng trọng lượng các viên bi hiện có

trong hộp cộng viên bi liền sau lớn hơn m

Chương trình minh họa b ng ngôn ngữ lập trình Python :

fi=open("xepbi.inp","r")

n,m=map(int, fi.readline().split())

a=list(map(int, fi.readline().split()))

c=list(map(int, fi.readline().split()))

fi.close()

sum=0; res=0

a=[0]+a; c=[2]+c

for i in range(1, n+1):

if ((c[i-1] != c[i]) or ( c[i-1]==c[i] and sum +a[i] >m)):

sum=a[i]

res+=1

else: sum+=a[i]

fo=open("xepbi.out", "w")

fo.write(str(res))

fo.close()

ÀI 7: TỔNG ĐOẠN CON

Một dãy con gồm các phần tử liên tiếp nhau trong một dãy cho trước được gọi là đoạn.

Yêu cầu: Cho dãy N số tự nhiên. Tìm đoạn con ngắn nhất có tổng các phần tử bằng giá trị k cho trước.

Dữ liệu:

+ Dòng 1: Chứa hai số nguyên dương N và K (1≤N≤20000).

+ Dòng 2: chứa N số tự nhiên a1, a2, ..., an cách nhau một khoảng trắng.

ết quả: một dòng duy nhất chứa hai số nguyên dương d và L cách nhau khoảng trắng. Trong đó d: chỉ số của phần tử đầu tiên trong đoạn; L: số phần tử trog đoạn (chiều dài đoạn). Nếu vô nghiệm thì in ra số 0.

Ví dụ:

TDOAN.INP TDOAN.OUT

26

21 17 16 3

0 2 3 2 10 1 5 5 6 12 20 30 14 8 0 11

0 6 0 0 5

tưởng:

Dữ liệu tương đối nhỏ (N≤2000) nên có thể xét mọi đoạn con của dãy, chọn lấy đoạn con có tổng bằng k và cập nhật độ dài ngắn nhất

Chương trình minh họa b ng ngôn ngữ lập trình Python :

import sys

sys.stdin=open("tdoan.inp", "r")

sys.stdout=open(("tdoan.out", "w")

n, k=map(int,input().split())

a=list(map(int, input().split()))

lmin=n

p=0

for i in range(n):

s=0

for j in range(i, n):

s+=a[j]

if (s==k and lmin>j-i+1):

lmin=j-i+1

p=i+1

break

if (p==0):

print(0)

else: print(p,lmin)

4. Khảo sát sự cấp thiết và tính khả thi của giải pháp đề xuất

4.1. ục đích khảo sát

- Giúp nắm rõ được vấn đề mình nghiêm cứu có thật sự cần thiết, đáp ứng được nhu cầu đổi mới, phát triển toàn diện cho học sinh trong giáo dục hiện nay hay không.

- Biết được mức độ khả thi của việc ứng dụng nội dung nghiên cứu của đề tài

27

trong thực tiễn

- Qua kết quả khảo sát rút ra được những kinh nghiệm cần thiết trong quá

trình nghiên cứu các giải pháp thực hiện.

4.2. Nội dung và phương pháp khảo sát

4.2.1. Nội dung khảo sát

Thứ nhất: Khảo sát tính cấp thiết của các giải pháp đề xuất đối với việc tìm hiểu và lựa chọn ngôn ngữ trong bồi dưỡng đội tuyển với chương trình giáo dục phổ thông mới 2018

Thứ hai: Khảo sát tính khả thi của các giải pháp đề xuất đối với việc sử dụng

lớp bài toán dạng số trong bồi dưỡng đội tuyển.

4.2.2. Phương pháp khảo sát và thang đánh giá

- Phương pháp khảo sát là: Sử dụng ứng dụng google forms tạo biểu mẫu và

trao đổi bằng bảng hỏi.

- Thang điểm đánh giá: gồm 4 mức (Tương ứng với số điểm từ 1 đến 4)

Không cấp thiết (1 điểm), ít cấp thiết (2 điểm), cấp thiết (3 điểm), rất cấp thiết (4 điểm). Không khả thi (1 điểm), ít khả thi (2 điểm), khả thi (3 điểm), rất khả thi (4 điểm)

- Tính điểm trung bình bằng phần mềm excel (Ký hiệu điểm trung bình là: x)

- Cách tính điểm của công cụ khảo sát như sau:

ức độ

Điểm trung bình Nội dung khảo sát 1 Nội dung khảo sát 2

Rất khả thi 3.5≤x≤4

Rất cấp thiết Cấp thiết Ít cấp thiết Không cấp thiết Khả thi Ít khả thi Không khả thi 3≤x<3.5 1.5≤x<3 1≤x<1.5

4.3. Đối tượng khảo sát

TT Đối tượng Số lượng

1 Học sinh 45

2 Giáo viên 22

28

67 Tổng

4.4. ết quả khảo sát về tính cấp thiết và tính khả thi của các giải pháp đã đề xuất 4.4.1. Sự cấp thiết của các giải pháp đã đề xuất

Sau khi hoàn thành xong đề tài sáng kiến kinh nghiệm tôi đã tiến hành khảo sát mức độ cấp thiết của các giải pháp. Cụ thể tôi đã đưa ra 1 câu hỏi để khảo sát ý kiến của giáo viên và một câu hỏi để khảo sát học sinh. Nội dung và kết quả khảo sát:

Thực trạng thực hiện

cấp cấp thiết ĐT TT Nội dung ít thiết rất cấp thiết không cấp thiết

SL % SL % SL % SL %

0 0.0 1 2.2 35 77.8 9 20 3.2 1

Theo em việc tìm hiểu và lựa chọn ngôn ngữ lập trình C++ hoặc ngôn ngữ lập trình Python để phục vụ cho việc bồi dưỡng học sinh giỏi tỉnh có cấp thiết hay không?

0 0.0 1 4.5 13 59.1 8 36.4 3.32 2

Theo thầy cô việc tìm hiểu và lựa chọn ngôn ngữ lập trình (C++ hoặc ngôn ngữ Python) để phục vụ cho việc bồi dưỡng học sinh giỏi tỉnh hiện nay có cấp thiết hay không?

0 0.0 1 1.5 12 54.5 9 40.9 3.36 3

Theo thầy cô trong công tác bồi dưỡng học sinh giỏi. Giáo viên có cần thiết dạy chuyên đề về lớp bài toán dạng số học hay không

Trung bình khảo sát Giáo viên 3.34

29

Trung bình khảo sát Giáo viên và học sinh 3.27

Kết quả trên thu được dựa trên biểu đồ thu được từ form khảo sát

Kết quả thu được

30

Kết quả thu được

Đánh giá Sự cấp thiết của các giải pháp đã đề xuất

Các thông số

TT Giải pháp ức

Trung bình

Chuyên đề lớp bài toán dạng số 1 3.36 Cấp thiết

2 3.32 Tìm hiểu và lựa chọn ngôn ngữ phù hợp khi giải quyết bài toán Cấp thiết

Trung bình chung về giải pháp 3 3.34 Cấp thiết

Nhận xét:

Qua khảo sát ta thấy đối với học sinh có 45 học sinh tham gia khảo sát trong đó có 9/45 chọn rất cấp thiết (chiếm 20 ) chọn “cấp thiết”, 35/45 (chiếm 77,8 ) , 1/45 (chiếm 2,2 ) chọn “ít cấp thiết” và không có học sinh chọn “không cấp thiết”.

Đối với giáo viên có 22 giáo viên tham gia khảo sát. Trong giải pháp 1 có 8 giáo viên chọn rất cấp thiết, 13 giáo viên chọn cấp thiết và 1 giáo viên chọn ít cấp thiết. giải pháp 2 có 22 giáo viên khảo sát. Trong đó rất cấp thiết có 9 giáo viên chọn, 12 giáo viên chọn cấp thiết và 1 giáo viên chọn ít cấp thiết. Cả hai giải pháp không có giáo viên nào chọn không cấp thiết.

Điểm trung bình cho giải pháp là 3.27 đạt mức cấp thiết, điều này chứng tỏ rằng giải pháp mà tôi đưa ra là hoàn toàn hợp lý và có tính cấp thiết đáp ứng được nhu cầu đổi mới giáo dục, nâng cao hiệu quả trong việc dạy đội tuyển học sinh giỏi trường và tỉnh.

4.4.2. Tính khả thi của các giải pháp đã đề xuất

31

Cùng với việc khảo sát tính cấp thiết tôi cũng đã khảo sát tính khả thi của giải pháp đưa ra. Cụ thể tôi đã đưa ra 1 câu hỏi để khảo sát ý kiến của giáo viên và một câu hỏi để khảo sát học sinh. Nội dung và kết quả khảo sát như sau:

Thực trạng thực hiện

Khả thi ĐT TT Nội dung Không khả thi Ít khả thi Rất khả thi

SL % SL % SL % SL %

0 0.0 2 4.4 36 80.0 7 15.6 3.1 1

Theo em học ngôn ngữ lập trình Python để thi học sinh giỏi cấp tỉnh có khả thi hay không?

0 0.0 1 4.8 12 52.4 9 42.9 3.38 2

Thầy cô đánh giá như thế nào về tính khả thi của việc vận dung đề tài " ứng dụng lớp bài toán kiểu dư liệu danh sách" để giải quyết lớp bài toán dạng số trong bồi dưỡng học sinh giỏi" ở chương trình giáo dục phổ thông mới 2018.

32

Trung bình 3.24

Đánh giá Tính khả thi của các giải pháp đã đề xuất

Các thông số

TT Các giải pháp ức

Trung bình

1 - Sử dụng chuyên đề số trong bồi dưỡng học sinh giỏi 3.1 Khả thi

2 33.8 Khả thi - Giải quyết bài toán lập trình bằng việc lựa chọn ngôn ngữ phù hợp khi tìm hiểu về C++ và Python

Nhận xét: Qua khảo sát cho thấy đối với cả học sinh và giáo viên đều thấy đề tài rất khả thi. Thể hiện qua điểm trung bình 3.24. Điều này chứng tỏ đề tài này sẽ là tài liệu áp dụng dạy, học trong ôn thi và bồi dưỡng học sinh giỏi

5. Kết quả đạt được

5.1. Đối với học sinh

Học sinh ngoài tìm hiểu được ngôn ngữ Python ở chương trình lớp 10 và 11. Học sinh còn biết điểm mạnh của ngôn ngữ lập trình Python. Các em biết lớp bài toán từ cơ bản đến nâng cao áp dụng kiểu dữ liệu danh sách. Năm học 2023-2024 trường tôi có 2 học sinh đi thi và đạt gồm (1 nhì, 1ba).

5.2. Đối với giáo viên

Giáo viên có tài liệu trong bồi dưỡng học sinh giỏi, có tài liệu về chuyên đề dữ liệu danh sách trong ngôn ngữ lập trình Python.

5.3. hả năng mang lại lợi ích thiết thực của sáng kiến

Là tài liệu cho học sinh và giáo viên trong việc ôn thi và bồi dưỡng học sinh giỏi cấp trường, huyện, tỉnh.

PHẦN 3: KẾT LUẬN

1. Kết luận

Nội dung của đề tài là tập hợp lớp các bài toán sử dụng kiểu dữ liệu danh sách

trong Python mà tác giả đã tích lũy được trong giảng dạy.

33

Đề tài này giúp giáo viên nhìn nhận được điểm ưu và nhược khi sử dụng ngôn ngữ Python. Đề tài đã được áp dụng giảng dạy trong bồi dưỡng học sinh giỏi trường và học sinh giỏi tỉnh vừa qua tại trường THPT Thái Hòa; đồng thời cũng chia sẻ, trao đổi với một số giáo viên các trường THPT của tỉnh Nghệ An và đã thu được kết quả tốt. Các em học sinh nắm được các lớp bài toán vận dụng kiểu dữ liệu danh sách khi lập trình vận dụng trong học và thi học sinh giỏi.

2. Đề xuất phạm vi

Áp dụng trong dạy học đội tuyển học sinh giỏi trường và tỉnh cho bậc trung học cơ sở và trung học phổ thông. Là tài liệu cho giáo viên dạy tin học tham khảo trong bồi dưỡng đội tuyển.

TÀI LIỆU THAM KHẢO

1. Sách Python cơ bản – Tác giả Võ Duy Tuấn

2. Think Pyhton 2nd Edition- Tác giả Allen B. Downey

3. A Byte of Python – Tác giả CodeGym

4. Dive into Python 3 – Tác giả Mark Pilgrim

5. Đường vào lập trình Python – Nhà xuất bản Đại học Quốc Gia Hà Nội

6. Tuyển tập bộ đề thi học sinh giỏi THPT môn tin học – Nhà xuất bản Dân Trí

34

...