SKKN Vận dụng thuật toán sắp xếp, tìm kiếm vào việc bồi dưỡng học sinh giỏi, thi chuyên phan trên ngôn ngữ lập trình C++

ếp việc 1 với thời hạn t[1] = 1 vào h: 
Không xếp được vì từ thời điểm 1 trở về trước trục thời gian h[1..1] đã kín. 
Ta thu được h = (4, 0, 0, 0, 3). 
- Chọn nốt việc 2 có tiền thưởng 10. Xếp việc 2 với thời hạn t[2] = 3 vào h: 
h[3] = 2. 
- Ta thu được h = (4, 0, 2, 0, 3). 
- Dồn việc trên trục thời gian h, ta thu được h = (4, 2, 3, 0, 0). 
- Xếp nốt việc phải làm mà không có thưởng, ta thu được h = (4, 2, 3, 1). 
- Ca làm việc kéo dài đúng N = 4 giờ. 
27 
- Dùng mảng cs để lưu lại vị trí công việc. 
*Code: 
#include using 
namespace std; 
int a[100],b[100],cs[100],d[100],h[1000],n,l=0,tt=0; 
void nhap() 
{ cin>>n; 
for(int i=1;i>a[i]>>b[i]; cs[i]=i;} 
fill(h+1,h+n+1,0); 
 } 
void qsort(int b[],int l,int r) 
{ int i=l, j=r; 
 int m=int(i+j)/2; 
 while (i<=j) 
 { while (b[i]>b[m]) i++; 
 while (b[j]<b[m]) j--; 
 if (i<=j) 
 { swap(b[i],b[j]); 
 swap(cs[i],cs[j]); 
 i++; j--; 
 } } 
 if (i<r) qsort(b,i,r); 
 if (j>l) qsort(b,l,j); 
} 
void xv() 
{ int v; 
 for(int i=1;i<=n;i++) 
 { v=cs[i]; 
 for(int k=a[v];k>0;k--) 
 if (h[k]==0) 
 {h[k]=v; l++; d[l]=v; tt=tt+b[i]; break; } 
 } } 
28 
void xuat() 
{ for(int i=l;i>0;i--) cout<<d[i]<<" "; 
cout<<tt<<” “<< l<< "\n"; 
} 
int main() 
{ freopen("viec.inp","r",stdin); 
freopen("viec.out","w",stdout);nhap(); 
 qsort(b,1,n); xv(); xuat(); return 0; 
} 
Bài 3. Đua ngựa 
Ở thời xuân thu, vua Tề và Điền Kỳ thường hay tổ chức đua ngựa từng cặp 
với nhau. Vua và Điền Kỳ mỗi người đua ra N con ngựa, đánh số từ 1 đến N. mỗi 
một con ngựa có một hệ số khác nhau. Một trận đấu mỗi người đưa ra một con 
ngựa để thi đấu. Trong cuộc đua, con ngựa vào có hệ số cao hơn thì sẽ thắng, nếu 
cùng hệ só thì Điền kỳ bí mật nhường cho vua thắng. mỗi một con ngựa chỉ được 
đấu đúng một trận. Ai có tổng số trận thắng nhiều hơn thì sẽ thắng chung cuộc. 
Bạn hãy giúp Điền Kỳ sắp xếp các lượt đấu để đạt số trận thắng cao nhất có thể. 
Dữ liệu vào: Horse.inp 
- Dòng đầu là số lượng ngựa (n<100000). 
- Dòng thứ hai có n số, số thứ I là hệ số của con ngựa thứ I của Điền Kỳ. 
- Dòng thứ ba có n số, số thứ I là hệ số của con ngựa thứ I của Vua Tề. 
Kết quả ra: horse.out 
- Ghi duy nhất một số là số trận thắng tối đa đạt được của Điền Kỳ. 
Ví dụ: 
Horse.inp Horse.out 
3 
4 6 2 
9 3 5 
2 
29 
Hạn chế thời gian: 1s, 
Cách giải: 
- Ban đầu ta chỉ cần sắp xếp các hệ số con ngựa của Vua Tề và Điền Kỳ 
- Sau đó so sánh lần lượt từng số hiệu con ngựa của Điền Kỳ với số hiệu con ngựa 
của Vua 
Tề, nếu con thứ 1 của Điền Kỳ có số hiệu lớn hơn con thứ j của Vua Tề thì số trận 
thắng của Điền Kỳ tăng lên. 
- Sau đó tiếp tục so sánh số hiệu con thứ i+1 của Điền Kỳ với số hiệu con thứ j+1 
của Vua , nếu Không lớn hơn thì lại so sánh con thứ i+2 của Điền kỳ với số hiệu 
con thứ j+1 của Vua. 
Và cứ như vậy cho đến khi hết số ngựa của Điền Kỳ. 
Code: 
#include; 
using namespace std; 
int a[100],b[100],n; 
void nhap(int c[],int k) 
{ for(int i=0;i>c[i];} 
int main() 
 { cin>>n; nhap(a,n); sort(a,a+n); 
nhap(b,n); sort(b,b+n); int d=0; 
int i=0, j=0; 
 while ((i<n)&&(j<n)) 
 {if (a[i]>b[j]) {d++; i++; j++;} 
 else i++; 
 } cout<<d; 
 return 0; 
 } 
Ta thấy bài toán trên độ phức tạp của đoạn code chính chỉ có O(n). Nhưng độ phức 
tạp của đoạn sắp xếp lại có thể là O(n2) hoặc O(nlogn) do ta lựa chọn thuật toán. 
Chính vì vậy độ phức tạp của thuật toán là phụ thuộc vào đoạn sắp xếp. 
- Chúng ta lựa chọn thư viện sort() để sắp xếp khi độ độ phức tạp chính phụ thuộc 
vào đoạn này. 
30 
Bài 4. Đoạn gối 
Cho N đoạn thẳng trên trục số với các điểm đầu ai và điểm cuối bi là những số 
nguyên trong khoảng −1000..1000, ai < bi. Liệt kê tối đa K đoạn thẳng gối nhau 
liên tiếp. Hai đoạn thẳng [a,b] và [c,d] được gọi là gối nhau nếu xếp chúng trên 
cùng một trục số thì điểm đầu đoạn này trùng với điểm cuối của đoạn kia, tức là 
c = b hoặc d = a. 
Dữ liệu vào: tệp văn bản DOAN.INP: 
- Dòng đầu ghi số N 
- N dòng tiếp theo, mỗi dòng ghi 2 số ai và bi 
Dữ liệu ra: tệp văn bản DOAN.OUT Ghi số tự nhiên K. 
Ví dụ: 
DOAN.INP DOAN.OUT 
5 
2 7 
1 3 
7 9 
3 4 
4 5 
3 
Ý tưởng: ta áp dụng phương pháp quy hoạch động + Tham lam. 
Giả sử các đoạn được sắp tăng theo đầu phải b. Kí hiệu c(i) là số lượng tối đa 
các đoạn thẳng gối nhau tạo thành một dãy nhận đoạn i làm phần tử cuối dãy (khi 
khảo sát các đoạn từ 
1..i). 
Ta có: c(1) =1, 
Với i = 2...N: c(i) = max { c(j) | 1 ≤ j < i, Đoạn j kề trước đoạn i: bj = ai } + 1. 
Lợi dụng các đoạn sắp tăng theo đầu phải b, với mỗi đoạn i ta chỉ cần duyệt 
ngược các đoạn j đứng trước đoạn i cho đến khi phát hiện bất đẳng thức bj < ai. 
Kết quả: K = max { c(i) | i = 1...n }. 
Độ phức tạp: cỡ N2 vì với mỗi đoạn ta phải duyệt tối đa tất cả các đoạn đứng trước 
đoạn đó. 
31 
Code: 
#include 
#include 
using namespace std; 
ifstream fi ("doangoi.inp"); 
ofstream fo ("doangoi.out"); 
int a[100],b[100],n, c[100],cs[100],t[100],k; 
void nhap() 
{ cin>>n; 
for(int i=1;i>a[i]>>b[i]; cs[i]=i;} } 
void qsort(int l, int r) 
{ int i=l,j=r; 
 int m=int((i+j)/2); 
 while (i<=j) 
 { while (b[i]<b[m]) i++; 
 while (b[j]>b[m]) j--; 
 if (i<=j) 
 { swap(b[i],b[j]); swap(cs[i],cs[j]); 
swap(a[i],a[j]); 
 i++;j--; 
 } 
 } if (i<r) qsort(i,r); 
 if (j>l) qsort(l,j); 
 } 
void xuli() 
{ c[1]=1; t[1]=1; 
 for (int i=2;i<=n;i++) 
 { c[i]=0; 
 for (int j=i-1;j>=1;j--) {f (a[i]>b[j]) (t[i]=i; break;} 
32 
Bài 5. Băng nhạc 
 Người ta cần ghi N bài hát, được mã số từ 1 đến N, vào một băng nhạc có thời 
lượng tính theo phút đủ chứa toàn bộ các bài đã cho. Với mỗi bài hát ta biết thời 
lượng phát của bài đó. Băng sẽ được lắp vào một máy phát nhạc đặt trong một siêu 
thị. Khách hàng muốn nghe bài hát nào chỉ việc nhấn phím ứng với bài đó. Để tìm 
và phát bài thứ i trên băng, máy xuất phát từ đầu cuộn băng, quay băng để bỏ qua i 
– 1 bài ghi trước bài đó. Thời gian quay băng bỏ qua mỗi bài và thời gian phát bài 
đó được tính là như nhau. Tính trung bình, các bài hát trong một ngày được khách 
hàng lựa chọn với số lần (tần suất) như nhau. Hãy tìm cách ghi các bài trên băng 
sao cho tổng thời gian quay băng trong mỗi ngày là ít nhất. 
Dữ liệu vào: được ghi trong tệp văn bản tên BANGNHAC.INP. 
- Dòng đầu tiên là số tự nhiên N cho biết số lượng bài hát. 
- Tiếp đến là N số nguyên dương thể hiện dung lượng tính theo phút của mỗi bài. 
Mỗi đơn vị dữ liệu cách nhau qua dấu cách. 
Dữ liệu ra: được ghi trong tệp văn bản BANGNHAC.OUT theo dạng thức sau: 
 - N dòng đầu tiên thể hiện trật tự ghi bài hát trên băng: mỗi dòng gồm hai số 
nguyên dương j và d cách nhau bởi dấu cách, trong đó j là mã số của bài hát cần 
ghi, d là thời gian tìm và phát bài đó theo trật tự ghi này. 
 if (a[i]==b[j]) 
 if (c[j]>c[i]) {c[i]=c[j]; t[i]=j;} 
 }c[i]++; 
 } } 
void xuat() 
{ int imax=1; 
 for(int i=2;i<=n;i++)if (c[imax]<c[i]) { c[imax]=c[i]; imax=i;} 
cout<<c[imax]<<endl; } 
} 
int main() 
{ nhap(); qsort(1,n); xuli(); xuat(); Return 0; 
 } 
33 
 - Dòng thứ n + 1 ghi tổng số thời gian quay băng nếu mỗi bài hát được phát một 
lần trong ngày. 
Ví dụ: 
BANGNHAC.INP BANGNHAC.OUT 
3 
7 2 3 
2 2 
3 5 
1 12 
19 
Ý tưởng: Để có phương án tối ưu ta chỉ cần ghi băng theo trật tự tăng dần của thời 
lượng. Bài toán được cho với giả thiết băng đủ lớn để ghi được toàn bộ các bài. Dễ 
dàng sửa chương trình để vận dụng cho trường hợp dung lượng tăng hạn chế trong 
M phút. Chương trình sắp xếp dữ liệu theo chỉ dẫn. 
Code: 
#include 
#include 
 using namespace std; 
ofstream fo("bd.out"); 
ifstream fi("bd.inp"); 
 int a[100],cs[100],n,t=0,tt=0; 
void nhap() //tu viet 
void qsort(int l,int r) 
{ int i=l,j=r; 
 int m=((i+j)/2); 
 while (i<=j) 
 { while (a[m]>a[i]) i++; 
while (a[m]<a[j]) j--; 
 if (i<=j) 
 { swap(a[i],a[j]); 
 swap(cs[i],cs[j]); 
 i++; j--; 
 } } 
34 
Vậy độ phức tạp của bài toán trên phụ thuộc vào đoạn sắp xếp. 
Bài 6. Lo cò 
Nhảy lò cò là trò chơi dân gian của Việt Nam, Người trên hành tinh X cũng 
rất thích trò chơi này và họ đã cải biên trò chơi này như sau: trên mặt phẳng vẽ n 
vòng tròn được đánh số từ 1 đến n. Tại vòng tròn i người ta điền số nguyên dương 
ai. hai số trên hai vòng tròn tùy ý không phân biệt nhất thiết phải khác nhau. Tiếp 
đến đến người ta vẽ các mũi tên là: nếu có ba số ai, aj, ak thõa mãn ak = ai+aj thì vẽ 
mũi tên hướng từ vòng tròn i đến vòng tròn k và mũi tên hướng từ vòng tròn j đến 
vòng tròn k. Người chơi chỉ được di chuyển từ một vòng tròn đến một vòng tròn 
khác nếu có mũi tên xuất phát từ một trong số các vòng tròn, di chuyển theo cách 
mũi tên đã vẽ để đi đến các vòng tròn khác. Người thắng cuộc sẽ là người tìm 
được cách di chuyển qua nhiều vòng tròn nhất. 
Ví dụ: với 5 vòng tròn và các số trong vòng tròn là 1, 2, 6, 4, 3, trò chơi được trình 
bày trong hình dưới đây: 
if(i<r) qsort(i,r); 
 if(j>l) qsort(l,j); 
} 
void xuat() 
{ qsort(1,n); 
 for(int i=1;i<=n;i++) 
 { t=t+a[i]; fo<<cs[i]<<" "<<t<<"\n"; 
 tt=tt+t; 
 } fo<<tt<<" "; 
} int main() 
35 
Khi đó có thể di chuyển được nhiều nhất qua 4 vòng tròn (tương ứng với đường di 
chuyển được tô đậm trên hình vẽ). 
Yêu cầu: Hãy xác định xem trong trò chơi mô tả ở trên nhiều nhất có thể di 
chuyển được qua bao nhiêu vòng tròn? 
Dữ liệu vào: 
 - Dòng đầu chứa số nguyên n (3<=n<=1000); 
 - Dòng thứ hai chứa dãy số nguyên dương a1, a2,  an (ai <=109, i=1, 2, n). 
Hai số liên tiếp trên một dòng được ghi cách nhau bởi dấ u cách. 
Dữ liệu ra: 
 Ghi ra số lượng vòng tròn trên đường di chuyển tìm được Rằng buộc: 60 % tests 
ứng với 60% số điểm của bài có 3<=n<=100 
Ví dụ: 
INPUT OUTPUT 
5 
1 2 6 4 3 
4 
Ý tưởng: từ đường tròn j để di chuyển sang vòng tròn i thì a[i]>a[j] , nên khi đó 
việc nhập dữ liệu không ảnh hưởng đến giá trị tối ưu của bài toán. 
- Ta sắp xếp các giá trị trong mảng a theo thứ tự tăng dần. 
- Với quy tắc di chuyển này mỗi đơn vị dữ liệu là một vòng tròn, ứng với một 
số trong dãy đã sắp xếp khi xét đến đường tròn thứ i để nó là điểm cuối của dãy 
nhiều vòng tròn nhất ta thêm nó vào sau dãy con dài nhất có thể đi đến các vòng 
tròn phía trước. 
Code: 
#include 
using namespace std; 
int n,a[1000],f[1000]; 
void xl() 
{ for(int i=0;i<n;i++) f[i]=1; 
 for (int i=2;i<n;i++) 
 {for (int j=i-1;j>=1;j--) 
 if (binary_search(a,a+i,a[i]-a[j])) f[i]=max(f[i],f[j]+1); 
 } } 
36 
2.3.2. Bài tập tự giải 
Bài 1. Bước nhảy xa nhất 
 Cho dãy A gồm N số nguyên không âm A1, A2,,AN. Một bước nhảy từ 
phần tử Ai đền phần Aj được gọi là bước nhảy xa nhất của dãy nếu thỏa mãn các 
điều kiện sau: 
+1≤i<j≤N. 
+Aj-Ai≥P. 
+j-i lớn nhất( Khi đó j-i được gọi là độ dài bước nhảy xa nhất của dãy). 
Yêu cầu: Tìm độ dài bước nhảy xa nhất của dãy A. 
Dữ liệu vào: Từ tệp JUMP.INP có cấu trúc như sau: 
-Dòng 1: Gồm hai số nguyên N và P(1≤N≤105; 0≤≤ P≤ 109). 
-Dòng 2 : Gồm N số nguyên A1,A2,...,An(0≤Ai≤10^9 với 1≤i≤N). 
Kết quả: Ghi vào tệp JUMP.OUT gồm một số nguyên dương duy nhất là độ dài 
của bước nhảy xa nhất của dãy ( Nếu không có bước nhảy nào thỏa mãn thì ghi kết 
quả bằng 0). 
Ví dụ: 
JUMP.INP JUMP.OUT 
6 3 
4 3 7 2 6 4 
3 
void xuat() 
{ cout<<*max_element(f,f+n); //đưa ra giá trị max trong mảng f 
} 
int main() 
{ freopen("loco.inp","r",stdin); 
freopen("loco.out","w",stdout); 
 cin>>n; 
 for(int i=0;i>a[i]; 
 sort(a,a+n); xl(); xuat(); return 0; 
} 
37 
Bài 2. Khoảng Cách 
Yêu cầu: Cho n số nguyên , hãy tính khoảng cách nhỏ nhất giữa 2 số nguyên bất 
kì. 
Dữ liệu vào: Từ tệp KHOANGCACH.INP gồm 
 - Dòng đầu tiên ghi số nguyên dương n ( n ≤ 100000 ). 
 - Dòng tiếp theo ghi n số nguyên a[i] ( | a[i] | ≤ 1e6 ). 
Dữ liệu ra: ghi vào tệp KHOANGCACH.OUT là: 
 - Kết quả bài toán. 
Ví dụ: 
KHOANGCACH.INP KHOANGCACH.OUT 
3 
1 5 2 
 1 
Bài 3. Bài toán cái túi ( với số lượng vật không hạn chế) 
Cho một cái túi có thể đựng một trọng lượng không quá W và n đồ vật, mỗi 
đồ vật i có trọng lượng là ai và giá trị là ci , tất cả các đồ vật đều có số lượng không 
hạn chế. Tìm một cách lựa chọn các đồ vật đựng vào ba lô, chọn các đồ vật nào, 
mỗi loại lấy bao nhiêu, sao cho tổng trọng lượng không vượt quá W và tổng giá trị 
là lớn nhất. 
Dữ liệu vào: từ file CAITUI.INP 
- Dòng đầu ghi n (n<1000), W 
- N dòng tiếp theo, mỗi dòng ghi hai số ai và ci (i=1..n). 
Dữ liệu ra: từ file CAITUI.OUT các đồ vật và số lượng các đồ vật được lấy 
Ví dụ: 
CAITUI.INP CAITUI.OUT 
 4 37 
15 30 
10 25 
 2 2 
 4 6 
2 3 
3 1 
4 1 
38 
Bài 4. Đoạn bao nhau 
Cho N đoạn thẳng trên trục số với các điểm đầu ai và điểm cuối bi là những 
số nguyên trong khoảng −1000..1000, ai < bi, i = 1..n. Tìm K là số lượng nhiều 
đoạn nhất tạo thành một dãy các đoạn bao nhau liên tiếp. Hai đoạn [a,b] và [c,d] 
được gọi là bao nhau nếu đoạn này nằm lọt trong đọan kia, tức là a ≤ c < d ≤ b 
hoặc c ≤ a < b ≤ d. 
 Dữ liệu vào: tệp văn bản DOAN.INP: 
- Dòng đầu ghi số N 
- N dòng tiếp theo, mỗi dòng ghi hai số ai và bi. 
Dữ liệu ra: tệp văn bản DOAN.OUT Chứa duy nhất một số 
tự nhiên K. 
Ví dụ: 
DOAN.INP DOAN.OUT 
6 
1 12 
8 10 
8 11 
2 7 
17 18 
13 20 
 3 
Bài 5. Phủ đoạn 
Cho N đoạn thẳng trên trục số với các điểm đầu ai và điểm cuối bi là những 
số nguyên trong khoảng −1000..1000, ai < bi. Hãy chỉ ra ít nhất K đoạn thẳng sao 
cho khi đặt chúng trên trục số thì có thể phủ kín đoạn [x, y] với tọa độ nguyên cho 
trước. 
 Dữ liệu vào: tệp văn bản DOAN.INP: xem bài trước 
- Dòng 1 chứa N, 
- N dòng tiếp theo mỗi dòng chứa hai số ai và bi là điểm đầu và điểm cuối. 
Dữ liệu ra: tệp văn bản DOAN.OUT 
- Dòng đầu tiên: số K, nếu vô nghiệm K = 0. 
Tiếp theo là K số tự nhiên biểu thị chỉ số của các đoạn thẳng phủ kín đoạn [x, y]. 
39 
Ví dụ: 
DOAN.INP DOAN.OUT 
5 
3 23 
1 15 
3 10 
8 20 
17 25 
 2 7 
3 
1 
3 
4 
Bài 6. Số nguyên nhỏ nhất 
 Cho dãy gồm N (N ≤ 30000) số tự nhiên không vượt quá 109, tìm số tự nhiên 
nhỏ nhất không xuất hiện trong dãy. 
Dữ liệu vào: Từ file SN.INP gồm: 
- Dòng đầu là số nguyên N. 
- Dòng thứ hai gồm N số. 
Dữ liệu ra: file SN.OUT có dạng: số tự nhiên nhỏ nhất không xuất hiện trong 
dãy. 
 Ví dụ: 
SN.INP SN.OUT 
5 
5 0 3 1 4 
2 
Bài 7. Cỏ Dại 
Tèo có một vườn rau nhưng dạo gần đây cỏ dại mọc lên ùn ùn nhỗ mãi 
không hết. Không biết làm thế nào, Tèo bèn nhờ Tí, một kĩ sư nghiên cứu về cỏ 
dại. Tí cho hay vườn của Tèo có hai cây cỏ dại vương – cây này phân phát hạt 
mầm, bảo vệ các cây cỏ dại khác, chỉ cần Tèo tìm được nó và nhổ nó lên thì đám 
cỏ dại kia sẽ từ từ biến mất. Nghe thấy vậy, Tèo liền về nhà đi tìm cây cỏ dại 
vương. 
 Vườn nhà Tèo là một đường thẳng có N cây cỏ dại, cây cỏ dại được đánh 
số từ 1 đến N, cây cỏ dại thứ i có độ dẻo dai Wi. Hai cây x, y là cỏ dại vương nếu 
|Wx – Wy| là lớn nhất. Bạn hãy giúp Tèo tìm |Wx – Wy| lớn nhất. 
40 
Dữ liệu vào: Từ tệp Codai.inp gồm: 
 • Dòng đầu tiên, chứa một số nguyên dương N (1 ≤ N ≤ 10 6) 
 • Dòng thứ 2, chứ N số nguyên Wi (1 <= i <= N) là độ dẻo dai của N cây cỏ. 
(1 ≤ Wi ≤ 10 9.) 
Dữ liệu ra: ghi vào tệp Codai.out 
 • In ra một số nguyên duy nhất là kết quả của bài toán. 
 Ví dụ: 
Codai.inp Codai.out 
3 
1 2 3 
2 
Bài 8. Dãy số 
Cho dãy số nguyên a1, a2, . . an. Số ap (1 ≤ e ≤ n) được gọi là một số trung bình 
cộng trong dãy nếu tồn tại 3 chỉ số i, j, k (1 ≤ i, j, k ≤n) đôi một khác nhau, sao 
cho ap = (ai + aj + ak)/3 
Yêu cầu: Cho n và dãy số a1, a2, . . an. Hãy tìm số lượng các số trung bình cộng 
trong dãy. 
Dữ liệu vào: Từ tệp Dayso.inp gồm: 
- Dòng đầu ghi số nguyên dương n (3 ≤ n ≤ 1000). 
- Dòng thứ hai chứa n số nguyên ai (|ai | < 10
8). 
Dữ liệu ra: Lưu vào tệp Dayso.out là: 
- Số lượng các số trung bình cộng trong dãy. 
 Ví dụ: 
Dayso.inp Dayso.out 
5 
4 3 6 3 5 
2 
41 
Bài 9. Đoạn rời 
Cho N đoạn thẳng với các điểm đầu ai và điểm cuối bi là những số nguyên 
trong khoảng−1000..1000, ai < bi. Liệt kê số lượng tối đa các đoạn thẳng rời nhau. 
Hai đoạn được xem là rời nhau nếu chúng không có điểm chung. Các đoạn có 
dạng như trong bài Phủ đoạn 2. 
 Dữ liệu vào: tệp văn bản DOAN.INP 
 - Dòng đầu tiên: số tự nhiên N > 1. 
. - N dòng tiếp theo, mỗi dòng ghi 2 số ai và bi. 
Dữ liệu ra: tệp văn bản DOAN.OUT 
 -Dòng đầu tiên: số K. 
 -Tiếp theo là K số tự nhiên biểu thị chỉ số của các đoạn thẳng rời nhau cách 
nhau bằng dấu cách. 
Ví dụ: 
DOAN.INP DOAN.OUT 
8 
-2 3 
3 5 
8 12 
13 15 
3 9 
4 5 
5 8 
7 15 
5 
1 2 7 3 4 
2.4. Kết quả sau khi áp dụng đề tài 
Đề tài đã được triển khai và áp dụng trong việc bồi dưỡng học sinh giỏi tỉnh 
trong các năm học vừa qua. Sau khi đề tài triển khai, ngoài trang bị kiến thức, kĩ 
năng xử lí các bài toán phức tạp cho học sinh. Qua đó cũng cố thêm kiến thức cho 
giáo viên bồi dưỡng và đồng nghiệp. Kết quả giành được nhiều tín hiệu tích cực từ 
nhiều phía. Đặc biệt là trong các đợt thi học sinh giỏi tỉnh luôn giành được các 
giải cao và luôn đứng đầu bảng B. Trong kì thi học sinh giỏi tỉnh năm học 2020-
2021 vừa qua. Em học sinh: Nguyễn Mạnh Đạt giải nhất bảng B với 16 điểm. 
42 
PHẦN III. KẾT LUẬN 
1. Với mục tiêu đề ra đề tài đã làm được 
Đề tài được trình bày trong 2 phần chính. Nêu ra thực trạng, những vấn đề 
cần giải quyết hiện nay mà một giáo viên bồi dưỡng học sinh giỏi cần phải chú ý. 
Trình bày cụ thể, đầy đủ, chi tiết về mặt lí thuyết của phương pháp sắp xếp và tìm 
kiếm. Ngoài ra còn lấy những bài toán cơ bản nhằm nâng cao kĩ năng cũng như 
vận dụng phương pháp một cách hiệu quả. 
2. Hướng phát triển của đề tài 
Trong thời gian tới tôi sẽ tập trung phát triển đề tài hơn nữa, xây dựng lại hệ 
thống lý thuyết một cách chặt chẽ, hợp lý hơn. Đồng thời xây dựng chỉnh sửa lại, 
mở rộng nội dung, dễ triển khai, thân thiện hơn. Nhằm mang lại nhiều kết quả cao 
trong các kì thi học sinh giỏi cũng như thi vào lớp 10 chuyên tin trường Phan Bội 
Châu. Ngoài ra chia sẽ đề tài một cách rộng rãi đến các giáo viên trong và ngoài 
nhà trường. Giúp giáo viên bồi dưỡng có thêm lựa chọn về nội dung, phương pháp 
trong việc ôn tập và bồi dưỡng học sinh giỏi một cách dễ dàng và hiệu quả hơn. 
3. Kiến nghị và đề xuất 
Để áp dụng đề tài hiệu quả trong quá trình bồi dưỡng giáo viên cần bồi 
dưỡng nhiều hơn nữa về lí thuyết sắp xếp và tìm kiếm. Xem và làm các bài toán 
từ cơ bản, điển hình cho đến nâng cao. Một số thao tác xử lí bằng phương pháp 
sắp xếp và các phương pháp khác để ứng dụng phương pháp này cũng như kết hợp 
các phương pháp với phương pháp này một cách hiệu quả nhất. 
Hướng dẫn, khuyến khích học sinh tham gia giải bài, tìm kiếm các bài tập 
có phân dạng về xử lí bằng phương pháp sắp xếp và tìm kiếm trên các trang mạng 
giải bài trực tuyến (đặc biệt trên trang vn.spoj.com; laptrinhphothong.vn ) và các 
đề thi học sinh giỏi qua các năm. 
Do thời gian cũng như năng lực cá nhân có hạn, nên đề tài còn có một số 
thiếu sót, xây dựng các nội dung, phương pháp và cách thức mới chỉ đáp ứng được 
yêu cầu cơ bản của đề tài đưa ra. Chính vì vậy rất mong nhận được những lời góp 
ý, nhận xét từ cán bộ quản lí nhà trường, từ Ban Giám khảo và từ các bạn đồng 
nghiệp, để phát huy những mặt mạnh, điều chỉnh, khắc phục những thiếu sót cho 
đề tài được hoàn thiện hơn. 
Lời cuối cho phép tôi xin chân thành cảm ơn ban giám hiệu nhà trường, các 
thầy cô bộ môn, các em học sinh trên địa bàn đã giúp đỡ và tạo điều kiện để tôi 
hoàn thành và triển khai đề tài một cách hiệu quả nhất. 
43 
TÀI LIỆU THAM KHẢO 
1. Hồ Sĩ Đàm_Tài liệu giáo khoa chuyên tin quyển 1 
2. Hồ Sĩ Đàm _Sách giáo khoa Tin học 11 
3. Lê Minh Hoàng_ Chuyên đề tin 
4. Đỗ Xuân Lôi - Cấu trúc dữ liệu và giải thuật 
5. Nguyễn Thanh Thủy_Ngôn ngữ lập trình C 
6. Các trang Internet 
-  
-  
-