Sáng kiến kinh nghiệm Sử dụng phương pháp chia để trị để giải một số bài toán

Sort) đều có độ phức tạp cỡ O(n2). Thuật toán sắp xếp nhanh (Quick 
Sort) hay sắp xếp trộn (Merge Sort) là hai thuật toán sắp xếp theo tư tưởng chia để 
trị. 0Với tư tưởng chia để trị, Quick Sort và Merge Sort cho ta độ phức tạp nhỏ hơn 
thường là O(nlogn). Trong đề tài này tôi chỉ tập trung nghiên cứu thuật toán 
QuickSort 
Chúng ta xét thuật toán sắp xếp nhanh (Quick Sort) 
Ý tưởng: Tư tưởng của thuật toán này là chia để trị, ta tìm cách chia đôi dãy 
ban đầu bằng cách chọn ra một phần tử là chốt (pivot). Từ dãy ban đầu, tất cả phần 
18 
tử nhỏ hơn phần tử chốt thì đưa về bên trái dãy; những phần tử lớn hơn hoặc bằng 
chốt thì đưa về bên phải dãy. Sau bước này ta có phần tử chốt là đứng đúng vị trí. 
Dãy ban đầu được chia thành hai dãy con nằm hai bên chốt. Tiếp tục phân chia các 
dãy con theo cách tương tự cho đến khi mọi dãy con đều có độ dài bằng 1. Có thể 
chọn phần tử chốt nằm đầu, cuối, giữa dãy hoặc chọn ngẫu nhiên một phần tử 
trong dãy. 
Giải Thuật: Trường hợp sau chọn chốt là phần tử giữa dãy 
 Sắp xếp một đoạn bất kỳ A[L] ... A[R] với điều kiện L<R 
 Bước 1: pivot=(L+R) div 2; Key=A[pivot]; 
 Bước 2: i:=L; j:=R; 
 Bước 3: 
 Nếu A[i]<key thì tăng i; 
 Nếu A[j]>key thì giảm j; 
 Bước 4: Nếu i<j thì đổi chỗ A[i] và A[j], quay lại bước 3; 
 Bước 5: Lặp lại bước 1 đến bước 3 với đoạn A[L] đến A[j] và A[i] 
đến A[H] cho đến khi tất cả các đoạn có độ dài bằng 1. 
 Đoạn chương trình con: 
procedure quicksort(l,h:longint); 
var i,j:longint;key,tg:longint; 
Begin 
 i:=l;j:=h;key:=A[(l+h) div 2]; 
 repeat 
 while a[i]>key do inc(i); 
 while a[j]<key do dec(j); 
 if i<=j then 
 begin 
 tg:=a[i]; 
 a[i]:=a[j]; 
 a[j]:=tg; 
 inc(i); 
 dec(j); 
 end; 
 until i>j; 
19 
 if i<h then quicksort(i,h); 
 if j>l then quicksort(l,j); 
end; 
Đánh giá độ phức tạp 
Việc chọn chốt để phân đoạn quyết định hiệu quả của thuật toán, nếu chọn 
chốt không tốt rất có thể việc phân đoạn bị suy biến thành trường hợp xấu khiến 
QuickSort hoạt động chậm. 
+ Trường hợp tốt nhất: mỗi lần phân hoạch ta đều chọn được phần tử 
median (phần tử lớn hơn hay bằng nửa số phần tử và nhỏ hơn hay bằng nửa số 
phần tử còn lại) làm chốt. Khi đó dãy được phân đoạn thành hai phần bằng nhau, 
và ta cần log2(n) lần phân đoạn thì sắp xếp xong. Ta cũng dễ nhận thấy trong mỗi 
lần phân đoạn ta cần duyệt qua n phần tử. Vậy độ phức tạp trong trường hợp tốt 
nhất cỡ O(nlogn). 
+ Trường hợp xấu nhất: mỗi lần phần đoạn ta chọn phải phần tử có giá trị 
cực đại hoặc cực tiểu làm mốc. Khi đó dãy bị phân đoạn thành hai phần không đều: 
một phần chỉ có một phần tử, phần còn lại có n-1 phần tử. Do đó, ta cần tới n lần 
phân đoạn mới sắp xếp xong. Vậy độ phức tạp trong trường hợp xấu nhất thuộc 
O(n2). Trường hợp này ít khi xẩy ra nếu việc chọn chốt là ngẫu nhiên. 
Bài toán áp dụng: 
 Bài 1. Camera theo dõi 
 Trong đoạn đường từ thành phố A đến thành phố B có N nút giao thông 
đánh số từ 1 đến N (với AB là một đoạn thẳng). Cần bố trí các camera theo dõi 
hoạt động giao thông tại các nút này. Mỗi camera đặt ở một vị trí nào đó có thể 
theo dõi được hoạt động giao thông trên những điểm ở cách nó không quá r (km). 
Bieets di (km) là khoảng cách từ nút giao thông A đến nút giao thông thứ I 
(i=1,2,,N). 
 Yêu cầu: Tìm cách đặt một số ít nhất camera để có thể theo dõi được hoạt 
động giao thông trên đoạn đường từ A đến B (mỗi nút phải nằm tròng tầm theo dõi 
của ít nhất một trong số các camera được bố trí). 
 Dữ liệu: Vào từ file văn bản CAMERA.INP gồm: 
 - Dòng đầu tiên ghi số nguyên dương N (N<100) và số thực r. 
20 
 - Dòng thứ i trong số N dòng tiếp theo ghi số thực d (i=1,2.,N) là 
một trong những khoảng cách từ thành phố A đến một nút giao thông bất kỳ. 
 Kết quả: Ghi ra file văn bản CAMERA. OUT gồm: 
 - Dòng đầu tiên ghi k là số lượng máy theo dõi cần đặt. 
 - Dòng thứ i trong số k dòng tiếp theo ghi Si là khoảng cách từ A đến 
vị trí đặt camera thứ i (các camera đặt theo thứ tự sao cho: S1<S2<.<Sk) 
 Ví dụ: 
CAMERA.INP CAMERA.OUT 
7 0.7 
0.5 
1.2 
1.5 
2.5 
3.4 
2.6 
4.7 
3 
1.2 
3.2 
4.7 
Chương trình tham khảo: 
const 
 fi=’CAMERA.INP’; 
fo=’CAMERA.OUT’; 
var F1,F2:TEXT; 
 a,kq:array[1.. 100]of real; 
 n,k,x:integer; r:real 
procedure taotep; 
begin 
Assign(f1,fi); assign(f2,fo); 
Reset(f1); rewrite(f2); 
end; 
procedure doctep; 
var i:integer; 
begin 
 readln(f1,n,r); 
21 
for i:=1 to n do 
read(f1,a[i]); 
end; 
procedure quicksort(l,h:integer); 
var i,j,key,tg:integer; 
begin 
 i:=l; j:=h; 
 key:=a[(l+h) div 2]; 
 repeat 
 while a[i]<key do inc(i); 
 while a[j]>key do dec(j); 
 if i<=j then 
 begin 
 tg:=a[i]; a[i]:=a[j]; a[j]:=tg; inc(i); 
 dec(j); 
 end; 
 until i>j; 
 if j>l then quicksort(l,j); 
 if i<h then quicksort(i,h); 
end; 
Procedure xuli; 
Var I,j:integer; 
Kc:real; 
Begin 
quicksort(1,n:integer) 
k:=1; kq[1]:=a[1]+r; i:=1; 
While i< do 
Begin 
While (a[i]<=r+kq[k]) and (i<n) do inc(i); 
If i<n then 
Begin 
22 
Inc(k); Kq[k]:=a[i]+r; 
End 
Else 
Begin 
If a[i]>kq[k]+r then 
Begin 
Inc(k); Kq[k]:=a[i]; 
End; 
End; 
End; 
End; 
Procedure ghitep; 
Var i:integer; 
Begin 
Writeln(f2,k); 
For i:=1 to k do writeln(f2,kq[i]:2:1); 
End; 
Procedure dongtep; 
Begin 
Close(f1); close(f2); 
BEGIN 
Taotep; doctep; xuli; ghitep; dongtep; 
END. 
Bài 2. Trò chơi 
Nhân dịp lễ giáng sinh, công viên trung tâm tổ chức trò chơi "con số may 
mắn". Mỗi em nhỏ đến tham dự sẽ được phát một số nguyên dương. Công viên có 
một thiết bị quay số, mỗi lần quay sẽ tạo ngẫu nhiên một số nguyên dương có giá 
trị tuyệt đối không vượt quá 104. Người dẫn chương trình sẽ thực hiện N lần quay 
số. Số nào xuất hiện nhiều nhất trong N lần quay được gọi là con số may mắn và 
em nhỏ nào có con số may mắn thì sẽ được phần thưởng. 
Yêu cầu: Cho N con số xuất hiện trong N lần quay. Bạn hãy giúp người dẫn 
chương trình xác định số lần xuất hiện của con số may mắn. 
23 
Dữ liệu vào từ file văn bản TC.inp: 
 Dòng đầu là số N (1 ≤ N ≤ 104). 
 Dòng tiếp theo có N số là các số xuất hiện trong N lần quay. 
Kết quả ghi ra file văn bản TC.out: 
Gồm một dòng duy nhất ghi số lần xuất hiện của con số may mắn. 
Ví dụ: 
TC.inp TC.out TC.inp TC.out 
6 
2 2 2 5 2 2 
5 
9 
4 6 7 6 8 6 9 3 2 
3 
Ý tưởng: 
Ngoài phương pháp sử dụng kỹ thuật đánh dấu bài toán trên còn có thể sử 
dụng thuật toán sắp xếp như sau: 
- Sắp xếp dãy theo chiều tăng dần 
- Max:=0; 
- Đếm các phần tử cạnh nhau và bằng nhau, tìm số lượng phần tử 
nhiều nhất: 
i:=1; 
repeat 
 d:=1; 
 while a[i]=a[i+1] do 
 begin inc(d); inc(i); end; 
 if d > max then Max:=d; 
 inc(i); 
until i > n; 
- Đưa ra max. 
Chương trình tham khảo: 
const 
 fi=’TC.INP’; 
fo=’TC.OUT’; 
24 
var F1,F2:TEXT; 
 a:array[1.. 1000]of integer; 
 n,i:integer; 
procedure taotep; 
begin 
Assign(f1,fi); assign(f2,fo); 
Reset(f1); rewrite(f2); 
end; 
procedure doctep; 
var i:integer; 
begin 
 readln(f1,n); 
for i:=1 to n do 
read(f1,a[i]); 
end; 
procedure quicksort(l,h:integer); 
var i,j,key,tg:integer; 
begin 
 i:=l; j:=h; 
 key:=a[(l+h) div 2]; 
 repeat 
 while a[i]<key do inc(i); 
 while a[j]>key do dec(j); 
 if i<=j then 
 begin 
 tg:=a[i]; a[i]:=a[j]; a[j]:=tg; inc(i); 
 dec(j); 
 end; 
 until i>j; 
 if j>l then quicksort(l,j); 
 if i<h then quicksort(i,h); 
25 
end; 
procedure xuli; 
var i,d:integer; 
Begin 
 quicksort(1,n); 
 for i:=1 to n do 
 if a[i]a[i+1] then inc(d); 
 write(f2,d); 
end; 
procedure dongtep; 
begin 
close(f1); close(f2); 
end; 
BEGIN 
Taotep; doctep; xuli; dongtep; 
END. 
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. Mỗi một con ngựa có một hệ số khác nhau. Trong cuộc đua, con ngựa 
nào có hệ số cao hơn thì sẽ thắng, nếu có hệ số ngang nhau thì sẽ về đích cùng một 
lúc mỗi một con ngựa chỉ được thi đấu một lượt. Ai có tổng số trận thắng nhiều 
hơn thì sẽ thắng chung cuộc. Số trận <= 1000 trận. 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 từ file DUANGUA.INP bao gồm: 
- Dòng đầu là số lượng ngựa: n 
- 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ả ghi vào file DUANGUA.OUT gồm 1 số duy nhất ghi số trận thắng 
cao nhất mà Điền Kỵ có thể dành được. 
 Ví dụ: 
DUANGUA.INP 
DUANGUA.OUT 
3 
4 6 2 
2 
26 
9 3 5 
5 
3 7 12 5 8 
13 5 9 14 6 
3 
Ý tưởng: 
Với mục tiêu dành nhiều trận thắng nhất có thể nên Điền Kỵ phải cố gắng 
đưa ra con ngựa thi đấu sao cho nó sẽ đấu với đối thủ mạnh nhất có thể của vua Tề 
mà vẩn dành được phần thắng 
Để thực hiện được điều này ta sắp xếp hệ số của các con ngựa của cả Điền 
Kỵ và Vua Tề theo thứ tự giảm dần. Khi đó, con ngựa mạnh nhất sẽ được đưa ra 
thi đấu trước và nó sẽ thi đấu với con ngựa đầu tiên tìm được (Từ đầu dãy ngựa 
của Vua Tề trở đi) mà nó có thể thắng. Lần lượt như thế cho đến khi các chú ngựa 
của Điện Kỵ thi đẫu hết. 
 Với Input: 
 3 
 4 6 2 
 9 3 5 
 Ta sắp xếp hai dãy số thành 
 6 4 2 và 9 5 3 
Khi đó con ngựa có hệ số 6 của Điền Kỵ sẽ đấu với con ngựa hệ số 5 của 
Vua Tề và được một trận thắng. Con ngựa có hệ số 4 của Điền Kỵ sẽ đấu với con 
ngựa hệ số 3 của Vua Tề và được trận thắng thứ hai. Cặp ngựa còn lại Điền Kỵ bị 
thua và số trận thắng nhiều nhất có thể là 2. 
Chương trình tham khảo: 
const 
 fi=’DUANGUA.INP’; 
fo=’DUANGUA.OUT’; 
var F1,F2:TEXT; 
 a,b:array[1.. 10000]of integer; 
 n,i:integer; 
procedure taotep; 
begin 
Assign(f1,fi); assign(f2,fo); 
27 
Reset(f1); rewrite(f2); 
end; 
procedure doctep; 
var i:integer; 
begin 
 readln(f1,n); 
 for i:=1 to n do 
 readln(f1,a[i]); 
 readln(f1); 
 for i:=1 to n do 
 readln(f1,b[i]); 
end; 
procedure quicksort(var x:mang;l,h:integer); 
var i,j,key,tg:integer; 
begin 
 i:=l; j:=h; 
 key:=x[(l+h) shr 1]; 
 repeat 
 while x[i]<key do inc(i); 
 while x[j]>key do dec(j); 
 if i<=j then 
 begin 
 tg:=x[i]; x[i]:=x[j]; x[j]:=tg; 
 inc(i); dec(j); 
 end; 
 until i>j; 
 if j>l then quicksort(x,l,j); 
 if i<h then quicksort(x,i,h); 
end; 
procedure xuli; 
var i,j,d:integer; 
28 
Begin 
 i:=1;j:=1;d:=0;b[n+1]:=maxint; 
 repeat 
 while (a[i]<=a[j]) do inc(j); 
 if j<=n then inc(d); 
 inc(i);inc(j); 
 until (i>n) or (j>n); 
 write(f2,d); 
 end; 
procedure dongtep; 
begin 
close(f1); close(f2); 
end; 
BEGIN 
Taotep; doctep; quicksort(a,1,n); quicksort(b,1,n); 
xuli; dongtep; 
END. 
Bài 4. Tổ chức tham quan 
Trong đợt tổ chức tham quan danh lam thắng cảnh của thành phố Hồ Chí 
Minh, Ban tổ chức hội thi tin học trẻ tổ chức cho N đoàn (Đánh số từ 1 đến N) mỗi 
đoàn đi tham quan một địa điểm khác nhau. Đoàn thứ i thăm địa điểm cách khách 
sạn Hoàng Đế di km (i=1,..,n). Hội thi có m xe đánh số từ 1 đến m (m≥n) để phục 
vụ việc đưa các đoàn đi tham quan. Xe thứ j có mức tiêu thụ xăng là vj đơn vị thể 
tích/km 
Yêu cầu: Hãy chọn N xe để phục vụ việc đưa các đoàn đi tham quan, mỗi xe 
chỉ phục vụ một đoàn, sao cho tổng chi phí xăng cần sử dụng là ít nhất. 
Dữ liệu vào: File văn bản P2.inp 
- Dòng đầu tiên ghi hai số nguyên dương m, n 
- Dòng thứ hai ghi các số nguyên dương d1,..,dn. 
- Dòng thứ ba ghi các số nguyên dương v1,..,vm. 
 Kết quả: Ghi ra file văn bản P2.out 
29 
- Dòng đầu tiên ghi tổng số xăng cần dùng cho việc đưa các đoàn đi tham 
quan (Không tính lượt về) 
- Dòng thứ i trong N dòng tiếp theo ghi chỉ số xe phục vụ đoàn i (i=1,..,n) 
Ý tưởng: 
- Sắp xếp dãy số mức tiêu thụ xăng V của các xe theo thứ tự tăng dần. 
- Sắp xếp dãy số quảng đường đi của các đoàn theo thứ tự tăng dần. 
- Mức tiêu thụ xăng thấp nhất là: Min = ∑dn-i+1*vi với i=1,..,n. Chỉ số xe 
phục vụ các đoàn là giá trị từ 1 đến n trong dãy ID. 
 (Để ngắn gọn chương trình ta cũng có thể thực hiện sắp xếp dãy D theo thứ 
tự tăng dần (như bài Đua Ngựa) và tính Min = ∑dn-i+1*vi với i=1,..,n. Để tường 
minh và dễ hiểu tôi viết cả hai chiều sắp xếp) 
Chương trình tham khảo: 
const 
 fi=’P2.INP’; 
fo=’P2.OUT’; 
var F1,F2:TEXT; 
 d,v,id:array[1.. 1000]of integer; 
 n, m:longint; 
 min:longint; 
procedure taotep; 
begin 
Assign(f1,fi); assign(f2,fo); 
Reset(f1); rewrite(f2); 
end; 
procedure doctep; 
var i:longint; 
begin 
 fillchar(id,sizeof(id),0); 
 readln(f1,m,n); 
 for i:=1 to n do 
30 
 readln(f1,d[i]); 
 readln(f1); 
 for i:=1 to m do 
 begin 
 readln(f1,v[i]); 
 id[i]:=i; 
 end; 
 end; 
end; 
procedure quicksort(l,h:integer); 
var i,j,key,tg,tg1:integer; 
begin 
 i:=l; j:=h; 
 key:=v[(l+h) div 2]; 
 repeat 
 while v[i]<key do inc(i); 
 while v[j]>key do dec(j); 
 if i<=j then 
 begin 
 tg:=v[i]; v[i]:=v[j]; v[j]:=tg; 
 tg1:=id[i]; id[i]:=id[j]; id[j]:=tg1; 
 inc(i); dec(j); 
 end; 
 until i>j; 
 if j>l then quicksort(l,j); 
 if i<h then quicksort(i,h); 
end; 
procedure quicksort2(l,h:integer); 
var i,j,key,tg:integer; 
begin 
 i:=l; j:=h; 
31 
 key:=d[(l+h) div 2]; 
 repeat 
 while d[i]>key do inc(i); 
 while d[j]<key do dec(j); 
 if i<=j then 
 begin 
 tg:=d[i]; d[i]:=d[j]; d[j]:=tg; inc(i); dec(j); 
 end; 
 until i>j; 
 if j>l then quicksort(l,j); 
 if i<h then quicksort(i,h); 
end; 
procedure xuli; 
var i:integer;f:text; 
Begin 
 QuickSort(1,m); 
 QuickSort2(1,n); 
 min:=0; 
 for i:=1 to n do min:=min+v[i]*d[i]; 
 writeln(f2,min); 
 for i:=1 to n do Write(f2,id[i],' '); 
 end; 
procedure dongtep; 
begin 
close(f1); close(f2); 
end; 
BEGIN 
Taotep; doctep;xuli;dongtep; 
END. 
 Bài 5. Siêu thị BigC 
32 
 Ngày nghỉ cuối tuần An được mẹ cho đi siêu thị BigC để mua thực phẩm để 
dự trữ trong một tuần, vì mẹ An phải đi công tác dài ngày trong tuần tới. Sau khi 
chọn đủ các gói hàng cần mua, thanh toán tiền xong và đến lúc cần đóng hàng vào 
hộp để mang về nhà. Số gói hàng hai mẹ con chọn mua là n gói với kích thước k1, 
k2,,.,kn. An có nhiệm vụ giúp mẹ đóng những gói hàng này vào những chiếc hộp 
giấy bìa cứng. Biết rằng siêu thị chỉ còn những chiếc hộp có kích thước m thỏa 
mãn ki≤m (i=1,2,.,n). Hỏi An cần ít nhất bao nhiêu hộp để có thể đóng đầy đủ 
các gói hàng mang về? 
Dữ liệu: Vào từ file văn bản BIGC.INP 
- Dòng 1: Chứa 2 số nguyên n và m (1≤n≤100, m≥1000) 
- Dòng 2: Chứa số n số nguyên dương k1, k2,, k (1≤ki≤1000, với mọi 
i=1,2,,n) 
Kết quả: Ghi ra file văn bản BIGC.OUT gồm một số nguyên dương duy nhất là số 
hộp ít nhất cần phải lấy. 
Các số trên một dòng của input file được ghi cách nhau ít nhất một dấu cách. 
Ví dụ: 
BIGC.INP BIGC.OUT 
6 200 
30 70 150 80 120 75 
3 
Hướng dẫn giải: 
 Sắp xếp các gói hàng theo kích thước giảm dần, tiến hành đóng các gói vào 
hộp. Với mỗi hộp, duyệt lần lượt các gói hàng (theo thứ tự đã sắp xếp), gói nào còn 
có thể chứa được vào hộp thì cho vào luôn. 
 Với thuật toán này độ phức tạp O(nlogn) có thể được 100% số điểm của bài 
toán. 
 Bài 6. Giả số nguyên tố 
 Giả sử b là một số nguyên dương. Nếu p là hợp số nguyên dương và bp chia 
cho p được số dư là b thì p được gọi là giả số nguyên tố cơ sở b. 
 Yêu cầu:Cho n là số nguyên dương hãy liệt kê các giả số nguyên tố cơ sở 2 
trong phạm vi từ 1 đến n. 
 Dữ liệu: Vào từ file văn bản PSEPRIME.INP gồm một dòng chứa số 
nguyên dương n≤106. 
 Kết quả: Ghi ra file văn bản PSEPRIME.OUT là các giả số nguyên tố cơ sở 
2 trong phạm vi từ 1 đến n, mỗi số ghi trên một dòng theo thứ tự tăng dần. Nếu 
không tìm được số thỏa mãn yêu cầu, ghi số 0. 
33 
 Ví dụ: 
PSEPRIME.INP PSEPRIME.OUT 
1000 341 561 645 
Hướng dẫn giải: 
Sử dụng công thức (A x B) mod C =((A mod C) x (B mod C)) mode C để tính 2p 
mod p. 
Sử dụng kĩ thuật chia để trị để tính 2pmod p. Bước tiếp theo ta chỉ cần kiểm tra số 
lẻ trong phạm vi từ 1 đến p 
 III. Hiệu quả của sáng kiến 
 Sau khi áp dụng sáng kiến kinh nghiệm này cho đội tuyển HSG tại trường 
THPT Thái Hòa từ năm học 2015 đến nay đạt được kết quả như sau: 
 100% học sinh đội tuyển khi gặp các bài toán cùng dạng đã nhận thức được 
thực trạng không giải quyết các test lớn của chương trình, đồng thời biết vận dụng 
thuật toán chia để trị để giải quyết bài toán. 
C. KẾT LUẬN VÀ KIẾN NGHỊ 
Qua các phần trên chúng ta đã thấy được phần nào hiệu quả của phương 
pháp chia để trị. 
Với cách tư duy thông thường của học sinh khi giải quyết các bài toán trong 
đề thi HSG Tin học thì rất khó giải quyết khi gặp các Test lớn về giá trị và về mặt 
thời gian chương trình sẽ không tối ưu. Do đó học sinh nên vận dụng thuật toán 
chia để trị để giải quyết. Tuy nhiên,không phải bài toán nào ta cũng áp dụng được 
thuật toán này mà phải tùy vào nội dung bài toán để có hướng áp dụng cho phù 
hợp. Việc này đòi hỏi học sinh phải được tiếp xúc với rất nhiều các bài toán tương 
tự, khi đó kỹ năng áp dụng thuật toán vào các bài tập mới hoàn thiện. 
Trong đề tài của mình tôi đã cố gắng đưa ra được một số dạng bài tập 
thường gặp sử dụng thuật toán sắp xếp và tìm kiếm theo tư tưởng chia để trị mong 
rằng sẽ giúp ích cho giáo viên và học sinh trong quá trình giảng dạy và học tập. 
Do thời gian có hạn nên nội dung đề tài chắc chắn còn nhiều thiếu sót, rất 
mong nhận được phản hồi góp ý từ đồng nghiệp để có thể hoàn thiện hơn và áp 
dụng đề tài vào giảng dạy. 
34 
A. PHẦN MỞ ĐẦU .............................................................................................. 1 
I. Lí do chọn đề tài ........................................................................................... 2 
II. Mục đích của đề tài ............................................................................................ 2 
III. Đối tượng và phạm vi nghiên cứu ..................................................................... 2 
IV. Phương pháp nghiên cứu .................................................................................. 2 
B. NỘI DUNG SÁNG KIẾN KINH NGHIỆM ...................................................... 3 
I. Cơ sở lý luận: ...................................................................................................... 3 
II. Nội dung và giải pháp thực hiện ........................................................................ 3 
Áp dụng phương pháp chia để trị cho bài toán tìm kiếm:........................................ 7 
1. Bài toán tìm kiếm ..................................................................................... 7 
Bài toán áp dụng: ................................................................................................... 8 
Áp dụng phương pháp chia để trị cho bài toán sắp xếp: ........................................ 17 
1. Bài toán sắp xếp ..................................................................................... 17 
Bài toán áp dụng: ................................................................................................. 19 
III. Hiệu quả của sáng kiến ................................................................................... 33 
C. KẾT LUẬN VÀ KIẾN NGHỊ.......................................................................... 33 
D. TÀI LIỆU THAM KHẢO .............................................................................. 34 
D. TÀI LIỆU THAM KHẢO 
1. Tài liệu giáo khoa chuyên tin – quyển 1. Tác giả 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 2009 
2. Giải thuật và lập trình. Tác giả Lê Minh Hoàng 
Nhà xuất bản Đại học Sư phạm Hà Nội 2002 
3. Đề thi Học sinh giỏi tỉnh, Đề thi chọn dự tuyển Quốc gia của một số tỉnh 
35 
36 
https://123doc.net/document/3345297-phuong-phap-chia-de-tri.htm 
https://viblo.asia/p/tim-hieu-thuat-toan-chia-de-tri-va-cac-vi-du-ap-dung-
3Q75wkP95Wb 
https://xemtailieu.com/tai-lieu/skkn-hieu-qua-cua-chia-de-tri-trong-sap-xep-
va-tim-kiem-1122787.html