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

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:36

Thêm vào BST

Báo xấu

1
lượt xem 0
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Sáng kiến "Ứ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" được hoàn thành với mục tiêu nhằm 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); 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; 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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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 ĩnh vực : Tin học Tổ : Toán Tin 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 : Tin học Tên tác giả : Châu Đức Vinh Tổ : Toán Tin Điện thoại : 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ữ liệu danh sách trong bồi dưỡng học sinh giỏi” 2
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. - Các tài liệu dạy lập trình 3
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. - 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 4
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ế. + 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. 5
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à giáo viên 6
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” for i in s: print(i,end=“ “) 7
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 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) 8
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() Bổ sung 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() Mở rộ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(,) vị trí index remove a.remove() Xóa đi phần tử đầu tiên có giá trị bằng 9
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. + 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. 10
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 for i in range(1, len(a)-1): 11
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) * Ghép các danh sách thành một danh sách 12
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. A = [] 13
n = int(input("Nhập số tự nhiên n:")) if n0: 14
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 maxdd=0 15
for i in range(d-1): max1=0 while a[i]*a[i+1]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] 0: current_count += 1 if current_count > max_count: max_count = current_count start_index = i - max_count + 1 else: 16
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 i0: 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=' ') i+=1 17
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