SỞ GIÁO DỤC VÀ ĐÀO TẠO THANH HOÁ

TRƯỜNG THPT ĐẶNG THAI MAI

SÁNG KIẾN KINH NGHIỆM

GIÚP HỌC SINH CÀI ĐẶT CHƯƠNG TRÌNH TỐI ƯU KHI
GIẢI MỘT SỐ BÀI TẬP CÓ SỬ DỤNG THUẬT TOÁN SẮP
XẾP BẰNG NGÔN NGỮ LẬP TRÌNH PASCAL VÀ C++
NHẰM NÂNG CAO CHẤT LƯỢNG HỌC SINH GIỎI
MÔN TIN HỌC Ở TRƯỜNG THPT

Người thực hiện: Hoàng Thị Mai
Chức vụ: Giáo viên
SKKN thuộc lĩnh vực: Tin học

THANH HÓA NĂM 2020


MỤC LỤC
1. Mở đầu..............................................................................................................1
1.1. Lý do chọn đề tài............................................................................................1
1.2. Mục đích nghiên cứu......................................................................................1
1.3. Đối tượng nghiên cứu.....................................................................................2
1.4. Phương pháp nghiên cứu................................................................................2
2. Nội dung sáng kiến kinh nghiệm....................................................................2
2.1. Cơ sở lí luận....................................................................................................2
2.2. Thực trạng vấn đề trước khi áp dụng sáng kiến kinh nghiệm.........................3
2.2.1. Đặc điểm tình hình nhà trường....................................................................3
2.2.2. Thực trạng trước khi nghiên cứu..................................................................3
2.3. Giải pháp đã sử dụng để giải quyết vấn đề.....................................................4

2.3.1. Cơ sở lý thuyết.............................................................................................4
2.3.1.1. Bài toán sắp xếp........................................................................................4
2.3.1.2. Thuật toán sắp xếp lựa chọn.....................................................................4
2.3.1.3. Thuật toán sắp xếp nhanh.........................................................................5
2.3.1.4. Thuật toán sắp xếp bằng phương pháp đếm phân phối.............................6
2.3.2. Biện pháp cài đặt chương trình tối ưu khi giải một số bài tập có sử dụng
thuật toán sắp xếp...................................................................................................6
2.3.2.1. Bài tập ví dụ có sử dụng thuật toán sắp xếp.............................................7
2.3.2.2. Bài tập áp dụng.......................................................................................11
2.3.2.2.1. Một số bài tập sử dụng thuật toán sắp xếp nhanh................................11
2.3.2.2.2. Một số bài tập sử dụng thuật toán đếm phân phối...............................16
2.4. Hiệu quả sáng kiến kinh nghiệm...................................................................19
3. Kết luận và kiến nghị.....................................................................................19
3.1. Kết luận.........................................................................................................19
3.1. Kiến nghị.......................................................................................................20


1. Mở đầu
1.1. Lý do chọn đề tài
Trong quá trình giảng dạy cũng như bồi dưỡng học sinh giỏi, tôi gặp rất
nhiều các bài tập có sử dụng thuật toán sắp xếp. Có thể thấy sắp xếp đóng vai trò
rất quan trọng trong cuộc sống nói chung và tin học nói riêng. Theo D.Knuth thì
40% thời gian tính toán của máy tính là dành cho việc sắp xếp. Do đặc điểm dữ
liệu như số thực hay số nguyên, kí tự hay xâu, kích thước nhỏ hay lớn, lưu trữ ở
bộ nhớ trong hay bộ nhớ ngoài, ... mà người ta có nhiều thuật toán sắp xếp khác
nhau. Trong số đó, sắp xếp lựa chọn, sắp xếp nhanh, sắp xếp bằng phương pháp
đếm phân phối là những thuật toán hay, dễ cài đặt, được ứng dụng nhiều khi giải
các bài toán Tin học. Mỗi thuật toán sắp xếp có những ưu điểm và nhược điểm
riêng. Khi học sinh gặp dạng bài tập này, mặc dù việc đoán nhận lớp giải thuật
sắp xếp không phải quá khó nhưng học sinh lại nóng vội bắt tay ngay vào việc

viết chương trình hoặc chủ quan không để ý đến đặc điểm, giới hạn dữ liệu đề
bài ra, dẫn đến việc sử dụng một số giải thuật sắp xếp không phù hợp và chưa
tối ưu đối với yêu cầu dữ liệu vào của đề ra. Do vậy, trong các kì thi học sinh
giỏi các em có thể đạt một số điểm nhất định, nhưng kết quả không cao, không
tương xứng với khả năng và công sức bỏ ra.
Với mong muốn giúp học sinh giải quyết tốt hơn các bài tập có sử dụng
thuật toán sắp xếp và hiểu biết sâu sắc hơn cách giải bài tập dạng này. Tôi đã
nghiên cứu tìm ra các ưu điểm và nhược điểm nổi bật của 3 thuật toán sắp xếp,
đánh giá độ phức tạp, đo thời gian thực hiện chương trình để so sánh và đưa ra
cách giải phù hợp, có hiệu quả nhất của từng thuật toán sắp xếp đối với từng
kiểu dữ liệu khác nhau. Qua đó, phát triển tư duy lập trình cho học sinh và dần
nâng cao chất lượng học sinh giỏi môn Tin học.
Hơn nữa, ngày nay các ứng dụng công nghệ thông tin ngày càng phát
triển. Các ngôn ngữ lập trình phát triển rất nhanh đáp ứng nhu cầu dạy và học
hiện đại. Hiện tại, ngôn ngữ lập trình pascal đang được sử dụng trong dạy học
lập trình ở lớp 11 đã trở nên lạc hậu, tính ứng dụng thực tế không cao cùng với
tâm lí xem môn Tin là môn học phụ nên không thu hút được sự yêu thích tìm tòi
khám phá của học sinh, dẫn đến việc học trở nên đối phó. Do vậy, việc lựa chọn
một ngôn ngữ lập trình phù hợp, đáp ứng được nhu cầu phát triển ngày càng cao
của nền giáo dục hiện đại là rất cần thiết. Nên tôi đã trăn trở nghiên cứu tìm hiểu
thêm ngôn ngữ lập trình C++ (đây là ngôn ngữ thú vị, dễ học, tương đồng với
Pascal, chương trình thực hiện nhanh) để chuyển thể một số bài tập có sử dụng
thuật toán sắp xếp từ ngôn ngữ lập trình pascal sang ngôn ngữ C++. Đồng thời
kiểm tra và so sánh thời gian thực hiện chương trình giữa hai ngôn ngữ.
Từ những lý do trên tôi đã mạnh dạn trình bày sáng kiến kinh nghiệm:
“Giúp học sinh cài đặt chương trình tối ưu khi giải một số bài tập có sử dụng
thuật toán sắp xếp bằng ngôn ngữ lập trình Pascal và C++ nhằm nâng cao chất
lượng học sinh giỏi môn Tin học ở trường THPT”.
1.2. Mục đích nghiên cứu
Đề tài này nghiên cứu nhằm giúp học sinh giải quyết tốt các bài tập có sử



dụng thuật toán sắp xếp, để khi đứng trước một bài toán cần giải quyết ngoài
việc tìm ra giải thuật để cài đặt chương trình thì học sinh sẽ biết cách so sánh,
đánh giá hiệu quả của thời gian thực hiện chương trình (hay còn gọi là độ phức
tạp của thuật toán) và lựa chọn được thuật toán phù hợp. Đồng thời giúp học
sinh lựa chọn ngôn ngữ lập trình phù hợp với năng lực bản thân, xu thế thời đại
nhằm nâng cao chất lượng học sinh giỏi. Từ đó giúp học sinh dần làm quen với
ngôn ngữ lập trình mới C++.
1.3. Đối tượng nghiên cứu
Sáng kiến kinh nghiệm có đối tượng nghiên cứu là các thuật toán sắp xếp
gồm: sắp xếp lựa chọn, sắp xếp nhanh, sắp xếp bằng phương pháp đếm phân
phối. Các bài toán có sử dụng thuật toán sắp xếp, được nghiên cứu và so sánh ở
nhiều cách làm mỗi cách tương ứng dùng một giải thuật sắp, xét trên các phương
diện như: độ phức tạp, kết quả output, thời gian thực hiện chương trình. Cách
làm tối ưu nhất được cài đặt chương trình bằng ngôn ngữ lập trình Pascal và C+
+.
1.4. Phương pháp nghiên cứu
Để trình bày sáng kiến kinh nghiệm này, tôi đã sử dụng phối kết hợp
nhiều phương pháp như: nghiên cứu tài liệu, thuyết trình, quan sát, điều tra cơ
bản, thực nghiệm so sánh, phân tích kết quả thực nghiệm, … phù hợp với môn
học thuộc lĩnh vực Tin học.
2. Nội dung sáng kiến kinh nghiệm
2.1. Cơ sở lý luận
Nghị quyết hội nghị Trung ương VIII khóa XI đề ra mục tiêu: “Đối với
giáo dục phổ thông tập trung phát triển trí tuệ, thể chất, hình thành phẩm chất,
năng lực công dân, phát hiện và bồi dưỡng năng khiếu, định hướng nghề nghiệp
cho học sinh. Nâng cao chất lượng giáo dục toàn diện, chú trọng giáo dục lý
tưởng truyền thống đạo đức, lối sống, ngoại ngữ, tin học, năng lực và kỹ năng
thực hành, vận dụng kiến thức vào thực tiễn, phát triển khả năng sáng tạo và tự

học, khuyến khích học tập suốt đời".[1]
Yêu cầu cấp bách hiện nay của toàn ngành giáo dục, là xây dựng phương
pháp dạy học hiện đại, đáp ứng được yêu cầu phát triển ngày càng cao của nền
giáo dục hiện đại. Toàn ngành đang ra sức phấn đấu xây dựng chương trình sách
giáo khoa mới, đổi mới phương pháp dạy học theo định hướng hình thành và
phát triển năng lực.
Mục tiêu của môn Tin học trong chương trình giáo dục phổ thông là giúp
học sinh hình thành và phát triển năng lực Tin học.
Đối với môn Tin học, căn cứ vào mục tiêu trên để xác định ra nhiệm vụ cụ
thể của môn học, đổi mới phương pháp dạy học nhằm góp phần thực hiện tốt
mục tiêu của ngành giáo dục trong giai đoạn mới.
Nếu học sinh có thói quen và kỹ năng tốt khi thiết kế và cài đặt chương
trình tối ưu để giải lớp bài tập sắp xếp nói riêng và các bài tập lập trình nói
chung thì chất lượng học sinh giỏi sẽ rất khả quan và đạt kết quả cao trong các kì
thi HSG.
1


2.2. Thực trạng vấn đề trước khi áp dụng sáng kiến kinh nghiệm
2.2.1. Đặc điểm tình hình nhà trường
Trường THPT Đặng Thai Mai được thành lập ngày: 20/08/2001, theo
quyết định số: 2109/QĐ-UB của Chủ tịch UBND Tỉnh Thanh Hoá. Trường nằm
ngay trên đường quốc lộ 1A, thuộc km 12 từ thành phố Thanh Hóa xuống phía
Nam, thuộc địa bàn xã Quảng Bình, huyện Quảng Xương, tỉnh Thanh Hóa, nơi
đa số phụ huynh học sinh làm nông nghiệp và khai thác, đánh bắt hải sản. Điều
kiện kinh tế còn gặp nhiều khó khăn. Các em học sinh ít có điều kiện tiếp xúc
với máy tính ở nhà. Chất lượng đầu vào của học sinh thấp, chủ yếu là học sinh
trung bình, yếu.
Năm học 2017 - 2018 trường có 27 lớp và 1 phòng học thực hành Tin học
có mạng Internet, có lắp đặt máy chiếu. Hiện nay, năm học 2019 - 2020 nhà

trường đã tăng lên 31 lớp, nhưng vẫn chỉ có một phòng thực hành Tin học được
lắp đặt máy chiếu, không kết nối Internet. Cơ sở vật chất chưa đảm bảo cho việc
học bộ môn Tin học của nhà trường.
Môn Tin học là môn học đặc thù có nhiều kiến thức khó. Đặc biệt là lập
trình pascal ở lớp 11 (đây là kiến thức thi học sinh giỏi tỉnh môn Tin học) được
đánh giá là khó và lạc hậu. Hơn nữa, môn học được học sinh, phụ huynh, nhà
trường mặc định là môn phụ, phụ huynh không khuyến khích ủng hộ con yêu
thích đam mê môn học, thậm chí nhiều phụ huynh còn cấm con tham gia đội
tuyển học sinh giỏi môn Tin học, tạo áp lực cho giáo viên và nhà trường để con
được ra khỏi đội tuyển tập trung vào học các môn ôn thi đại học nên việc lựa
chọn và bồi dưỡng học sinh giỏi là vô cùng khó khăn. Thực trạng trên dẫn tới
tâm lý học sinh chán học nên chất lượng học sinh giỏi không cao.
2.2.2. Thực trạng trước khi nghiên cứu
Năm 2014 – 2015 tôi được phân công là giáo viên chính bồi dưỡng học
sinh giỏi tỉnh môn Tin học. Rút kinh nghiệm từ các năm trước đây khi bồi dưỡng
học sinh giỏi, tôi đã chú trọng nhiều hơn đến cải tiến chương trình tối ưu tuy
nhiên hiệu quả mang lại chưa cao.
Đối với lớp bài tập có sử dụng giải thuật sắp xếp, đây là dạng bài tập
không quá khó, là phần học sinh có thể ghi điểm. Tuy nhiên, phần vì giáo viên
chưa có phương pháp giảng dạy phù hợp đối với lớp bài tập này, phần vì học
sinh chủ quan không chú ý đến đặc điểm dữ liệu, giới hạn dữ liệu, không nắm
được đặc trưng nổi bật của từng thuật toán sắp xếp nên khi học sinh gặp dạng
bài tập này thường chỉ dừng lại ở bước đoán nhận có sử dụng thuật toán sắp xếp
rồi nóng vội viết chương trình ngay. Vì vậy, chương trình thường không hiệu
quả dẫn tới kết quả thi học sinh giỏi không cao, không tương xứng với năng lực.
Bảng điểm các lần thi khảo sát chất lượng học sinh giỏi về chuyên đề dãy
con (do tôi tự tổ chức) năm học 2014 – 2015 khi chưa thực hiện đề tài:
Họ tên
Lê Đình Miền
Trần Ngọc Nhật


Lần 1
3/10
5/10

Lần 2
5/10
4/10

Lần 3
6/10
5/10

Lần 4
6/10
6/10
2


Do đó kết quả học sinh giỏi năm 2014 - 2015 có đạt một số kết quả nhất
định, nhưng không cao (1 giải ba, 1 giải khuyến khích).
Bởi vậy, để học sinh đạt được kết quả cao trong kỳ thi học sinh giỏi Tỉnh
cần phải rèn luyện cho các em tuân thủ tốt các bước thiết kế và cài đặt chương
trình tối ưu, điều này không dễ chút nào, đòi hỏi giáo viên phải kiên nhẫn, duy
trì uốn nắn ngay từ khi các em bắt đầu với những bài toán đơn giản và trong suốt
quá trình học cho đến khi các em đi thi.
Trong phạm vi sáng kiến kinh nghiệm của mình, tôi chỉ tập trung nghiên
cứu 3 thuật toán: sắp xếp lựa chọn, sắp xếp nhanh và sắp xếp bằng phương pháp
đếm phân phối. Mặt khác, tôi nghiên cứu và cài đặt song song hai ngôn ngữ lập
trình là Pascal và C++ để giúp học sinh tiếp cận với ngôn ngữ lập trình mới.

Đồng thời, tôi có sử dụng phần mềm Themis để đo và so sánh thời gian thực
hiện chương trình giữa hai ngôn ngữ nhằm giúp học sinh thấy được việc lựa
chọn ngôn ngữ lập trình phù hợp cũng là yếu tố khá quan trọng trong lập trình.
2.3. Giải pháp đã sử dụng để giải quyết vấn đề
2.3.1. Cơ sở lý thuyết
2.3.1.1. Bài toán sắp xếp
Để không mất tính tổng quát, ta sẽ trình bày các thuật toán sắp xếp cho bài
toán sau: Cho dãy gồm n số nguyên a1, a2, ..., an. Hãy sắp xếp thành dãy tăng
không ngặt (dãy không giảm).
Tùy thuộc vào đặc điểm dữ liệu để ta lựa chọn thuật toán sắp xếp hợp lý.
2.3.1.2. Thuật toán sắp xếp lựa chọn
 Ý tưởng:
- So sánh cặp số a1 với a2, nếu số sau nhỏ hơn số trước thì đổi chỗ hai số
đó cho nhau. Làm tương tự với các cặp số a 1 với a3, ..., a1 với an. Khi đó phần tử
nhỏ nhất sẽ đưa lên đầu dãy (tức a1).
- Thực hiện lặp lại với các cặp số: a2 với a3; a2 với a4; ...; a2 với an; ...; an-1
với an.
 Mô phỏng thuật toán bằng Pascal và C++:
Pascal
C++
For i:= 1 to n-1 do
for j:= i+1 to n do
if a[i]>a[j] then
begin
tg:=a[i];
a[i]:=a[j];
a[j]:=tg;
end;

for (i = 1; i < n - 1; i++)

for (j = i + 1; j < n; j++)
if (a[i] > a[j])
{
tg = a[i];
a[i] = a[j];
a[j] = tg;
}

 Độ phức tạp thuật toán là: O(n2)
 Đánh giá ưu điểm, nhược điểm:
 Ưu điểm:
- Code đơn giản, dễ hiểu.
- Sắp xếp được với giá trị phần tử là kiểu số nguyên, kiểu số thực, kiểu kí
3


tự, kiểu xâu.
- Sắp xếp được với phần tử có miền giá trị lớn |ai| ≤ 1018 (nếu ai là kiểu
xâu, sắp xếp được xâu có độ dài rất lớn chỉ phụ thuộc vào dung lượng bộ nhớ
trong).
 Nhược điểm:
2
- Độ phức tạp của thuật toán lớn O(n ).
- Chạy không đủ nhanh (quá 1 giây) với dữ liệu lớn, chỉ áp dụng với số
phần tử n < 104.
2.3.1.3. Thuật toán sắp xếp nhanh
 Ý tưởng:
Chọn một phần tử làm chốt (ở đây ta chọn phần tử ở vị trí giữa). Từ trái
sang tìm phần tử có vị trí i lớn hơn hoặc bằng phần tử chốt, từ phải sang tìm
phần tử có vị trí j bé hơn hoặc bằng phần tử chốt. Nếu i <= j thì đổi chỗ hai phần

tử. Làm cho đến khi i > j. Lúc này sẽ chia ra được 2 nhóm cần sắp xếp. Làm
tương tự như vậy với mỗi nhóm cho đến khi đã sắp xếp hết dãy.
 Mô phỏng thuật toán bằng Pascal và C++:
Pascal
C++
procedure qsort(l,r:longint);
var
i,j,x,y: longint;
begin
i:=l;
j:=r;
x:=a[(l+r) div 2];
repeat
while a[i]while xif not(i>j) then
begin
y:=a[i];
a[i]:=a[j];
a[j]:=y;
inc(i);
j:=j-1;
end;
until i>j;
if lif iend;

void
qsort(a[], l, r)

{
x = a[(l + r) / 2];
i = l;
j = r;
do
{
while (a[i] < x) i++;
while (a[j] > x) j--;
if (i <= j)
{
tg = a[i];
a[i] = a[j];
a[j] = tg;
i++;
j--;
}
}
while (i <= j)
if (l < j) qsort(a, l, j);
if (i < r) qsort(a, i, r);
}

 Độ phức tạp trung bình của thuật toán là: O(nlogn)
 Đánh giá ưu điểm, nhược điểm:
 Ưu điểm:
6
- Thời gian thực hiện nhanh. Áp dụng với số phần tử n ≤ 10 .
- Sắp xếp được với các phần tử là kiểu số nguyên, kiểu số thực, kiểu kí tự,
kiểu xâu.
18

- Sắp xếp được các phần tử với miền giá trị lớn |ai| ≤ 10 (nếu ai là kiểu
4


xâu, sắp xếp được các xâu có độ dài rất lớn chỉ phụ thuộc vào dung lượng bộ
nhớ trong).
 Nhược điểm:
6
- Chạy chậm (quá 1 giây) với số phần tử n > 10 .
- Không ổn định, tùy thuộc vào cách chia thành 2 phần, nếu chia không tốt
độ phức tạp trong trường hợp xấu nhất có thể là O(n 2) (trường hợp này hiếm khi
xảy ra).
2.3.1.4. Thuật toán sắp xếp bằng phương pháp đếm phân phối
 Ý tưởng:
- Khởi tạo giá trị ban đầu cho mảng dem.
- Dùng mảng dem để đếm số lần xuất hiện của số a[i] trong dãy.
- Duyệt i từ giá trị nhỏ nhất (gtmin) của các a[i] đến giá trị lớn nhất
(gtmax) của các a]i]. Duyệt j từ 1 đến dem[i] rồi in ra i.
 Mô phỏng thuật toán bằng Pascal và C++:
Pascal
C++
{khoi tao gia tri mang dem}
fillchar(dem,sizeof(dem),0);
{so lan xuat hien cua a[i]}
for i:=1 to n do
inc(dem[a[i]]);
{in day so}
for i:= gtmin to gtmax do
if j:=1 to dem[i] do
write(i,' ');

//khoi tao gia tri mang dem
for (i = 0; i <= max; i++)
dem[i] = 0;
//so lan xuat hien cua a[i]
for (i = 0; i < n; i++)
dem[a[i]]++;
//in day so
for (i = gtmin; ifor (j=1; j<= dem[i]; j++)
out << i << " ";

 Độ phức tạp của thuật toán là: O(max(n,gtmax)).
 Đánh giá ưu điểm, nhược điểm:
 Ưu điểm:
- Code đơn giản.
- Độ phức tạp phụ thuộc miền giá trị.
- Áp dụng được với dãy có số phần tử lớn n ≤ 108.
 Nhược điểm:
- Chỉ sắp xếp được các phần tử số nguyên hoặc kí tự.
- Phải biết miền giá trị của số nguyên.
7
- Miền giá trị > 10 sẽ không thể tạo được mảng dem để lưu trữ (nghĩa là
chỉ áp dụng được với miền giá trị |ai| ≤ 107).
2.3.2. Biện pháp cài đặt chương trình tối ưu khi giải một số bài tập có sử
dụng thuật toán sắp xếp
Khi phát vấn một bài tập mới mà tôi yêu cầu học sinh làm theo các trình
tự sau:
Bước 1: Xác định bài toán.
Bước 2: Xác định đặc điểm dữ liệu (như số phần tử n, kiểu phần tử là số

thực hay số nguyên, kí tự hay xâu, ...).
Bước 3: Lập bảng so sánh giữa các thuật toán (gồm đánh giá độ phức tạp,
5


thời gian thực hiện).
Bước 4: Nhận xét và lựa chọn thuật toán hiệu quả nhất.
Bước 5: Cài đặt thuật toán đã lựa chọn bằng ngôn ngữ Pascal và C++.
Bước 6: Sử dụng Themis-chấm bài tự động để chấm code (với 10 bộ test
gửi kèm đĩa CD) bằng ngôn ngữ lập trình Pascal và C++. Từ đó nhận thấy tính
hiệu quả giữa hai ngôn ngữ.
Bước 7: Lập trình giải các bài tập có sử dụng thuật toán sắp xếp với thuật
toán hiệu quả nhất bằng ngôn ngữ lập trình Pascal và C++.
2.3.2.1. Bài tập ví dụ có sử dụng thuật toán sắp xếp
Bài tập: Cho một dãy số nguyên a1, a2, ..., an. Hãy đếm số lượng giá trị khác
nhau trong dãy và đưa ra số lần lặp của giá trị xuất hiện nhiều nhất.
Dữ liệu vào: File BAI1.INP gồm 2 dòng:
+ Dòng đầu số nguyên dương N.
+ Dòng thứ hai gồm dãy số nguyên a1, a2, ..., an.
Dữ liệu ra: File BAI1.OUT gồm 2 dòng:
+ Dòng đầu tiên ghi số lượng giá trị khác nhau trong dãy
+ Dòng thứ 2 ghi số lần lặp của giá trị xuất hiện nhiều nhất.
Ví dụ:

BAI1.INP

BAI1.OUT

8
5

67174668
3
Trường hợp 1: Giả sử số phần tử của dãy n <= 106 và giá trị các phần tử là
số nguyên |ai| <= 109.
Dựa vào đặc điểm dữ liệu (số phần tử của dãy n <= 106 và giá trị các phần tử
là số nguyên |ai| <= 109) ta có bảng so sánh sau:
Sắp xếp chọn
Sắp xếp nhanh Sắp xếp đếm phân phối
So sánh
(Selection sort)
(Quicksort)
(Counting sort)
O(109)
Độ phức
O(1012)
O(106log106)
Không thể tạo mảng dem
tạp
để lưu trữ
Thời gian
Quá 1giây
Đạt yêu cầu
Không thực hiện được
Từ bảng trên, ta thấy để giải quyết tối ưu bài toán trên với giới hạn dữ liệu a i
nguyên, |ai| ≤ 109, n ≤ 106, tôi định hướng học sinh chọn thuật toán sắp xếp
nhanh. Cách này học sinh có thể lấy được 100% số điểm.
 Ý tưởng:
B1: Sắp xếp dãy số tăng dần. (các số bằng nhau đứng liên tiếp nhau)
B2: Khởi tạo d:=1 (số phần tử khác nhau), dd:=1 (số phần tử liên tiếp
bằng nhau) và dmax:=1 (số lần lặp của giá trị xuất hiện nhiều nhất). Duyệt i từ

phần tử thứ 2 đến n, nếu 2 số đứng cạnh nhau mà bằng nhau thì tăng dd, ngược
lại khác nhau thì tăng d, đồng thời tìm dmax.
 Độ phức tạp trung bình: O(n*logn)
 Code tham khảo:
Pascal
C++
6


const fo='BAI1.INP';
fi='BAI1.OUT';
var a:array[0..1000000] of
longint;
n,d,dmax,dd,i:longint;
procedure qsort(l,r:
longint);
var i,j,x,y: longint;
begin
i:=l;j:=r;
x:=a[(l+r) div 2];
repeat
while a[i]while xif i<=j then
begin
y:=a[i];
a[i]:=a[j];
a[j]:=y;
inc(i);
j:=j-1;

end;
until i>j;
if lif iend;
begin
assign(input,fo);
reset(input);
assign(output,fi);
rewrite(output);
readln(n);
for i:=1 to n do
read(a[i]);
qsort(1,n);
{Xu ly}
dd:=1;d:=1;dmax:=1;
for i:=2 to n do
if a[i] = a[i-1] then
inc(dd)
else
begin
if dd>dmax then
dmax:=dd;
inc(d);dd:=1;
end;
writeln(d); write(dmax);
close(input);
close(output);
end.

#include <iostream>
#include <fstream>
using namespace std;
long n,d,dmax,dd,i;
void qsort(long a[], long l,
long r)
{
long x,i,j,tg;
x = a[(l + r) / 2];
i = l; j = r;
do
{
while (a[i] < x) i++;
while (a[j] > x) j--;
if (i <= j)
{
tg = a[i];a[i] = a[j];
a[j] = tg; i++; j--;
}
}
while (i <= j);
if (l < j) qsort(a, l, j);
if (i < r) qsort(a, i, r);
}
int main()
{ ifstream fi("BAI1.INP");
ofstream fo("BAI1.OUT");
fi >> n;
//cap phat mang dong
long* a = new long[n+1];

for (i = 1; i <= n; i++)
fi >> a[i];
qsort(a,1, n);
d = 1; dd = 1; dmax = 1;
for (i = 2; i <= n; i++)
{
if (a[i]==a[i-1]) dd++;
else
{
if (dd>dmax) dmax = dd;
d++; dd = 1;
}
}
fo << d << endl << dmax;
//tra lai vung nho dong
delete[] a;
fi.close();
fo.close();
return 0;
}

7


Chú ý: Cách này áp dụng được cả trong trường hợp phần tử của dãy là
kiểu số thực hoặc kiểu kí tự hoặc kiểu xâu. Nếu n <= 103 thì ta thay thủ tục sắp
xếp nhanh bằng thủ tục sắp xếp chọn vẫn lấy được 100% số điểm.
Sử dụng phần mềm Themis. Ta đo thời gian thực hiện chương trình giữa 2
ngôn ngữ Pascal và C++ ở mỗi test cụ thể như sau: (file code và test kèm CD)
Độ phức

tạp

Test01
(giây)

Test02
(giây)

Test03
(giây)

Test04
(giây)

Test05
(giây)

Test06
(giây)

Test07
(giây)

Test08
(giây)

Test09
(giây)

Test10

(giây)

Pascal

0(nlogn)

0.018

0.019

0.018

0.044

0.021

0.019

0.019

0.329

0.332

0.409

C++

0(nlogn)

0.017

0.017

0.014

0.032

0.015

0.015

0.016

0.272

0.294

0.274

Từ bảng trên, ta dễ dàng nhận thấy cùng một thuật toán nhưng sử dụng
ngôn ngữ lập trình C++ để cài đặt thì thời gian thực hiện nhanh hơn khi cài đặt
bằng ngôn ngữ lập trình Pascal.
Trường hợp 2: Giả sử số phần tử của dãy n <= 107 và giá trị các phần tử là
nguyên |ai| <= 106.
Bảng so sánh (số phần tử n <= 107 và giá trị phần tử nguyên |ai| <= 106)
Sắp xếp chọn
Sắp xếp nhanh Sắp xếp đếm phân phối
So sánh
(Selection sort)

(Quicksort)
(Counting sort)
Độ phức
O(1014)
O(107log107)
O(107)
tạp
Thời gian
Quá 1giây
Quá 1 giây
Đạt yêu cầu
Từ bảng trên, ta thấy để giải quyết tối ưu bài toán trên với giới hạn dữ liệu a i
nguyên, |ai| <= 106 , n <= 107, tôi định hướng học sinh chọn thuật toán đếm
phân phối. Cách này học sinh có thể lấy được 100% số điểm.
 Ý tưởng:
B1: Khởi tạo: dem[i]:=0; nmax:=107; d:=0; dmax:=0; (mảng dem với
dem[i] là số lần xuất hiện số nguyên i, i=-nmax...nmax)
B2: Đọc các phần tử a[i] của dãy A và thực hiện đếm phân phối các giá trị
a[i] trong dãy A: dem[a[i]]:=dem[a[i]]+1, đồng thời tìm giá trị lớn nhất max
của dãy A.
8


B3: Duyệt i từ -max..max nếu dem[i]<>0 (tồn tại số i trong dãy) thì tăng d
đồng thời tìm dmax.
 Độ phức tạp trung bình: O(max(n,nmax))
 Code tham khảo

Pascal

const fo='BAI1.INP';
fi='BAI1.OUT';
nmax=10000001;
var
dem:array[-nmax..nmax] of
longint;
a:array [0..10000001] of
longint;
n,d,dmax,i,x,max:longint;
begin
assign(input,fo);
reset(input);
assign(output,fi);
rewrite(output);
fillchar(dem,sizeof(dem),0);
max:=-nmax;
read(n);
for i:=1 to n do
begin
read(a[i]);
inc(dem[a[i]]);
if abs(a[i])> max then
max:=abs(a[i]);
end;
{Xu ly}
d:=0; dmax:=0;
for i:=-max to max do
if dem[i]<>0 then
begin
inc(d);

if dem[i]>dmax then
dmax:=dem[i];
end;
writeln(d);
write(dmax);
close(input);
close(output);
end.

C++

#include <iostream>
#include <fstream>
#include <math.h>
#include <bits/stdc++.h>
using namespace std;
int main()
{ long n,d,dmax,i,max;
ifstream fi("BAI1.INP");
ofstream fo("BAI1.OUT");
fi >> n;
//cap phat mang dong
long* a = new long[n+1];
max = 0;
for (i = 1; i <= n; i++)
{ fi >> a[i];
if (abs(a[i]) > max)
max = abs(a[i]);
}
long* demd=new long[max + 1];

long* dema=new long[max + 1];
for (i = 0; i <= max; i++)
demd[i] = dema[i] = 0;
for (i = 1; i <= n; i++)
{ if (a[i] >= 0)
demd[a[i]]++;
else
dema[abs(a[i])]++;
}
//xu ly
d=dmax=0;
for (i = 0; i <= max; i++)
{ if (demd[i] > 0) d++;
if (dema[i] > 0) d++;
if (demd[i] > dmax)
dmax = demd[i];
if (dema[i] > dmax)
dmax = dema[i];
}
fo << d << endl << dmax;
delete[] a; delete[] demd;
delete[] dema;
fi.close();
fo.close();
return 0;
}

9

Chú ý: Do trong C++ không hỗ trợ truy xuất mảng có chỉ số âm nên ta tạo
thêm mảng để đánh dấu số âm và lọc ra hai mảng số âm (dema), số dương
(demd) ngay từ lúc đếm.
Sử dụng phần mềm Themis. Ta đo thời gian thực hiện chương trình giữa 2
ngôn ngữ Pascal và C++ ở mỗi test cụ thể như sau: (file code và test kèm CD)

Pascal
C++

Độ phức
tạp
0(max(n,n
max))
0(max(n,n
max))

Test01
(giây)

Test02
(giây)

Test03
(giây)

Test04
(giây)

Test05
(giây)

Test06
(giây)

Test07
(giây)

Test08
(giây)

Test09
(giây)

Test10
(giây)

0.065

0.067

0.060

0.049

0.072

0.052

0.216

0.998

0.777

0.919

0.024

0.014

0.015

0.015

0.060

0.015

0.121

0.685

0.670

0.912

Từ bảng trên, ta dễ dàng nhận thấy cùng một thuật toán nhưng sử dụng
ngôn ngữ lập trình C++ để cài đặt thì thời gian thực hiện nhanh hơn khi cài đặt
bằng ngôn ngữ lập trình Pascal.
Từ hai trường hợp phân tích ở trên, ta nhận thấy với đặc điểm dữ liệu như:

số phần tử của dãy nhỏ N < 106, giá trị phần tử lớn 107 < |ai| ≤ 1018 (có thể kiểu
số nguyên, số thực, kiểu kí tự, kiểu xâu) thì chọn thuật toán sắp xếp nhanh
(hoặc sắp xếp lựa chọn nếu N ≤ 103). Còn đặc điểm dữ liệu như: số phần tử của
dãy lớn N ≤ 107, giá trị phần tử nhỏ ≤ 106 (chỉ có thể là kiểu số nguyên hoặc kí
tự) thì nên lựa chọn thuật toán đếm phân phối.
2.3.2.2. Bài tập áp dụng
2.3.2.2.1. Một số bài tập sử dụng thuật toán sắp xếp nhanh
Bài 1: Đếm từ
Từ là một dãy gồm các chữ cái thường 'a'..'z' đứng liền nhau không chứa
dấu cách.
Cho xâu s gồm các chữ cái thường 'a' .. 'z' và dấu cách. Mỗi từ trong xâu s
dài không quá 10 kí tự.
Yêu cầu: Đếm số lượng từ khác nhau nhận được từ xâu s.
Dữ liệu vào: Đọc từ tệp văn bản DEMTU.INP gồm một xâu s có độ dài không
vượt quá 106 (có ít nhất 1 từ).
Dữ liệu ra: Ghi ra tệp văn bản DEMTU.OUT gồm duy nhất một số là kết quả
cần tìm.
Ví dụ:
DEMTU.INP
DEMTU.OUT
roi nhu bong bong
3
10


Chú ý: Dùng mảng A để lưu các từ trong xâu đã cho.
Ta có bảng so sánh sau(số từ < 106 và mỗi từ là một xâu |ai| <= 10)
Sắp xếp chọn
Sắp xếp nhanh Sắp xếp đếm phân phối
So sánh

(Selection sort)
(Quicksort)
(Counting sort)
O(109)
Độ phức
Không thể tạo mảng dem
O(1012)
O(106log106)
tạp
để lưu trữ (vì giá trị phần
tử kiểu xâu)
Thời gian
Quá 1 giây
Đạt yêu cầu
Không thực hiện được
Từ bảng trên, ta thấy để giải quyết tối ưu bài toán trên với giới hạn dữ liệu ai
là kiểu xâu, |ai| <= 10 , n < 106, tôi định hướng học sinh chọn thuật toán sắp
xếp nhanh.
 Độ phức tạp trung bình: O(nlogn)
 Ý tưởng:
B1: Lưu các từ trong xâu S vào mảng A.
B2: Sắp xếp mảng A tăng dần (khi đó những từ giống nhau liên tiếp nhau)
B3: Duyệt mảng A để đếm từ khác nhau.
 Code tham khảo

Pascal

const fo='DEMTU.INP';
fi='DEMTU.OUT';
var i,n,d,k,dem:longint;

s,s1:ansistring;
a:array[0..1000000]of

C++

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
using namespace std;
void
qsort(vector<string>&
str, long l, long r)
ansistring;
procedure qsort(l,r: longint); { long i,j; string x,tg;
i = l;
var
j = r;
i,j: longint;
x = str[(l + r) / 2];
x,y:ansistring;
do
begin
{
i:=l;
while (str[i] < x) i++;
j:=r;
while
(str[j] > x) j--;
x:=a[(l+r) div 2];

if (i <= j)
repeat
{
while a[i]tg = str[i];
inc(i);
str[i] = str[j];
while xstr[j] = tg;
dec(j);
i++;
if not(i>j) then
j--;
begin
}
y:=a[i];
}
a[i]:=a[j];
while
(i < j);
a[j]:=y;
if (linc(i);
if (ij:=j-1;
}
end;

11

until i>j;
if lif i
int main()
qsort(l,j); {
qsort(i,r);
ifstream fi("DEMTU.INP");
end;
ofstream fo("DEMTU.OUT");
vector<string> str;
begin
string a = "";
assign(input,fo);
char ch;
reset(input);
while (!fi.eof())
assign(output,fi);
{
rewrite(output);
fi.get(ch);
readln(s);
if (ch == ' ')
s:=s+' ';
{
d:=0; k:=0;
if (a.length())
for i:=1 to length(s) do
str.push_back(a);

if s[i] in ['a'..'z'] then
a = "";
s1:=s1+s[i]
}
else
else
if s1<>'' then
{
begin
a += ch;
inc(k);
}
a[k]:=s1;
}
s1:='';
if (!a.empty())
end;
a.erase(a.length()-1,1);
qsort(1,k);
str.push_back(a);
dem:=1;
qsort(str, 0, str.size()
for i:=1 to k-1 do
- 1);
if a[i]<>a[i+1] then
long dem = 1;
inc(dem);
for (long i = 0; i <
write(dem);
str.size() - 1; i++)

close(input);
{
close(output);
if (str[i] != str[i
end.
+ 1]) dem++;
}
fo << dem;
fi.close();fo.close();
return 0;
}

Bài 2: Dãy con
Cho dãy gồm N số a1, a2, ..., an. Hãy tìm dãy con liên tiếp dài nhất có tổng
bằng 0.
Dữ liệu vào: Từ tệp DAYCON.INP gồm:
+ Dòng đầu tiên chứa số nguyên dương N (N≤105).
+ Dòng thứ 2 chứa N số a1, a2, ..., an (|ai|≤109).
Dữ liệu ra: Ghi ra file văn bản DAYCON.OUT gồm hai dòng:
+ Dòng đầu tiên ghi độ dài dãy con liên tiếp dài nhất có tổng bằng 0.
+ Dòng thứ 2 ghi các giá trị của dãy con thỏa mãn (nếu nhiều dãy con
thỏa mãn thì ghi ra dãy con đầu tiên, nếu không có dãy thỏa mãn ghi NO).
Ví dụ:
12


DAYCON.INP
10
3 0 2 1 -2 0 3 -2 1 -2

DAYCON.OUT
5
1 -2 0 3 -2

Chú ý: Tạo mảng S với S[i]:=a[1]+a[2]+...+A[i].
Bảng so sánh (số phần tử ≤ 105 và giá trị các phần tử là xâu |si| ≤ 1014)
Sắp xếp chọn
Sắp xếp nhanh Sắp xếp đếm phân phối
So sánh
(Selection sort)
(Quicksort)
(Counting sort)
O(109)
Độ phức
O(1010)
O(105log105)
Không thể tạo mảng dem
tạp
để lưu trữ
Thời gian
Quá 1 giây
Đạt yêu cầu
Không thực hiện được
Từ bảng trên, ta thấy để giải quyết tối ưu bài toán trên với giới hạn dữ liệu si
là |si|<=1015, n<105, tôi định hướng học sinh chọn thuật toán sắp xếp nhanh.
 Ý tưởng:
B1: Tạo mảng S với S[i]:=a[1]+a[2]+...+A[i]. (Ta có dãy con từ i đến j
=0 nếu S[j]-S[i-1]=0 hay S[j]=S[i-1])
B2: Sắp xếp mảng S (Lưu mảng chỉ số vào mảng vt, khi sắp xếp mảng S
đồng thời lưu luôn chỉ số ban đầu của S).

B3: Tìm độ dài (dd) dãy con liên tiếp dài nhất có tổng bằng 0. Tìm chỉ số
(cs) đầu của dãy thỏa mãn.
 Code tham khảo

Pascal

C++

const fo='DAYCON.INP';
#include <iostream>
fi='DAYCON.OUT';
#include <stdint.h>
nmax=1000000000000000;
#include <vector>
var
a,vt:array[0..100000] of #include <fstream>
longint;
using namespace std;
s:array[0..100000] of void qsort(vector<long>& vt,
int64;
vector<int64_t>& s, long l,
n,i,j,dd,cs:longint;
long r)
min,max:int64;
{ int64_t x = s[(l + r) / 2];
procedure sort(l,r: longint);
long i = l;long j = r;
var
do
i,j: longint;

{ while (s[i] < x) i++;
x,y,tg:int64;
while (s[j] > x) j--;
begin
if (i <= j)
i:=l;
{
j:=r;
int64_t tg1 = s[i];
x:=s[(l+r) div 2];
s[i]=s[j]; s[j]=tg1;
repeat
long tg2 = vt[i];
while s[i]vt[i] = vt[j];
inc(i);
vt[j] = tg2;
while xi++; j--;
dec(j);
}
if not(i>j) then
}

13


begin
y:=s[i];
s[i]:=s[j];

s[j]:=y;
tg:=vt[i];
vt[i]:=vt[j];
vt[j]:=tg;
inc(i);
j:=j-1;
end;
until i>j;
if lif iend;
function maxx(a,b:int64):int64;
begin
if a>b then exit(a)
else exit(b);
end;
function minn(a,b:int64):int64;
begin
if a>b then exit(b)
else exit(a);
end;
begin
assign(input,fo);
reset(input);
assign(output,fi);
rewrite(output); s[0]:=0;
read(n);
for i:=1 to n do
begin
read(a[i]);

s[i]:= s[i-1]+a[i];
vt[i]:=i;
end;
sort(1,n);
{xu li}
min:=nmax; dd:=0; max:=-nmax;
for i:=1 to n do
if (s[i]=s[i-1]) then
begin
if (maxx(vt[i],vt[i-1])>max)
then
max:=maxx(vt[i],vt[i-1]);
if(minn(vt[i],vt[i-1])then min:=minn(vt[i],vt[i-1]);
end
else
begin
if max-min>dd then

while (i <= j);
if (l < j) qsort(vt,s,l,j);
if (i < r) qsort(vt,s,i,r);
}
long maxx(long a, long b)
{
if (a > b) return a;
else return b;
}
long minn(long a, long b)
{

if (a > b) return b;
else return a;
}
int main()
{
ifstream fi("DAYCON.INP");
ofstream fo("DAYCON.OUT");
long n;
fi >> n;
vector<long> a(n + 1);
vector<int64_t> s(n + 1);
vector<long> vt(n + 1);
s[0] = 0;
for (long i=1; i<= n; i++)
{
fi >> a[i];
s[i] = s[i - 1] + a[i];
vt[i] = i;
}
qsort(vt, s, 1, n);
long min, max, d, cs;
min = n; max = 0;
d = 0;
for (long i=1; i<=n; i++)
{
if (s[i] == s[i - 1])
{
if (maxx(vt[i],vt[i1])> max)
max=maxx(vt[i],vt[i-1]);
if (minn(vt[i], vt[i 1]) < min)

min = minn(vt[i], vt[i 1]);
}
else
{ if (max - min > d)
{ d = max - min;
cs = min;

14


begin
}
dd := max - min;
if (max - min == d
cs := min;
&& min < cs)
end;
cs = min; min = n;
if (max-min=dd) and
max = 0;
(min}
min:=nmax; max:=-nmax;
}
end;
if (d == 0) fo << "NO";
if dd=0 then write('NO')
else
else
{ fo << d << endl;

begin
for (long i = cs + 1;
writeln(dd);
i <= cs + d; i++)
for i:=cs+1 to cs+dd do
fo << a[i] << ' ';
write(a[i],' ');
}
end;
fi.close(); fo.close();
close(input); close(output);
return 0;
end.
}

2.3.2.2.2. Một số bài tập sử dụng thuật toán đếm phân phối
Bài 1: Bán hàng
Tại một điểm bán hàng tự động, mỗi loại hàng được gán tương ứng với
một số nguyên dương gọi là mã hàng, hai loại hàng khác nhau có mã hàng khác
nhau. Mỗi lần khách mua hàng, máy chỉ bán một loại hàng với số lượng là 1 sản
phẩm và ghi vào nhật kí của máy mã loại hàng đã bán. Sau khi kết thúc một đợt
bán hàng, nhật kí bán hàng của máy là một dãy số nguyên dương. Người quản lí
cần thống kê xem loại hàng nào đã được máy bán nhiều nhất, số lượng hàng loại
đó đã bán là bao nhiêu? Bạn hãy viết chương trình giúp người quản lý tìm loại
hàng đó.
Dữ liệu vào: Vào từ file văn bản DEMHANG.INP:
- Dòng đầu tiên ghi số nguyên dương N (N≤107) là số lượng hàng đã bán.
- N dòng tiếp theo mỗi dòng ghi một số nguyên dương là mã loại hàng đã
bán trong nhật kí của máy. Giá trị các số nguyên dương không vượt quá 106.
Kết quả ra: Đưa ra file văn bản DEMHANG.OUT chỉ một dòng duy nhất ghi

mã loại hàng đã bán nhiều nhất và số lượng hàng loại đó mà máy đã bán, hai giá
trị này cách nhau một ký tự trống. Nếu như có nhiều loại hàng có cùng số lượng
bán nhiều nhất thì in ra mã loại hàng có giá trị bé nhất.
Ví dụ:
DEMHANG.INP
DEMHANG.OUT
11
2 4
12232452676
Bảng so sánh (số phần tử ≤ 107 và giá trị các phần tử |ai| ≤ 106)
Sắp xếp chọn
Sắp xếp nhanh
Đếm phân phối
So sánh
(Selection sort)
(Quicksort)
(Counting sort)
Độ phức
O(1014)
O(107log107)
O(107)
tạp
Thời gian
Quá 1 giây
Quá 1 giây
Đạt yêu cầu
15


Ý

tưởng:
Tương tự trường hợp 2 ở bài tập ví dụ
 Code tham khảo:
Pascal
program dem_hang;
const fi='DEMHANG.INP';
fo='DEMHANG.OUT';
maxn=10000000;
maxdem=1000000;
var
a:array[0..maxn] of
longint;
dem:array[0..maxdem] of
longint;
n,i,j,max,luu:longint;
begin
assign(input,fi);
reset(input);
assign(output,fo);
rewrite(output); read(n);
fillchar(dem,sizeof(dem),0);
for i:=1 to n do
begin
read(a[i]);
inc(dem[a[i]]);
end;
{xu li}
max:=0; luu:=0;
for i:=1 to maxdem do

if dem[i]>max then
begin
max:=dem[i]; luu:=i;
end;
write(luu,' ',max);
close(input); close(output);
end.

C++

#include <iostream>
#include <fstream>
using namespace std;
int main()
{ ifstream fi("DEMHANG.INP");
ofstream fo("DEMHANG.OUT");
long n;
fi >> n;
long* a = new long[n];
long maxa = 0;
for (long i=0; i{fi >> a[i];
if(a[i]>maxa) maxa=a[i];
}
long*dem=new long[maxa+1];
for (long i=1;i<=maxa; i++)
dem[i] = 0;
for (long i=0; idem[a[i]]++;
long max = 0; long luu = 0;

for (long i=1;i<=maxa;i++)
if (dem[i] > max)
{
max = dem[i];
luu = i;
}
fo << luu << ' ' << max;
delete[] a; delete[] dem;
fi.close(); fo.close();
return 0;
}

Bài 2: Taxi (Đề học sinh giỏi Tin học 2017 -2018 tỉnh Thanh Hóa)
Trong dịp ngỉ hè các bạn học sinh lớp 12 dự định tổ chức dã ngoại đến
biển sầm sơn và sẽ đi bằng taxi. Các bạn được chia thành n nhóm, nhóm thứ i
gồm si bạn (1 ≤ si ≤ 4) và mỗi chiếc taxi chở tối đa 4 hành khách. Vậy lớp 12 cần
thuê ít nhất bao nhiêu chiếc taxi để chở các nhóm đi, với điều kiện là các bạn
trong nhóm phải ngồi chung taxi (một taxi có thể trở một nhóm trở lên).
Dữ liệu vào: Từ tệp BAI3.INP gồm:
- Dòng đầu chứa số nguyên dương n (1 ≤ n ≤ 105) (số lượng các nhóm học
sinh).
- Dòng số 2 chứa dãy số nguyên s1, s2, ..., sn (1 ≤ si ≤ 4). Các số nguyên
cách nhau bởi dấu cách với các si là số học sinh trong nhóm thứ i.
16


Dữ liệu ra: Ghi ra file văn bản BAI3.OUT là một số nguyên duy nhất là số
lượng tối thiểu xe taxi cần thiết để trở tất cả học sinh đến nơi.
Ví dụ:

BAI3.INP

BAI3.OUT

5
4
12433
 Ý tưởng:
Ở bài này, với dữ liệu cho của đề bài (1 ≤ n ≤ 105) và (1 ≤ si ≤ 4) thì ta
dùng sắp xếp nhanh hay đếm phân phối đều lấy được 100% số điểm. Do giá trị si
(1 ≤ si ≤ 4) nhỏ nên dùng phương pháp đếm phân phối đơn giản và tối ưu hơn.
B1: Tạo mảng dem với dem[i] là số nhóm có i học sinh.
B2: Xét tất cả các trường hợp để tìm số lượng tối thiểu xe taxi.
 Code tham khảo:

Pascal

const fi='bai3.inp';
fo='bai3.out';
var d:array[1..4] of longint;
n,x,dem,du,i:longint;
begin
assign(input,fi);
reset(input);
assign(output,fo);
rewrite(output);
readln(n);
fillchar(d,sizeof(d),0);
for i:=1 to n do
begin

read(x); inc(d[x]);
end;
dem:=d[4]+d[3];
if d[3]>=d[1] then d[1]:=0
else d[1]:=d[1]-d[3];
dem:=dem+d[2] div 2;
if d[2] mod 2=0 then du:=0
else du:=2;
if d[1]=0 then
if du<>0 then inc(dem);
if d[1]<>0 then
begin
dem:=dem+d[1] div 4;
du:=du+d[1] mod 4;
if du>0 then
if du<=4 then inc(dem)
else dem:=dem+2;
end;
write(dem);
close(input); close(output);
end.

C++

#include <iostream>
#include <fstream>
using namespace std;
int main()
{
ifstream fi("BAI3.INP");

ofstream fo("BAI3.OUT");
long n;long d[5];int x;
fi >> n;
for (int i=1; i<=4; i++)
d[i] = 0;
for (long i=0; i{
fi >> x; d[x]++;
}
long dem = d[4] + d[3];
long du;
if (d[3] >= d[1])
d[1] = 0;
else d[1] -= d[3];
dem += d[2] / 2;
du = (d[2] % 2) * 2;
if (d[1] == 0)
if (du != 0) dem++;
if (d[1] != 0)
{
dem += d[1] / 4;
du += d[1] % 4;
if (du > 0)
if (du<4) dem++;
else dem += 2;
}
fo << dem;
fi.close(); fo.close();
return 0;
}

17


2.4. Hiệu quả của sáng kiến kinh nghiệm
Với cách làm như vậy đã rèn luyện kỹ năng lập trình cho các học sinh
tham gia học đội tuyển, các em cũng có thói quen tối ưu hóa thuật toán để cài
đặt chương trình tối ưu, để ý đến thời gian chạy chương trình hơn.
Ngoài ra, học sinh nhận thấy được tầm quan trọng của việc lựa chọn ngôn
ngữ lập để cài đặt chương trình sao cho hiệu quả nhất.
Bảng điểm thi khảo sát chất lượng học sinh giỏi về chuyên đề sắp xếp
(Chất lượng học sinh dần dần tiến bộ)
Năm học
Họ và tên
Lần 1
Lần 2
Lần 3
Lần 4
Lê Trọng Việt
7/10
8/10
10/10
10/10
2017 - 2018
Lương Mai Trinh
5/10
7/10
9/10
8/10
Lê Văn Thụ

6/10
6/10
9/10
9/10
2019 - 2020
Lê Văn Hòa
5/10
5/10
8/10
9/10
Năm 2017 - 2018 tôi tiếp tục làm công tác bồi dưỡng học sinh giỏi tỉnh
môn tin học cho nhà trường. Năm học 2019 – 2020 tôi được phân công dạy hỗ
trợ đồng nghiệp trong công tác bồi dưỡng học sinh giỏi Tin. Cả hai năm tôi đều
áp dụng phương pháp này khi giảng dạy tuy rất dày công nhưng kết quả mang
lại rất tốt. Cụ thể năm 2017 - 2018, 100% học sinh đạt giải (1 giải nhì, 1 giải ba).
Năm học 2019 – 2020 sở không tổ chức thi học sinh giỏi tỉnh (vì dịch Covid19), tuy nhiên học sinh có sự tiến bộ rõ rệt qua các lần khảo sát của nhà trường
và liên trường.
Như vậy, rõ ràng việc giúp học sinh cài đặt chương trình tối ưu, hiệu quả
đem lại là rất tốt, tránh được việc học sinh mất điểm vì những lí do đáng tiếc
trong kì thi học sinh giỏi THPT môn Tin học.
3. Kết luận và kiến nghị
3.1. Kết luận
Bài tập có sử dụng thuật toán sắp xếp rất nhiều và đa dạng, nhưng trong
sáng kiến kinh nghiệm trên tôi đã giúp học sinh nhận dạng được một số bài tập,
so sánh để đưa ra cách giải tối ưu để lấy được điểm tối đa, các cách giải tối ưu
được trình bày bằng hai ngôn ngữ lập trình Pascal và C++. Từ đó áp dụng làm
các bài tập khác nhạy bén hơn nhằm nâng cao chất lượng học sinh giỏi và mang
lại kết quả cao hơn trong các kì thi học sinh giỏi Tin.
Ngoài ra, tôi cài đặt chương trình trên ngôn ngữ lập trình C++ để học sinh
tiếp cận với ngôn ngữ mới và minh chứng được việc lựa chọn ngôn ngữ lập trình

cũng là một yếu tố khá quan trọng trong việc học lập trình.
Đề tài này đã được tôi áp dụng giảng dạy cho đội tuyển học sinh giỏi môn
Tin học năm học 2017 - 2018 và năm học 2019 - 2020 của trường tôi. Đồng thời
tôi đã trao đổi, chia sẽ với một số giáo viên chuyên bồi dưỡng học sinh giỏi của
một số trường trung học phổ thông của tỉnh Thanh Hóa và đạt được kết quả tốt.
Tôi nhận thấy học sinh hứng thú, tích cực hơn trong việc học lập trình và kết quả
rất khả quan trong các kỳ thi học sinh giỏi môn Tin học. Bên cạnh đó, việc tôi
giới thiệu ngôn ngữ lập trình mới giúp học sinh đam mê, tìm tòi và tự học thêm
ngôn ngữ lập trình mới phục vụ cho việc học trong tương lai.
18


Tất cả file code, test, đề bài tập được thực hiện trong sáng kiến kinh
nghiệm tôi đã gửi kèm theo đĩa CD.
Trong khuôn khổ đề tài, với kinh nghiệm ít ỏi và vốn kiến thức có hạn nên
đề tài không tránh khỏi những thiếu sót, tôi rất mong được sự góp ý, trao đổi từ
các đồng nghiệp để đề tài được hoàn thiện hơn.
3.2. Kiến nghị
Đối với nhà trường, cần có kế hoạch cụ thể để thực hiện (lồng ghép trong
hoạt động ngoại khóa, sinh hoạt tập thể của học sinh, ...) việc giáo dục cho học
sinh nhận thức được tầm quan trọng của bộ môn Tin học đối bản thân và xã hội
hiện đại ngày nay. Từ đó tạo hứng thú và đam mê cho những học sinh có tố chất
về lĩnh vực Tin học phát triển nhằm cung cấp nguồn nhân lực công nghệ thông
tin trí tuệ cao cho xã hội.
Đối với Sở giáo dục và đào tạo, nên tổ chức tập huấn cho giáo viên Tin
học tiếp cận những ngôn ngữ lập trình mới (C++, Python, ...) đáp ứng yêu cầu
của chương trình giáo dục hiện đại.
Trên đây chỉ là những kiến nghị mang tính chủ quan của tôi, nhưng cũng
rất mong được các cấp có thẩm quyền xem xét và sự góp ý của các đồng nghiệp.
XÁC NHẬN CỦA

THỦ TRƯỞNG ĐƠN VỊ

Thanh Hóa, ngày 30 tháng 06 năm 2020
Tôi xin cam đoan đây là SKKN của mình viết,
không sao chép nội dung của người khác.

Hoàng Thị Mai

19


TÀI LIỆU THAM KHẢO
[1] Đảng Cộng sản Việt Nam, Ban chấp hành trung ương khóa XI (2013), nghị
quyết số 29-NQ/TW ngày 04/11/2013 về đổi mới căn bản toàn diện giáo dục và
đào tạo.
[2] Giáo trình Giải thuật, Th.s. Nguyễn Văn Linh, Đại học Cần Thơ (2003).
[3] Giáo trình Cấu trúc dữ liệu và giải thuật, Trần Hạnh Nhi, Dương Anh Đức,
NXB Đại học quốc gia TPHCM.
[4] Tài liệu chuyên Tin học quyển 1, Hồ Sỹ Đàm (chủ biên), Đỗ Đức Đông, Lê
Minh Hoàng, Nguyễn Thanh Tùng, nhà xuất bản giáo dục Việt Nam.
[5] Sáng tạo trong thuật toán và lập trình tập 1, Nguyễn Xuân Huy, nhà xuất
bản Thông tin và truyền thông.

20


DANH MỤC
SÁNG KIẾN KINH NGHIỆM ĐÃ ĐƯỢC HỘI ĐỒNG SÁNG KIẾN KINH
NGHIỆM NGÀNH GIÁO DỤC VÀ ĐÀO TẠO HUYỆN, TỈNH VÀ CÁC
CẤP CAO HƠN XẾP LOẠI TỪ C TRỞ LÊN

Họ và tên tác giả: Hoàng Thị Mai
Chức vụ và đơn vị công tác: Giáo viên, Trường THPT Đặng Thai Mai

TT

Tên đề tài SKKN

Cấp đánh giá xếp
loại

Kết quả
đánh giá
xếp loại
(A, B, hoặc C)

1.

Giúp học sinh lựa chọn
và cài đặt chương trình
tối ưu khi giải một số
Sở Giáo dục và
dạng bài tập về dãy con
Đào tạoThanh Hóa
nhằm nâng cao chất
lượng học sinh giỏi môn
Tin học ở trường THPT

B

Năm học

đánh giá
xếp loại

2015-2016

21