SKKN 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)

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

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

b, Khai báo map Cú pháp:
+ 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<int,int> 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});
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<string, int> 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<<it.first<<” “<< it.second;
Hoặc bạn có thể sử dụng interator cụ thể như sau: for(map<kiểu dữ liệu key, kiểu dữ liệu value>:: interator it=tên map.begin(); it != tên map.end(); it++)
cout<<(*it).first<<” “<<(*it).second;
* Tìm các key trong map có tồn tại hay không:
Ta có thể sử dụng hàm count hoặc hàm find Ví dụ: Tìm kiếm một key có giá trị bằng 100 if(m.count(100)!=0) cout<<” fount”; else cout<<”not fount”;
Khi sử dụng hàm find If(m.find(100)!=m.end()) cout<<” fount”; else cout<<”not fount”;
Với hàm find tìm thấy khi khác map.end và không tìm thấy khi bằng map.end *Phương thức 3: Xóa cặp Key-value khỏi map.