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

Sà GIÁO DĀC & ĐÀO T¾O NGHà AN
TR ̄àNG THPT ĐÔ L ̄¡NG 1
&&&&&&ö÷&&&&&&

Tóm Tắt

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

NĂM HàC: 2021 – 2022

MĀC LĀC

PHÄN I. Đ¾T VÂN ĐÀ
- 1. Lý do chán đÁ tài
- 2. Māc đích nghiên cứu
- 3. Nhiám vā và ph¿m vi nghiên cứu
  - 3 Nhiệm vụ nghiên cứu
  - 3 Phạm vi nghiên cứu
- 4. Đái t°ÿng nghiên cứu
- 5. Ph°¢ng pháp nghiên cứu
  - 5 Nhóm phương pháp nghiên cứu lý luận
  - 5. Nhóm phương pháp nghiên cứu thực tiễn
  - 5. Phương pháp thực nghiệm
- 6. Tính mßi và đóng góp của đÁ tài
PHÄN II. NàI DUNG
- 1. C¢ sở lý lu¿n
  - 1. Lý luận về chương trình phổ thông mới
  - 1. Lý luận dạy học về dạy học lập trình C++
  - 1. Lý luận về độ phức tạp của thuật toán
- 2. C¢ sở thāc tißn
  - 2. Thực trạng trước khi thực hiện các giải pháp sáng kiến
  - 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
  - 2. Thực trạng học tin lập trình của học sinh á trưßng trung học phổ thông
- 3. Nái dung
  - 3. Kiểu dữ liệu map
  - 3. Kiểu dữ liệu Set
  - 3. Kiểu dữ liệu pair
  - 3. Các hàm lower_bound; upper_bound
- 4. Áp dāng d¿y thāc nghiám
- 5. K¿t quÁ áp dāng thāc nghiám
PHÄN III. K¾T LU¾N
- 1. K¿t lu¿n
- 2. ĐÁ xuÃt ph¿m vi
PHÄN IV. TÀI LIàU THAM KHÀO

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

1. 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) f Cf(n) với mọi n g 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. 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. 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. 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. 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.

m({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<<= <<< it;

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(); it !=
tên map(); 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(100)!=0) cout<<= fount=;

else cout<<=not fount=;

Khi sử dāng hàm find

If(m(100)!=m())

cout<<= fount=;

else cout<<=not fount=;

Với hàm find tìm thấy khi khác map và không tìm thấy khi bằng map

Ph°¢ng thức 3 : Xóa cặp Key-value khỏi map.

Viác xóa key đồng nghĩa xóa cặp key-value tương āng cÿa key.

Ta sử dāng hàm erase với cú pháp như sau:

Tên map(key);

Với các thao tác thêm, xóa, tìm độ phāc t¿p O(logn).

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
1 1 2 3 5 1 -4 1

– 4 1

1 4

2 1

3 1

5 1

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 10 7**_. 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 10_** 18 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<=n;i++)
{
int x;
cin>>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.

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<=n;i++)
{
cin>>a[i];
m[a[i]]++;
}
for(int i=1; i<=n; i++)
if(m[a[i]]!=0)
{
cout<<a[i]<<" "<<m[a[i]]<<'\n';
m[a[i]]=0;
}
Chương trình hoàn thián
#include <bits/stdc++.h>
using namespace std;
int a[1000007];
int main()
{
map<int,int> m;
int n;
freopen("songuyen","r",stdin);
freopen("songuyen","w",stdout);
cin>>n;
for(int i=1; i<=n;i++)
{
cin>>a[i];
m[a[i]]++;
}
for(int i=1; i<=n; i++)
if(m[a[i]]!=0)
{
cout<<a[i]<<" "<<m[a[i]]<<'\n';
m[a[i]]=0;
}
}

Map đ¿c biát m¿nh là cái mà b¿n h°ßng tßi là các ký tā và các chußi vßi tÅn sá
xuÃt hián của ký tā ho¿c chuß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ừ 8a9 đến 8z9 hoặc từ 8A9 đến 8Z9. 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=9A9; ch<=9Z9; ch++)

for(i=0;i<S();i++)

if(ch==S[i]) mang[ch]++;

Tuy nhiên nếu đề bài phân biệt chữ hoa, chữ thưßng thì cách này sẽ không giải
quyết được. Làm thế nào để giải quyết bài toán phân biệt chữ hoa chữ thưßng. Vì
vậy chúng ta nghĩ ngay đến kiểu dữ liệu map vì mỗi ký tự chữ cái là (key). Số lần
xuất hiện kí tự là (value). Với bài toán này sử dụng cấu trúc dữ liệu map giải
quyết cách đơn giản. Trong đó key là ký tự chữ cái.

INPUT OUT PUT

abcbaaccAABBccbbd A 2
B 2

a 3

b 4

c 5

d 1

Chương trình hoàn thián:
#include <bits/stdc++.h>
using namespace std;
int main()
{
map<char,int> m;
string s;
freopen("demkytu","r",stdin);
freopen("demkytu","w",stdout);

m[s[i]]=0;
}
Chương trình hoàn thián
#include <bits/stdc++.h>
using namespace std;
int main()
{
map<char,int> m;
string s;
freopen("demkytu","r",stdin);
freopen("demkytu","w",stdout);
getline(cin,s);
int x=s();
for(int i=0; i< x;i++)
{
m[s[i]]++;
}
for(int i=0; i< x;i++)
if(m[s[i]]!=0)
{
cout<<s[i];
m[s[i]]=0;
}
}
Dựa vào cấu trúc dữ liáu map. Mỗi key là duy nhất mà trong bài toán này key là ký
tự.

Bài toán 3: Cho các xâu và đưa ra các xâu khác nhau và số lần xuất hián các xâu
đó.

Input Out put
9
python
C++
C++
java
java
Pacal
python
pacal
truong

C++ 2

Pacal 1
java 2
pacal 1
python 2
truong 1

Với bài toám này chúng ta sử dụng cấu trúc dữ liệu dễ dàng giải quyết. Vì khóa
á đây là xâu và value là số lần xuất hiện các xâu. Điểm mạnh cÿa map là chỗ này,

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 <bits/stdc++.h>
using namespace std;
int main()
{
map<string, int> m;
int n;

freopen("xauchuoi","r",stdin);
freopen("xauchuoi1","w",stdout);
cin>>n;
for(int i=1; i<=n;i++)
{
string s;
cin>>s;
m[s]++;
}
for(auto it: m)
cout<<it<<" "<<it<<'\n';
}

Nếu bài toán yêu cầu đưa ra xâu có tần suất xuất hiện nhiều nhất. Lúc này ta
hiểu tần số đó chính là value trong map còn xâu chính là key. Vậy ta lấy giá trị
value trong map so sánh để tìm ra value lớn nhất. Trong đó value chính là thành
phần second còn key chính là first. Tương āng value lớn nhất ta sẽ có key tương
āng.

Cụ thể: Dùng 1 biến lưu value lớn nhất.

Duyệt lần lượt các value trong map. Lưu ý value trong map là thành phần second
còn first là thành phần key.

int lon=0;
for(auto it: m)
{
if(it > lon)
{
lon=it;
kq=it;
}
}

Chương trình hoàn thián

kq=it;}
}
cout<<kq<<" "<<lon<<'\n';

Āng dāng cÿa map có rất nhiều bài toán. Chúng tôi đưa ra một số bài trong đề thi
học sinh giỏi tỉnh nghá an các năm. Đó là d¿ng bài toán về tần suất xuất hián các giá
trị trong dãy số hoặc ký tự trong xâu. Với bài toán d¿ng này chúng tôi đã d¿y cho
học sinh sử dāng kiểu dữ liáu cấu trúc map thật đơn giản và độ phāc t¿p bài toán là
O(logn).

Đề thi học sinh giỏi tỉnh các năm có bài toán về tần suất xuất hiện các giá trị trong
dãy.

Cā thể các đề các năm như sau:

Đề thi học sinh giỏi năm học 2010-2011 tỉnh nghệ An

Bài toán: (5 điểm) TÄN Sà
Cho dãy số nguyên dương, số lần xuất hián cÿa một số đưÿc gọi tần số cÿa số
nguyên đó. Hãy tìm số nguyên dương có tần số cao nhất và tần số tương āng cÿa
nó.
Dữ liệu vào c ho từ file văn bản BAI1 bao gồm:
 Dòng đầu là số N (1f N f 10000) là số lưÿng các số nguyên trong dãy.
 Mỗi dòng trong N dòng tiếp theo chāa số nguyên M (1f M f 1000) trong dãy.
Kết quả ghi ra file văn bản BAI1, gồm 2 số nguyên viết trên một dòng, số thā
nhất ghi số nguyên có tần số cao nhất, số thā 2 là tần số cÿa nó (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ó). Hai số cách nhau một ký tự trắng.
Ví dā:

BAI1 BAI1 BAI1 BAI1

9 1 2 5 6 3 7 2 5 2
2 3 7
2 4 6 7 7 2 4

2 2

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>ln)
{
ln=it;
kq=it;
}