SKKN Giúp học sinh rèn luyện và nâng cao kỹ năng lập trình qua việc lựa chọn thuật toán tối ưu phù hợp với dữ liệu bài toán

 trị của i (vị trí của x trong mảng A). 
 Nếu A[i] != x thì sang bước 3. 
3. Gán i = i + 1: 
 Nếu i == n (tức hết mảng) thì dừng lại và trả kết quả là -1 (không tìm thấy x). 
 Nếu i < n thì quay lại bước 2. 
Hàm tìm kiếm tuần tự được viết như sau: 
int sequentialsearch(int A[], int n, int x) 
{ for(int i=0;i<n;i++) 
 if (A[i]==x) 
 return i; //đưa ra vị trí i khi tìm thấy 
 return -1; //duyệt hết mảng, không tìm thấy x 
33 
Nhận xét: thuật toán tìm kiếm tuần tự đơn giản, dễ cài đặt, có độ phức tạp O(n) 
Tìm kiếm nhị phân 
Tìm kiếm nhị phân (binary search) hay còn một số tên gọi khác nữa như tìm 
kiếm nửa khoảng (half-interval search), tìm kiếm logarit (logarithmic search), chặt 
nhị phân (binary chop) là thuật toán tìm kiếm dựa trên việc chia đôi khoảng đang xét 
sau mỗi lần lặp, sau đó xét tiếp trong nửa khoảng có khả năng chứa giá trị cần tìm, 
cứ như vậy cho đến khi không chia đôi khoảng được nữa. Thuật toán tìm kiếm nhị 
phân chỉ áp dụng được cho danh sách đã có thứ tự hay đã được sắp xếp. 
Do cách tìm kiếm chia đôi khoảng này, sau mỗi lần lặp, khoảng đang xét lại 
được chia đôi, và tiếp tục khoảng tiếp lại chia đôi khoảng đã được chia trước đó. Do 
đó, độ phức tạp thời gian của thuật toán này sẽ là O(log(n)), tốt hơn rất rất nhiều so 
với tìm kiếm tuần tự. 
Cho một mảng A có n phần tử bắt đầu từ vị trí 0, mảng A được sắp xếp tăng 
dần. Để tìm phần tử có giá trị x trong mảng A chúng ta sẽ cài đặt thuật toán tìm kiếm 
nhị phân như sau: 
1. Gán left = 0, right = n – 1. 
2. Gán mid = (left + right) / 2 (lấy phần nguyên, đây là phần tử chính giữa của 
khoảng hiện tại) 
 Nếu như A[mid] == x: 
 Dừng lại và trả về giá trị của mid (chính là vị trí của x trong mảng A). 
 Nếu như A[mid] > x (có thể x nằm trong nửa khoảng trước): 
 right = mid – 1 // giới hạn khoảng tìm kiếm lại là nửa khoảng trước 
 Nếu như A[mid] < x (có thể x nằm trong nửa khoảng sau): 
 left = mid + 1 // giới hạn khoảng tìm kiếm lại là nửa khoảng sau 
3. Nếu left <= right: 
 Đúng thì quay lại bước 2 (còn chia đôi được). 
 Sai thì dừng và trả về kết quả -1 (không tìm thấy x) 
int BinarySearch(int A[], int n, int x) 
 { int left = 0; 
 int right = n - 1; 
 int mid; 
 while (left <= right) 
 { 
 mid = (left + right) / 2; 
34 
 if (A[mid] == x) 
 return mid; // tìm thấy x, trả về mid là vị trí 
của x trong mảng A 
 if (A[mid] > x) 
 right = mid - 1; // Giới hạn khoảng tìm kiếm lại 
là nửa khoảng trước 
 else if (A[mid] < x) 
 left = mid + 1; // Giới hạn khoảng tìm kiếm lại 
là nửa khoảng sau } 
 return -1; // không tìm thấy x 
 } 
Nhận xét: thuật toán tìm kiếm nhị phân được sử dụng khi dãy số đã sắp xếp lúc 
đó độ phức tạp là O(log(n)). Trong trường hợp dãy chưa sắp xếp, thì phải sắp xếp 
rồi mới sử dụng được tìm kiếm nhị phân. Lúc này độ phức tạp phụ thuộc vào độ 
phức tạp của thuật toán sắp xếp đã sử dụng trước tìm kiếm. 
Kết luận: 
So sánh Tìm kiếm tuần tự Tìm kiếm nhị phân 
Độ phức tạp O(n) O(logn) 
Đặc điểm Code đơn giản, dễ hiểu Code phức tạp hơn 
Trường hợp nên sử dụng 
(thời gian thực hiện 1s) 
- Dãy chưa sắp xếp 
- tìm kiếm số lượng phần 
tử khoảng n≤ 107 (giới 
hạn của mảng) 
- Dãy đã sắp xếp 
- Nếu dãy chưa sắp xếp 
thì phụ thuộc thuật toán 
sắp xếp sử dụng. 
3.2.3.2. Bài tập ví dụ 
Bài 1: Tìm kiếm nhị phân6 
Cho dãy số a(n) nguyên dương. Tìm phần tử trong dãy a(n) có giá trị bằng x 
Dữ liệu: Dòng đầu ghi số nguyên dương n (n≤105) 
Dòng 2 ghi n số nguyên dương ai (ai ≤1018) 
Dòng 3 ghi số nguyên dương T (T ≤105) 
T dòng kế tiếp, mỗi dòng ghi số nguyên dương x 
6 Bài SB02B trên  
35 
Kết quả: ghi ra T dòng, dòng thứ i ghi Y nếu trong dãy a(n) tồn tại phần tử x, 
nếu không tồn tại ghi N 
Giới hạn: - 60% số test với 1 ≤ N ≤ 103. 
 - 40% số test với 103 < N ≤ 105. 
Bước 1: Xác định bài toán 
- Input: dãy số a(n) nguyên dương (n≤105, ai ≤1018), T test (T ≤105), mỗi test 
một số nguyên dương x 
- Output: ghi ra T dòng, dòng thứ i ghi Y nếu trong dãy a(n) tồn tại phần tử x, 
nếu không tồn tại ghi N 
Bước 2: Đặc điểm dữ liệu 
Dữ liệu vào gồm dãy số a(n) nguyên dương (n≤105, ai ≤1018) và T test (T≤105), 
mỗi test là một số nguyên dương x 
Bước 3: Các cách giải có thể lựa chọn 
Đây là bài toán tìm kiếm đơn giản, đa số học sinh sẽ dùng cách tìm kiếm tuần 
tự. Tuy nhiên vì dữ liệu khá lớn (n≤105 ,T ≤105) nên ta xét các cách giải sau: 
- Cách 1: sử dụng thuật toán tìm kiếm tuần tự thì mỗi T độ phức tạp là O(n) 
=> Độ phức tạp toàn bộ chương trình là O(T*n) 
- Cách 2: - sắp xếp dãy tăng dần 
 - Tìm kiếm nhị phân cho mỗi T với T ≤105 
Vì dãy số a(n) nguyên dương (n≤105, ai ≤1018), nên ta chọn thuật toán sắp xếp 
nhanh là phù hợp. Độ phức tạp sẽ là O(nlogn) với n≤105 
Tìm kiếm nhị phân cho mỗi T với T ≤105 có độ phức tạp là O(Tlogn) 
 Độ phức tạp của chương trình là O(max(nlogn,Tlogn)) ≈O(nlogn) (vì n ≈ T) 
Bước 4: Đánh giá, lựa chọn thuật toán 
Như vậy theo bảng ước lượng (*) : 
Nếu sử dụng cách 1 (tìm kiếm tuần tự cho mỗi T) thì chỉ đáp ứng được 60% 
số test với 1 ≤ N ≤ 103, T≤105 
Nếu sử dụng cách 2 (sắp xếp dãy an tăng dần theo sắp xếp nhanh và dùng tìm 
kiếm nhị phân cho mỗi T) thì đáp ứng 100% test với N ≤ 105, T≤105 
Vậy lựa chọn cách 2 để cài đặt chương trình 
Bước 5: Viết chương trình 
Code tham khảo 
36 
#include 
using namespace std; 
const long long maxn=1e5+7; 
long long n,x,t; 
long long a[maxn]; 
int nhiphan(long long B[], long long m, long long y) 
{ 
 int left = 0; 
 int right = m - 1; 
 int mid; 
 while (left <= right) 
 { 
 mid = (left + right) / 2; 
 if (B[mid] == y) 
 return mid; // tìm thấy x, trả về mid là vị trí 
của x trong mảng A 
 if (B[mid] > y) 
 right = mid - 1; // Giới hạn khoảng tìm kiếm lại 
là nửa khoảng trước 
 else if (B[mid] < y) 
 left = mid + 1; // Giới hạn khoảng tìm kiếm lại 
là nửa khoảng sau 
 } 
 return -1; // không tìm thấy x 
} 
int main() 
{cin>>n; 
for(int i=0;i<n;i++) 
cin>>a[i]; 
sort(a,a+n); 
cin>>t; 
for(int j=1;j<=t;j++) 
37 
{cin>>x; 
if (nhiphan(a,n,x)==-1) 
 cout<<"N"<<"\n"; 
else cout<<"Y"<<"\n"; 
} 
return 0; 
} 
Bài 2: SEQ7 
Cho dãy số gồm n số nguyên a1, a2, , an và 2 số nguyên không âm L, R (L ≤ R). 
Yêu cầu: Đếm số cặp (i, j) thỏa mãn điều kiện: i ≤ j và L ≤ |ai++aj| ≤ R . 
Dữ liệu vào: Từ file văn bản SEQ.INP gồm: 
 - Dòng đầu tiên chứa 3 số nguyên n, L, R (n ≤ 105 ; 0 ≤ L ≤ R ≤ 109) 
 - Dòng thứ hai chứa n số nguyên dương a1, a2,, an (ai ≤ 109) 
Kết quả: Ghi ra file văn bản SEQ.OUT gồm một số nguyên duy nhất là số lượng 
cặp (i, j) đếm được. 
 Ví dụ: 
SEQ.INP SEQ.OUT 
3 0 1 
1 -1 2 
4 
Hạn chế: - Có 50% số test ứng với 0 < n ≤ 103 
 - Có 50% số test ứng với 103 < n ≤ 105 
Bước 1: Xác định bài toán 
- Input: n số nguyên dương a1, a2,, an (ai ≤ 109, n ≤ 105), 2 số nguyên L, R 
(0 ≤ L ≤ R ≤ 109) 
- Output: số cặp (i, j) thỏa mãn điều kiện: i ≤ j và L ≤ |ai++aj| ≤ R 
Bước 2: Đặc điểm dữ liệu 
Dữ liệu vào gồm dãy số a(n) nguyên dương (ai ≤ 109, n ≤ 105) và 2 số nguyên 
L, R (0 ≤ L ≤ R ≤ 109) 
Bước 3: Các cách giải có thể lựa chọn 
7 Đề thi học sinh giỏi Tỉnh năm học 2016-2017 
38 
Ta thấy dữ liệu vào L ≤ R ≤ 109 thì không thể sử dụng tìm kiếm tuần tự được. 
Ta nghĩ đến cách tìm kiếm nhị phân, nhưng dãy này không thể sắp xếp vì sẽ thay 
đổi vị trí các phần tử. Bài này vận dụng thuật toán tìm kiếm nhị phân linh hoạt như 
sau: 
Trước hết tính tổng các số từ 1 đến n với s[i] = a[1]+a[2]++a[n] 
Nhận xét tại vị trí j cần tìm vị trí i (i <= j) sao cho 
l <= s[j]-s[i-1] <= r 
=> s[j]-l <= s[i-1] <= s[j]-r 
Ta dùng BIT để đếm số lượng các số trước đó thỏa điều kiện trên. 
Nhận xét là nó bị kẹp nên ta dùng phần bù : chỉ việc lấy số lượng các số >= 
s[j]-l trừ đi số lượng các số > s[j]-r thì ta sẽ được phần cần tìm 
Vậy tạo một BIT để đếm, nhưng số lớn (109 và hơn thế nữa) nên ta cần nén số 
lại, những số ta dùng hay nói cách khác là cập nhật và lấy giá trị là s[i-1], s[i]-l và 
s[i]-r+1. Ta cho vào một mảng rồi sort lại, đẩy vào một mảng mới tương ứng mỗi 
giá trị sẽ có một thứ tự 1 2 3 trên BIT. Cuối cùng dùng chặt nhị phân để tìm kết 
quả 
Bước 4: Đánh giá, lựa chọn thuật toán 
Như vậy theo bảng ước lượng (*) : 
Nếu sử dụng cách 1 (Dùng mảng tính tổng rồi sử dụng tìm kiếm tuần tự ) thì 
chỉ đáp ứng được 60% số test với N ≤ 103 
Nếu sử dụng cách 2 (theo ý tưởng như trên) thì đáp ứng 100% test với N ≤ 105 
Vậy lựa chọn cách 2 để cài đặt chương trình 
Bước 5: Viết chương trình 
Code tham khảo 
#include 
#define N 100005 
using namespace std; 
int n,L,R; 
long long s[N]; 
int main() 
{ 
 freopen("SEQ.inp","r",stdin); 
 freopen("SEQ.out","w",stdout); 
39 
 ios::sync_with_stdio(0); 
 cin>>n>>L>>R; 
 for (int i=1; i <= n; i++) 
 { 
 int a; 
 cin>>a; 
 s[i]=s[i-1]+a; 
 } 
 if (1LL*n*n <= 50000000) 
 { 
 long long res=0; 
 for (int i=1; i <= n; i++) 
 { 
 if (abs(s[i]) >= L && abs(s[i]) <= R) 
 res++; 
 for (int j=1; j < i; j++) 
 { 
 long long a=abs(s[i]-s[j]); 
 if (a >= L && a <= R) 
 res++; 
 } 
 } 
 cout<<res; 
 return 0; 
 } 
 s[++n]=0; 
 sort(s+1,s+1+n); 
 int l=1, r=1; 
 long long res=0; 
 for (int i=2; i <= n; i++) 
 { 
40 
 while (l = L) 
 l++; 
 if (l > 1 && abs(s[i]-s[l]) < L) 
 l--; 
 while (r R) 
 r++; 
 if (abs(s[i]-s[l]) >= L && abs(s[i]-s[r]) <= R) 
 res+=l-r+1; 
 } 
 cout<<res; 
 return 0; 
} 
Tóm lại, khi giải một bài toán ngoài việc giải đúng yêu cầu của bài toán thì với 
những bài toán có dữ liệu vào lớn còn cần phải lựa chọn thuật toán tối ưu nhất thích 
hợp đáp ứng dữ liệu vào. Trên đây chúng ta đã tìm hiểu một số trường hợp cụ thể. 
Tuy nhiên, trong quá trình giải người lập trình phải rất linh hoạt mới đáp ứng được 
yêu cầu của bài toán. Trong quá trình giảng dạy, giáo viên nên cho học sinh luyện 
tập nhiều bài toán có dữ liệu lớn, với nhiều dạng khác nhau để học sinh rèn luyện 
được khả năng tư duy linh hoạt và kỹ năng vận dụng sáng tạo theo bài toán cụ thể. 
Sau đây là một số bài tập giúp học sinh luyện tập, vận dung cho các dạng đã nêu. 
3.2.4. Bài tập luyện tập 
Bài 1: CHIA HẾT 
Lợi rất hào hứng với các bài toán số học, lần này Lợi muốn thử năng lực lập 
trình của các bạn với bài toán như sau: 
Cho bốn số nguyên dương a, b, x, y (a ≤ b; a, b, x, y ≤ 109). 
Yêu cầu: Đếm số lượng số nguyên dương thuộc đoạn [a ; b] chia hết cho x hoặc chia 
hết cho y. 
Dữ liệu vào: Từ tệp văn bản CHIAHET.INP gồm một dòng duy nhất chứa bốn số 
nguyên dương a, b, x, y và các số cách nhau ít nhất một dấu cách trống. 
Kết quả: Ghi ra tệp văn bản CHIAHET.OUT số lượng số nguyên dương đếm được. 
Ví dụ: 
CHIAHET.INP CHIAHET.OUT 
2 15 3 5 7 
41 
Giải thích: 
a = 2, b = 15, x = 3, y = 5 các số nguyên dương thuộc đoạn [2 ; 15] chia hết cho 
3 hoặc 5 là 3, 5, 6, 9, 10, 12, 15 nên số lượng là 7. 
Giới hạn: - 40% số test với a ≤ b ≤ 102 
 - 40% số test với a ≤ b ≤ 106 
 - 20% số test với a ≤ b ≤ 109 
Bài 2: TỔNG CHẴN 
Trên giá sách của thư viện trường THPT chuyên Phan Bội Châu có N quyển sách 
được đánh số thứ tự 1, 2, ... , N (2 < N < 106). Mỗi quyển sách có số lượng trang tương 
ứng là a1, a2, ... , aN (ai < 104, 1 < i < N). 
Yêu cầu: Tính số lượng tất cả các cách để có thể lấy 2 quyển sách trong số N quyển 
sách, sao cho tổng số lượng trang sách trong N - 2 quyển sách còn lại trên giá là một số 
chẵn. 
Dữ liệu vào: Từ tệp văn bản TONGCHAN.INP gồm hai dòng: 
 Dòng thứ nhất chứa số nguyên dương N. 
 Dòng thứ hai chứa N số nguyên dương a1, a2, ..., aN, các số cách nhau ít nhất một 
dấu cách trống. 
Kết quả: Ghi ra tệp văn bản TONGCHAN.OUT gồm một dòng duy nhất chứa một 
số nguyên là số cách có thể chọn. 
Ví dụ: 
TONGCHAN.INP TONGCHAN.OUT 
5 
36 58 27 64 75 
4 
Giải thích: 
Có 4 cách chọn là: 
Cách 1: Lấy quyển 1 và quyển 2 thì tổng số trang sách của các quyển còn lại: 
27+64+75 = 166 là số chẵn 
Cách 2: Lấy quyển 1 và quyển 4 thì tổng số trang sách của các quyển còn lại: 
58+27+75 = 160 là số chẵn 
Cách 3: Lấy quyển 2 và quyển 4 thì tổng số trang sách của các quyển còn lại: 
36+27+75 = 138 là số chẵn 
Cách 4: Lấy quyển 3 và quyển 5 thì tổng số trang sách của các quyển còn lại: 
36+58+64 = 158 là số chẵn 
42 
Giới hạn: - 60% số test với N ≤ 104 
 - 40% số test với 104 < N ≤ 106 
Bài 3: TÌM SỐ 
Hãy tìm số nguyên dương nhỏ nhất có chữ số hàng đơn vị là d (1≤d≤9) sao cho 
nếu chuyển chữ số hàng đơn vị lên trước chữ số đầu tiên thì ta được một số mới gấp 
k lần số cũ (1≤k≤9) 
Dữ liệu: Vào từ file văn bản NUMBER.INP 
Gồm nhiều dòng, mỗi dòng chứa hai số nguyên dương d, k cách nhau ít nhất 
một dấu cách. 
Kết quả: Ghi ra file văn bản NUMBER.OUT 
Gồm nhiều dòng, mỗi dòng ghi một số nguyên tìm được ứng với d,k ở dòng 
tương ứng của file dữ liệu. Ghi -1 nếu không có số thỏa mãn 
Ví dụ: 
NUMBER.INP NUMBER.OUT 
8 4 205128 
Ghi chú: Có 50% số test kết quả không vượt quá 106 
Bài 4: Đế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 
Bài 5: 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). 
43 
+ 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ụ: 
DAYCON.INP DAYCON.OUT 
10 
3 0 2 1 -2 0 3 -2 1 -2 
5 
1 -2 0 3 -2 
Bài 6: Taxi 
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 TAXI.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. 
Dữ liệu ra: Ghi ra file văn bản TAXI.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ụ: 
TAXI.INP TAXI.OUT 
5 
1 2 4 3 3 
4 
Tất cả file code của bài tập ví dụ và bài tập luyện tập thực hiện trong sáng 
kiến kinh nghiệm tôi đã lưu vào drive https://bit.ly/3d1VY5W 
4. Tính mới của SKKN 
- SKKN đã đưa ra định hướng để giúp học sinh có thể lựa chọn thuật toán phù hợp 
với dữ liệu bài toán để giải quyết bài toán hiệu quả nhất có thể. SKKN đã phân loại 
thành các dạng thường gặp, giúp người đọc dễ hiểu và dễ liên hệ với các bài toán khác. 
- Với bảng ước lượng độ phức tạp thuật toán tương ứng dữ liệu bài toán giúp 
học sinh có thể có căn cứ để giải bài toán phù hợp. 
44 
- Hệ thống các bài toán trong ví dụ có thể không phải là những bài toán xa lạ, nhưng 
trong SKKN đã đưa ra được hướng giải quyết theo hướng lựa chọn thuật toán phù hợp. 
5. Hiệu quả của SKKN 
Qua các năm giảng dạy và tham gia bồi dưỡng học sinh giỏi Tỉnh, tôi đã tích 
lũy được những kinh nghiệm trên. Hai năm 2019-2020 và 2020-2021 tôi đã áp 
dụng các giải pháp trên kết hợp sử dụng ngôn ngữ C++ để cài đặt vào thực hiện 
giảng dạy và thấy khá hiệu quả. Từ những ví dụ nên trên, với mỗi bài đều được phân 
tích, so sánh để làm rõ định hướng đã lựa chọn giúp học sinh dễ hiểu, dễ nhớ, dễ liên 
hệ tương tự. Từ đó giúp học sinh rèn luyện và nâng cao được kĩ năng tư duy lập 
trình, đáp ứng được yêu cầu ngày càng cao của các cuộc thi lập trình Tin học hiện 
nay. Sau khi tôi áp dụng vào giảng dạy, hầu như các em đều tự làm được những bài 
tương tự, thậm chí phức tạp hơn và luôn tìm cách để bài giải trở nên tốt nhất. Từ đó 
các em tự khai thác khả năng tư duy, sáng tạo của bản thân mình và đam mê Tin học 
hơn. Kết quả bồi dưỡng học sinh giỏi năm học 2020-2021 đạt giải ba với số điểm 
khá cao. 
Như vậy việc giúp học sinh biết cách lựa chọn thuật toán tối ưu phù hợp với dữ 
liệu của bài toán đem lại hiệu quả khá tốt, tránh được học sinh bị mất điểm đáng tiếc 
ở phần dữ liệu lớn. Từ đó góp phần nâng cao chất lượng bồi dưỡng học sinh giỏi. 
6. Những hướng phát triển của đề tài 
- SKKN có thể thêm các giải pháp khác để tạo thành chuyên đề giải pháp tối 
ưu hóa thuật toán để rèn luyện và nâng cao kĩ năng lập trình cho học sinh, làm tài 
liệu bồi dưỡng học sinh giỏi Tin học THPT 
45 
III. KẾT LUẬN VÀ KIẾN NGHỊ 
1. Kết luận 
Từ thực tế giảng dạy và bồi dưỡng học sinh giỏi, tôi nhận thấy: bài toán Tin 
học đa dạng và phong phú. Người lập trình phải rất linh hoạt trong giải và cài đặt 
chương trình. Đặc biệt với những bài toán đòi hỏi xử lý với dữ liệu lớn trong thời 
gian hạn chế. Với mỗi dạng toán cần có phương pháp giải phù hợp, với mỗi bài toán 
cần tìm giải thuật tối ưu cùng với việc xây dựng cấu trúc dữ liệu lưu trữ hợp lý. Qua 
các năm giảng dạy, cùng với sự tìm tòi các tài liệu, các bài viết trên sách tham khảo 
và mạng Internet cùng với cấu trúc đề ra và kiến thức cơ bản qua các kì thi chọn học 
sinh giỏi Tỉnh, tôi thấy với các giải pháp đã nêu có thể giúp học sinh có thêm kinh 
nghiệm để giải nhiều bài toán tương tự. Với mỗi giải pháp chúng ta có thể đưa ra rất 
nhiều ví dụ để học sinh có thể vận dụng, tuy nhiên trong phạm vi của một sáng kiến 
kinh nghiệm, tôi chỉ đưa ra một số ví dụ để trình bày. Vì kinh nghiệm chưa 
nhiều, không thể tránh khỏi các hạn chế, rất mong muốn nhận được những góp ý từ 
các bạn đồng nghiệp, Hội đồng khoa học các cấp và bạn bè chia sẻ, bổ sung để đề 
tài có thể hoàn thiện hơn. 
2. Kiến nghị 
Đối với Sở giáo dục và đào tạo: nên tổ chức nhiều đợt tập huấn nâng cao chuyên 
môn cho giáo viên Tin học về tiếp cận nhưng ngôn ngữ lập trình mới như C++, 
Python.. để đáp ứng của chương trình giáo dục phổ thông mới. 
Đối với nhà trường: 
- Cần đẩy mạnh hơn nữa cuộc vận động: “Mỗi thầy cô giáo là một tấm gương 
tự học và sáng tạo”. 
- Ngoài ra cần có chương trình 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. Từ đó tạo hứng thú và đam mê cho học sinh tham gia các 
kì thi học sinh giỏi. 
Đối với giáo viên: 
- Luôn trăn trở và tìm mọi giải pháp để bồi dưỡng năng lực giải các bài toán 
cho học sinh, đặc biệt là năng lực tu duy, sáng tạo trong học lập trình, giúp học sinh 
yêu học bộ môn hơn. 
- Thường xuyên trao đổi với học sinh và đồng nghiệp để tìm hiểu thêm nhiều 
vấn đề nghiên cứu để đáp ứng nhu cầu đổi mới dạy học. 
Đối với học sinh: 
- Đổi mới cách học sao cho hiệu quả nhất; nên tăng cường phương pháp tự học; 
tự nghiên cứu theo chuyên đề hoặc dự án theo sự hướng dẫn của giáo viên. 
46 
TÀI LIỆU THAM KHẢO 
1. Tài liệu chuyên Tin học - Quyển 1 - Hồ Sĩ Đàm - Nhà xuất bản Giáo dục 
2. Sáng tạo trong thuật toán và lập trình -Nguyễn Xuân Huy - NXB Thông tin 
truyền thông. 
3. Một số vấn đề chọn lọc trong môn Tin học -Nguyễn Xuân My – NXB Giáo dục 
4. Cấu trúc dữ liệu và giải thuật – Trần Hạnh Nhi, Dương Anh Đức- NXB ĐH 
quốc gia TPHCM 
4. Tạp chí Tin học nhà trường – Hội Tin học Việt Nam 
5. Nguồn đề học sinh giỏi Tin học Tỉnh Nghệ An các năm qua. 
6.  
7. https://vnoi.info/ 
47 
NHẬN XÉT CỦA HỘI ĐỒNG 
. 
CHỦ TỊCH HỘI ĐỒNG