Sáng kiến kinh nghiệm THPT: Sử dụng cấu trúc dữ liệu set, map, pair và một số hàm trong C++ trong bồi dưỡng học sinh giỏi cho bài toán tìm kiếm, sắp xếp với độ phức tạp O(n) hoặc O(logn)

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

Thêm vào BST

Báo xấu

78
lượt xem 26
download

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

Đề tài "Sử dụng cấu trúc dữ liệu set, map, pair và một số hàm trong C++ trong bồi dưỡng học sinh giỏi cho bài toán tìm kiếm, sắp xếp với độ phức tạp O(n) hoặc O(logn)" chủ yếu nghiên cứu hệ thống lớp các bài toán ứng dụng cấu trúc dữ liệu map, set, pair và một số hàm có sẵn trong lập trình bằng ngôn ngữ C++. Giúp độc giả tiếp cận cách dạy, cách học một cách có hệ thống.

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: Sử dụng cấu trúc dữ liệu set, map, pair và một số hàm trong C++ trong bồi dưỡng học sinh giỏi cho bài toán tìm kiếm, sắp xếp với độ phức tạp O(n) hoặc O(logn)

SỞ GIÁO DỤC & ĐÀO TẠO NGHỆ AN TRƯỜNG THPT ĐÔ LƯƠNG 1 ……………………………… SÁNG KIẾN KINH NGHIỆM Đề tài: Sử dụng cấu trúc dữ liệu set, map, pair và một số hàm trong C++ trong bồi dưỡng học sinh giỏi cho bài toán tìm kiếm, sắp xếp với độ phức tạp O(n) hoặc O(logn) Lĩnh vực: Tin học Người thực hiện: Nguyễn Thị Hà (Giáo viên 1) Hoàng Thị Hương (Giáo viên 2) Tổ bộ môn: Toán - Tin Đơn vị: Trường THPT Đô Lương 1 Số điện thoại: 0855974950 hoặc 0983666458 Email: thuhadl1@gmail.com NĂM HỌC: 2021 – 2022 0
MỤC LỤC PHẦN I. ĐẶT VẤN ĐỀ ................................................................................................................. 2 1. Lý do chọn đề tài.................................................................................................................... 2 2. Mụ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 ...................................................................................................... 4 5.1 Nhóm phương pháp nghiên cứu lý luận ............................................................................ 4 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 C++ ...................................................................... 5 1.3. Lý luận về độ phức tạp của thuật toán ............................................................................. 6 2. Cơ sở thực tiễn ....................................................................................................................... 6 2.1. Thực trạng trước khi thực hiện các giải pháp sáng kiến .................................................. 6 2.2. Thực trạng giáo viên và học sinh trong dạy học đội tuyển học sinh giỏi ......................... 6 2.4. Thực trạng học tin lập trình của học sinh ở trường trung học phổ thông...................... 7 3. Nội dung.................................................................................................................................. 7 3.1. Kiểu dữ liệu map............................................................................................................... 7 3.2. Kiểu dữ liệu Set............................................................................................................... 23 3.3. Kiểu dữ liệu pair ............................................................................................................. 29 3.4. Các hàm lower_bound; upper_bound ............................................................................ 43 4. Áp dụng dạy thực nghiệm ................................................................................................... 46 5. Kết quả áp dụng thực nghiệm ............................................................................................ 46 PHẦN III. KẾT LUẬN ............................................................................................................... 47 1. Kết luận ................................................................................................................................ 47 2. Đề xuất phạm vi ................................................................................................................... 47 PHẦN IV. TÀI LIỆU THAM KHẢO ........................................................................................ 48 1
PHẦN I. ĐẶT VẤN ĐỀ 1. Lý do chọn đề tài Chương trình giáo dục phổ thông mới 2018 có rất 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 với dự kiến 32 tiết học. Đây là chủ đề đòi hỏi lập trình bài toán để máy tính giải quyết. Năm học 2020-2021 và năm học 2021- 2022 hầu hết tất cả các trường từ bậc trung học cơ sở đến bậc trung học phổ thông đội tuyển học sinh giỏi giải quyết các bài toán lập trình bằng ngôn ngữ C++ chứ không dùng ngôn ngữ Pascal như mấy năm trước. Vậy tại sao có sự chuyển đổi này đó chính là trong ngôn ngữ C++ ngoài những kiểu dữ liệu chuẩn học sinh đã được biết như kiểu số nguyên; kiểu số thực; kiểu kí tự; kiểu logic và một số kiểu dữ liệu có cấu trúc như kiểu mảng và kiểu xâu còn có một số cấu trúc dữ liệu như: map, set, pair được sử dụng trong các bài toán tìm kiếm, sắp xếp dễ dàng .Ngoài ra trong C++ có sẵn một số hàm cho phép chúng ta sử dụng một số dạng bài toán tìm kiếm và tính toán đơn giản trong lập trình. Nhằm nâng cao trình độ lập trình của học sinh nói chung và đáp ứng yêu cầu thi học sinh giỏi các cấp nói riêng học sinh trong lập trình luôn chú trọng đến tối ưu của thuật toán. Hay nói cách khác làm thế nào để độ phức tạp của bài toán càng nhỏ càng tốt. Khi có input thì output phải chính xác, đồng thời kết quả thời gian chạy ngắn nhất, độ phức tạp nhỏ nhất thường là O(n) hoặc O(logn). Với bài toán tìm kiếm, sắp xếp thường là các bài toán về mảng 1 chiều, liên quan dãy con liên tiếp và kết quả bài toán yêu cầu đưa ra 2 thành phần đó là giá trị và chỉ số. Vì vậy những bài toán dạng này chúng ta sử dụng cấu trúc dữ liệu map, pair, set dễ giải quyết với độ phức tạp bài toán O(n) hoặc O(logn) với dữ liệu lớn. Cấu trúc đề thi học sinh giỏi cũng đề cập đến bài toán tìm kiếm chúng ta biết khai thác tối đa ngôn ngữ C++ trong tìm kiếm với một số hàm có sẵn như: find; lower_bound; upper_bound viết code một cách nhanh chóng, hữu dụng. Thực tế về dạy học đội tuyển cấp tỉnh môn tin học giáo viên cũng như học sinh không chỉ lập trình được bài toán đó mà cần yêu cầu thời gian chạy ít nhất. Nói một cách khác là mỗi 1 test yêu cầu chạy tối đa không quá 1 giây thì lúc đó mới có kết quả cao. Tuy nhiên thực tế học sinh lập trình được bài toán nhưng cứ thường quá thời gian. Một trong những lỗi vượt quá thời gian thường xảy ra là thuật toán chưa tối ưu. Muốn như vậy thì độ phức tạp cho các bài toán với kiểu dữ liệu lớn thường từ 104 trở lên phải là O(n) hoặc O(logn). Do đó chúng ta cần biết vận dụng điểm mạnh trong ngôn ngữ C++ như về cấu trúc dữ liệu, các kiểu dữ liệu và các hàm có sẵn. 2
Vì vậy trong quá trình giảng dạy tôi đúc rút ra một số kinh nghiệm để giúp các học sinh tiếp cận nội dung này dễ dàng hơn, tạo nhiều đam mê cho học sinh. Để rèn năng lực và kỹ năng lập trình cho học sinh khá, giỏi môn Tin học. Qua kinh nghiệm bồi dưỡng học sinh giỏi đội tuyển tỉnh và tôi đã có những kết quả nhất định. Cụ thể năm học 2021-2022 tôi mạnh dạn bồi dưỡng 2 em dự thi cấp tỉnh và đạt cả 2, trong đó có 1 em đạt 17/20. Với những lý do trên tôi đã đưa ra đưa ra đề tài “Sử dụng cấu trúc dữ liệu set, map, pair và một số hàm trong C++ trong bồi dưỡng học sinh giỏi cho bài toán tìm kiếm, sắp xếp với độ phức tạp O(n) hoặc O(logn)”. 2. Mục đích nghiên cứu Trong quá trình nghiên cứu và giảng dạy, tôi nhận thấy ngôn ngữ lập trình C++ cung cấp nhiều thư viện nên rất tiện lợi trong quá trình lập trình giải các bài toán, đồng thời lớp các bài toán về tìm kiếm và sắp xếp cũng được vận dụng nhiều trong lập trình. Vì vậy, tôi viết đề tài này với mục đích: - Thứ nhất, trao đổi cùng với các đồng nghiệp về việc vận dụng ngôn ngữ C++ trong việc lập trình. - Thứ hai, là tài liệu cho giáo viên phục vụ giảng dạy, bồi dưỡng HSG. 3. Nhiệm vụ và phạm vi nghiên cứu 3.1 Nhiệm vụ nghiên cứu Đề tài chủ yếu nghiên cứu hệ thống lớp các bài toán ứng dụng cấu trúc dữ liệu map, set, pair và một số hàm có sẵn trong lập trình bằng ngôn ngữ C++. Giúp độc giả tiếp cận cách dạy, cách học một cách có hệ thống. 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 học tại trường THPT Đô Lương 1. Đề 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 C++ - Cấu trúc đề thi học sinh giỏi tỉnh môn tin tỉnh Nghệ An - Các kiểu dữ liệu cấu trúc . - Một số hàm tìm kiếm. - Đối tượng học sinh đội tuyển tin học sinh giỏi trường và tỉnh. 3
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 chương trình giáo dục phổ thông mới 2018. 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. - Nghiên cứu, phân tích cấu trúc và nội dung chương trình tin học THPT đặc biệt là cấu trúc đề thi học sinh giỏi cấp trường và cấp tỉnh khối THCS và THPT môn tin học. Các tài liệu liên quan đến ngôn ngữ lập trình C++ và cấu trúc dữ liệu nâng cao trong C++. 5.2. Nhóm phương pháp nghiên cứu thực tiễn - Thực tiễn qua các dạy học bồi dưỡng đội tuyển học sinh giỏi tỉnh và ôn luyện học sinh giỏi cấp trường. 5.3. Phương pháp thực nghiệm - Thực nghiệm qua bồi dưỡng học sinh giỏi tỉnh và kết quả đạt được của đội tuyển tỉnh qua các khi tham dự kỳ thi HSG tỉnh. Nhất là năm 2021-2022 lập trình bằng ngôn ngữ C++. 6. Tính mới và đóng góp của đề tài - Giúp học sinh đội tuyển học sinh giỏi biết được các cấu trúc dữ liệu nâng cao. Các hàm có sẵn trong C++. Vận dụng những đặc trưng cấu trúc dữ liệu vào giải quyết các bài toán một cách đơn giản. Như bài toán về tần số, bài toán tìm kiếm và bài toán sắp xếp. - Là tài liệu cho học sinh giỏi cấp trường và cấp tỉnh tham khảo. Đồng thời tài liệu cho giáo viên dạy đội tuyển bậc THCS và THPT môn tin học. PHẦN II. NỘI DUNG 1. Cơ sở lý luận 1.1. Lý 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 4
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 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. Lý luận dạy học về dạy học lập trình C++ - Học lập trình C++ cơ bản đang là một xu hướng của ngành lập trình hiện nay. Bởi vì C++ là ngôn ngữ phổ biến đứng thứ 5 hiện nay. Có rất nhiều ứng dụng phổ biến được viết bằng loại ngôn ngữ này như Photoshop, Chrome,.. Cho nên nó có sức ảnh hưởng rất lớn về xu hướng của ngôn ngữ lập trình hiện nay. - Điểm mạnh của C++ với những ngôn ngữ lập trình khác + Ngôn ngữ C++ là ngôn ngữ cấp trung. Nó có sự kết hợp các tính năng của cả 2 ngôn ngữ cấp cao và thấp. C++ có thể sử dụng cho lập trình để giúp người dùng có thể thâm nhập được vào phần cứng. Hỗ trợ các chức năng của ngôn ngữ lập trình bậc cao. + C++ là ngôn ngữ lập trình có cấu trúc cho phép một chương trình phức tạp được chia thành các chương trình đơn giản nhỏ hơn nó. Đó được gọi là các hàm. Nó còn cho phép di chuyển dữ liệu dễ dàng giữa các hàm. Mà bạn vẫn thường xuyên thấy ở các ngôn ngữ lập trình hiện đại ngày nay. + Có nhiều tính năng khác nhau. Nó cho phép người dùng truy cập trực tiếp vào các API phần cứng của máy, sự xuất hiện của phiên dịch. Đặc biệt là sử dụng tài nguyên của máy và cấp phát bộ nhớ. Đó là sự tối ưu của các ứng dụng và trình điều khiển các hệ thống nhúng. Ngôn ngữ lập trình vô cùng hiệu quả và tiện dụng. Nó được sử dụng cho các hệ thống. Nó nằm trong hệ thống lớn của hệ điều hành Windows, Unix,… + Là ngôn ngữ lập trình đa mục đích. Có thể ứng dụng được trực tiếp vào các ứng dụng của doanh nghiệp, game, đồ họa,… -Ngôn ngữ lập trình C++ nhanh hơn hầu hết những ngôn ngữ khác như Python, Java. Đó cũng chính là lý do mà người dùng thường thích sử dụng ngôn ngữ này hơn so với những ngôn ngữ khác. Vậy việc học lập trình C++ luôn là điều mà người lập trình nào cũng muốn hướng tới. 5
1.3. Lý luận về độ phức tạp của thuật toán - Giả sử ta có hai thuật toán P1 và P2 với thời gian thực hiện tương ứng là T1(n) = 100n2 (với tỷ suất tăng là n2) và T2(n) = 5n3 (với tỷ suất tăng là n3). Khi n > 20 thì T1 < T2. Sở dĩ như vậy là do tỷ suất tăng của T1 nhỏ hơn tỷ suất tăng của T2. Như vậy một cách hợp lý là ta xét tỷ suất tăng của hàm thời gian thực hiện chương trình thay vì xét chính bản thân thời gian thực hiện. Cho một hàm T(n), T(n) gọi là có độ phức tạp f(n) nếu tồn tại các hằng C, N0 sao cho T(n) ≤ Cf(n) với mọi n ≥ N0 (tức là T(n) có tỷ suất tăng là f(n)) và kí hiệu T(n) là O(f(n)) (đọc là “ô của f(n)”). Các hàm thể hiện độ phức tạp có các dạng thường gặp sau: log2n, n, nlog2n, n2, n3,2n, n!, nn. Trong cách viết, ta thường dùng logn thay thế cho log2n cho gọn. Khi ta nói đến độ phức tạp của thuật toán là ta nói đến hiệu quả thời gian thực hiện chương trình nên có thể xem việc xác định thời gian thực hiện chương trình chính là xác định độ phức tạp của thuật toán. 2. Cơ sở thực tiễn 2.1. Thực trạng trước khi thực hiện các giải pháp sáng kiến Học sinh có thể giải quyết bài toán với nhiều cách khác nhau. Nhưng để đảm bảo theo yêu cầu của đề và chạy 1 giây theo dữ liệu đề thì hầu như học sinh thường vất phải lỗi này. Vậy làm thế nào để có thể giải quyết bài toán tối ưu nhất? Có các giải pháp nào cho các bài toán đó. Chúng ta cùng tìm hiểu và vận dụng các hàm có sẵn trong C++ và kiểu dữ liệu có cấu trúc với bài toán sắp xếp, tìm kiếm và tần suất. 2.2. Thực trạng giáo viên và học sinh trong dạy học đội tuyển học sinh giỏi - Học sinh đa số đã làm quen với ngôn ngữ Pacal, nên khi chuyển sang ngôn ngữ C++ các em còn bỡ ngỡ. Đồng thời ở chương trình tin học cũ lớp 11 kiểu dữ liệu có cấu trúc nâng cao như bản ghi thì giảm tải. chỉ có kiểu mảng, xâu. Nên khi giải quyết một số bài toán gặp khó khăn. - Các tài liệu viết một cách chung chung. Để tìm một tài liệu chi tiết, đầy đủ, dễ đọc và áp dụng là rất khó. Mặt khác các thuật toán tương đối khó nên phải dành khá nhiều thời gian cho việc ngồi trên máy tính để lập trình. Trong khi đó các em còn rất nhiều kiến thức phải học các môn khác. - Giáo viên dạy đội tuyển cơ bản đã đầu tư tìm tòi. Tuy nhiên giáo viên cơ bản cũng chưa được làm việc nhiều với ngôn ngữ C++ nên gặp khó khăn. Đồng thời các hàm có sẵn trong C+ và kiểu dữ liệu có cấú trúc không có sẵn nội dung trong sách giáo khoa nên bắt buộc giáo viên đó phải nghiên cứu nhiều và biết vận dụng và bài toán. - 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
2.4. Thực trạng học tin lập trình của học sinh ở trường trung học phổ thông - 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. - Môn tin học không áp dụng thi tốt nghiệp hay đại học nên các em cứ theo xu hướng là thi nào học đó. Nên chọn học sinh vào đội tuyển để các em dành thời gian học và nghiên cứu môn tin lập trình rất khó khăn. Muốn đạt kết quả cao trong các kì thi học sinh giỏi tỉnh 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. Còn phải đư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à những tìm ra được những lợi thế và điểm mạnh của C++ như các chương trình có sẵn. Các cáu trúc dữ liệu nâng cao vận dụng dễ dàng để giải quyết bài toán. 3. Nội dung 3.1. Kiểu dữ liệu map Trong quá trình học tập và tìm hiểu, có thể các bạn rất quen thuộc và hay sử dụng các phép toán trên mảng, xâu kí tự. Trong bài viết này, sẽ giới thiệu với các bạn 1 cấu trúc dữ liệu khá mạnh, giúp giải quyết nhiều bài toán với tốc độ cao và cách cài đặt đơn giản. đó là map. a, Map là gì Map trong C++ là một tập hợp các phần tử được sắp xếp theo thứ tự cụ thể, mà mỗi phần tử trong đó được hình thành bởi sự kết hợp của một cặp khóa và giá trị (key & value), với mỗi khóa là duy nhất trong map. Trong map, các khóa (key) được sử dụng để sắp xếp và xác định giá trị (value) tương ứng được liên kết với nó. Các cấu trúc dữ liệu như mảng hay xâu kí tự, khi truy xuất dữ liệu bạn sẽ sử dụng một tham số gọi là chỉ số, ví dụ như arr[1], str[2], … Đối với cấu trúc dữ liệu map, để truy xuất dữ liệu bạn sẽ sử dụng một tham số gọi là key Cấu trúc dữ liệu kiểu map là một cấu trúc dữ liệu ánh xạ giữa cái gọi là khoá (key) sang giá trị của khoá đó (gọi là value). Trong cấu trúc dữ liệu này, mỗi một key sẽ nhận một giá trị khác nhau. 7
b, Khai báo map Cú pháp: map someMap; Trong đó: + kiểu dữ liệu của key thường là string hoặc số nguyên + kiểu dữ liệu của value thường là giá trị số như int, float, ..v.v. ; + someMap: tên bạn muốn đặt cho map. Ví dụ về khai báo map như sau: map m; Trong đó: m là tên map c, Sử dụng map Có 3 phương thức chính trong map: * Phương thức 1: Thêm 1 cặp key- value bằng cách gán 1 key với 1 giá trị Cấu trúc: Tên map [key]=value; Ví dụ 1: m[100]=200 ; Nghĩa là thêm 1 cặp (key-value) vào trong map Ngoài ra để thêm 1 cặp (key- value) vào map bạn có thể sử dụng tên map.insert({key, value}); Ví dụ 2: m.inser({300,400}); 8
m.inser({400,500}); Như vậy ta đã thêm 3 cặp giá trị vào map gồm ({100,200};{300,400};{400,500}) Ví dụ 3: khai báo map và them cặp giá trị vào map map A; // Khởi tạo một map A // Thêm vào map A một số phần tử. A["One"] = 1; A["Two"] = 2; A["Three"] = 3; Phương thức 2: Truy suất giá trị thông qua khóa(key); Để duyệt qua các phần tử map các bạn có thể dùng for(auto it:tên map) cout
d, Ứng dụng kiểu cấu trúc map vào trong các bài toán Với cấu trúc dữ liệu map nó phù hợp với dạng bài toán về tần suất xuất hiện các phần tử trong mảng hoặc các ký tự, từ trong xâu. Một đặc điểm nổi bật của map là các key sẽ tự sắp xếp theo thứ tự tăng dần. Bài toán 1: Đếm số lần xuất hiện các phần tử trong mảng sau đó in ra tần suất xuất hiện các số trong mảng. Ví dụ: Input Out put 8 -41 1 1 2 3 5 1 -4 1 14 21 31 51 Bài toán này ta có thể sử dụng 2 vòng for lồng nhau hoặc có thể sử dụng 1 mảng đếm. Tuy nhiên khi sử dụng mảng đếm dữ liệu các giá trị trong mảng phải là số không âm và có giá trị kích thước là bé hơn 107. Vậy chẳng may có bài toán mà giá trị trong mảng số âm chẳng hạn. Thì lúc này bạn không thể sử dụng mảng giá trị để đếm được hay đánh dấu vì chỉ số lúc này âm. Hoặc giá trị trong mảng lên đến 1018 thì vượt quá kích thước mảng. Vậy để giải quyết bài toán này ta sử dụng cấu trúc dữ liệu map. Vì ở đây mỗi Key là duy nhất và khác nhau. Tương ứng key là giá trị phần tử mảng đồng thời value là giá trị xuất hiện phần tử đó. Cụ thể: Ta khai báo một map với tên là m. Sau đó tương ứng giá trị phần tử x thì m[x]++. Khi đó x là key và key giống nhau thì giá trị map tăng lên. Mỗi giá trị x ta tìm ra được value. Nói cách khác mỗi key- sẽ là 1 value tương ứng. Giá trị value tương ứng của key đó chính là tần suất xuất hiện của x trong dãy. Đoạn lệnh sau: for(int i=1; i>x; m[x]++; } Đây là đoạn lệnh đọc giá trị trong tệp ra biến x tương ứng mỗi x là 1 key và m[x] là value. 10
Truy xuất kết quả của map ghi vào tệp. trong đó it.first là key và it.second là tần số xuất hiện hay là value for(auto it:m) cout
Vậy với dạng này khi ta sử dụng map cần lưu giá trị các phần tử vào mảng. Đồng thời mỗi value khác không có nghĩa là có xuất hiện giá trị đó trong mảng thì in giá trị mảng và đánh dấu map. Cụ thể đoạn chương trình sau: for(int i=1; i>a[i]; m[a[i]]++; } for(int i=1; i
Bài toán 2: Thuộc Bài số 2 trang 73 trong sách giáo khoa tin học 11 nội dung bài tập và thực hành số 5. Bài toán: Viết chương trình nhập từ bàn phím 1 xâu kí tự s và thông báo ra màn hình số lần xuất hiện của mỗi chữ cái tiếng anh trong s (không phân biệt chữ hoa, chữ thường) Với bài toán này ký tự tiếng anh không phân biệt chữ hoa, chữ thường. Do đó học sinh nghĩ ngay biến đổi chữ cái tiếng anh về thường hoặc hoa. Lúc này chữ cái tiếng anh chỉ chòn 29 ký tự là từ ‘a’ đến ‘z’ hoặc từ ‘A’ đến ‘Z’. Và ý tưởng là sẽ có 2 vòng for lồng nhau cùng với mảng lưu đếm Cụ thể: for( ch=’A’; ch
getline(cin,s); int x=s.size(); for(int i=0; i< x;i++) { char ch=s[i]; m[ch]++; } for(auto it:m) cout
m[s[i]]=0; } Chương trình hoàn thiện #include using namespace std; int main() { map m; string s; freopen("demkytu.inp","r",stdin); freopen("demkytu.out","w",stdout); getline(cin,s); int x=s.size(); for(int i=0; i< x;i++) { m[s[i]]++; } for(int i=0; i< x;i++) if(m[s[i]]!=0) { cout
như vây key của chúng ta kiểu string. Do đó với cách làm tương tự chỉ khác ở chỗ khai báo kiểu dữ liệu trong map của key là string. Chương trình hoàn thiện #include using namespace std; int main() { map m; int n; freopen("xauchuoi.inp","r",stdin); freopen("xauchuoi1.out","w",stdout); cin>>n; for(int i=1; i>s; m[s]++; } for(auto it: m) cout
#include using namespace std; string kq; int lon=0; int main() { map m; int n; freopen("xauchuoi.inp","r",stdin); freopen("xauchuoi.out","w",stdout); cin>>n; for(int i=1; i>s; m[s]++; } for(auto it: m) { if(it.second > lon) { lon=it.second; kq=it.first; } } cout
kq=it.first;} } cout
Với bài toán trên yêu cầu đưa ra kết quả số nguyên có tần số xuất hiện nhiều nhất (trong trường hợp có nhiều số nguyên có tần số cao nhất bằng nhau, hãy đưa ra số nguyên nhỏ nhất và tần số của nó). Bài toán này ta nghĩ ngay đến cặp key- value. Trong đó key chính là số nguyên còn value chính là tần số xuất hiện. Tại sao ở đây ta sử cấu trúc dữ liệu map. Bởi vì mỗi key là duy nhất nên có nhiều số nguyên giống nhau thì chỉ là 1 key tương ứng số nguyên đó. Còn xuất hiện nhiều lần chính là tần số tương ứng ( value). Trong trường hợp cùng value thì đưa ra key nhỏ nhất. Mà key trong map đã tự sắp xếp theo thứ thự từ bé đến lớn. Do đó để tìm value Max ta có đoạn lệnh như sau: int ln=0; if(it.second>ln) { ln=it.second; kq=it.first; } Chương trình hoàn thiện #include using namespace std; long long x,kq, ln=0; int main() { map m; int n; freopen("bai1.inp","r",stdin); freopen("bai1.out","w",stdout); cin>>n; for(int i=1; i>x; m[x]++; } for(auto it:m) if(it.second>ln) { ln=it.second; kq=it.first; } cout