Sáng kiến kinh nghiệm Ứng dụng thuật toán đệ quy - khử đệ quy trong giảng dạy bồi dưỡng học sinh giỏi

+(n % 10); 
 } 
Trong đó: P là Tong(n), S là lệnh gán Tong = 0, S* là lệnh rỗng. 
Viết hàm bằng ngôn ngữ C++: 
 int TCS(int n) 
 { 
 if (n==0) return 0; 
 else 
 return (n % 10)+ TCS(n / 10); 
 } 
- Đệ quy nhị phân : 
+ Một hàm được gọi là đệ quy nhị phân nếu bên trong thân hàm 
có hai lời gọi hàm lại chính nó một cách trực tiếp có dạng sau: 
 9
P {if(điều kiện dừng) thực hiện S; 
 else 
 { 
 thực hiên S*; 
 gọi P; gọi P; 
 } 
 } 
 Với S, S* là các thao tác không đệ quy. 
Ví dụ: Hàm Fibo tính số hạng thứ n của dãy Fibonacci. 
Ta phân tích bài toán này dưới dạng đệ quy như sau: 
Gọi Fibo(n) là số hạng thứ n của dãy Fibonacci. Ta có: 
Fibo(n) {if((n==0)||(n==1)) Fibo=1; 
 else 
 Fibo=(Fibo(n-1)+Fibo(n-2)); 
 } 
Trong đó: P là Fibo(n), S là lệnh gán Fibo = 1, S* là lệnh rỗng. 
 Viết hàm bằng ngôn ngữ lập trình C++: 
int F(int n) 
 { 
 if (n==0) || (n==1) return 1; 
 else 
 return F(n-1)+F(n-2); 
 } 
 - Đệ quy phi tuyến 
Là dạng đệ quy trực tiếp mà lời gọi đệ quy được thực hiện bên 
trong vòng lặp có dạng như sau: 
P {if(điều kiện dừng) thực hiện S; 
 else 
 for (i=chỉ số đầu;i<=chỉ số 
cuối;i++) 
 { 
 thực hiên S*; 
 gọi P; 
 } 
 } 
 10
 Ví dụ: Cho dãy A(n) được xác định theo công thức sau: 






6n , 1)-A(n2)-A(n3)-A(n4)-A(n5)-A(n
6n , n 
A(n) 
 Gọi A(n) là tổng các số được xác định theo công thức trên. Ta 
có: 
 A(n) {if(n<6) s=n; 
 else 
 { 
 s=0; 
 for (i=5; i>=1;i--) 
 s=s+A(n-i); 
 } 
 A=s;} 
 Trong đó: P là A(n), S là lệnh gán s = n, S* là lệnh gán s = 0. 
int A(int n) 
{ 
int S,i; 
 if (n<6) S=n; 
 else 
 { 
 S=0; 
 for (i=5;i>=1;i--) 
 S= S + A (n-i); 
 } 
 return S; 
 } 
1.4. Chương trình con đệ quy 
1.4.1. Hàm đệ quy 
Hàm đệ quy là hàm mà trong thân hàm có lời gọi lại chính nó. 
Ví dụ: Hàm đệ quy tính n! 
double GT(int n) 
 { 
 if (n==0) return 1; 
 else 
 return n*GT(n-1); 
 11
 } 
1.4.2. Thủ tục đệ quy 
Thủ tục đệ quy là thủ tục có chứa lệnh gọi đến chính nó. Thủ tục đệ quy 
thường được sử dụng để mô tả các thao tác trên cấu trúc dữ liệu có tính đệ quy. 
Ví dụ: Thủ tục đệ quy in đảo ngược một số nguyên dương n cho trước như 
sau: 
void IDN(int n) 
 { 
 if (n<10) cout<<n; 
 else 
 { 
 Cout<<n % 10; 
 IDN(n / 10); 
 } 
 } 
1.5. Các bước xây dựng chương trình con đệ quy 
Để xây dựng thuật toán giải một bài toán có tính đệ quy bằng phương 
pháp đệ quy ta thực hiện 3 bước sau: 
 - Bước 1: Thông số hóa bài toán: 
+ Tổng quát hóa bài toán cụ thể cần giải thành bài toán tổng quát. 
+ Tìm ra các thông số cho bài toán tổng quát (các thông số điều khiển: các 
thông số mà độ lớn của chúng đặc trưng cho độ phức tạp của bài toán, và 
giảm đi một lần gọi đệ quy). 
 - Bước 2: Tìm các trường hợp neo cùng thuật toán giải tương ứng: 
+ Đây là những trường hợp suy biến của bài toán tổng quát, là các trường 
hợp tương ứng với giá trị biến của các biến điều khiển (trường hợp kích 
thước bài toán nhỏ nhất) mà thuật toán giải không đệ quy. 
- Bước 3: Tìm thuật toán giải trong trường hợp tổng quát bằng cách phân 
rã bài toán theo kiểu đệ quy: 
+ Tìm thuật toán giải bài toán trong trường hợp tổng quát bằng cách phân 
nó thành các thành phần: 
 - Thuật toán không đệ quy 
 - Bài toán trên nhưng có kích thước nhỏ hơn 
Ví dụ: Tính số hạng thứ n của dãy số Fibonacci được định nghĩa: 
 12






1n khi FF
1n0n khi 1
F
2-n1-n
n 
Xây dựng chương trình con đệ quy để giải bài toán trên theo 3 bước như 
sau: 
Bước 1: Ta gọi thuật toán giải bài toán ở mức tổng quát là hàm Fibo(n) 
chứa 1 thông số n, với n thuộc kiểu số nguyên và n là thông số quyết định 
độ phức tạp của bài toán. 
 Bước 2: Với n<2 thì trả về kết quả là Fibo(n) = 1 và dừng thuật toán. 
 Bước 3: Trong trường hợp tổng quát với n>2 thì: 
 Fibo(n) = Fibo(n-1)+Fibo(n-2). 
1.6. Cơ chế thực hiện thuật toán đệ quy 
Trạng thái của tiến trình xử lý một thuật toán ở một thời điểm được đặc 
trưng bởi các biến và lệnh cần thực hiện kế tiếp. Với tiến trình xử lý một thuật 
toán đệ quy ở từng thời điểm thực hiện, cần lưu trữ cả các trạng thái xử lý đang 
còn dang dở. 
Đặc điểm của cơ chế thực hiện thuật toán đệ quy là việc thực thi lời gọi đệ 
quy sinh ra lời gọi đệ quy mới cho đến khi gặp trường hợp neo (trường hợp suy 
biến) cho nên để thực thi thuật toán đệ quy cần có cơ chế lưu trữ thông tin thỏa 
các yêu cầu sau: 
- Ở mỗi lần gọi phải lưu trữ thông tin trạng thái con dang dở của tiến trình 
xử lý ở thời điểm gọi. Số trạng thái này bằng số lần gọi chưa được hoàn 
tất. 
- Khi thực hiện xong một lần gọi, cần khôi phục lại toàn bộ thông tin trạng 
thái trước khi gọi. 
- Lệnh gọi cuối cùng (ứng với trường hợp neo) sẽ được hoàn tất đầu tiên, 
thứ tự dãy các lệnh gọi được hoàn tất ngược với thứ tự gọi, tương ứng dãy 
thông tin trạng thái được hồi phục theo thứ tự ngược với thứ tự lưu trữ. 
Cấu trúc dữ liệu cho phép lưu trữ dãy thông tin thỏa 3 yêu cầu trên là câu 
trúc lưu trữ thỏa luật LIFO (Last In First Out). Một kiểu cấu trúc lưu trữ thường 
được sử dụng trong trường hợp này là cấu trúc ngăn xếp (Stack). 
Ví dụ 1: Xét thuật toán đệ quy tính n giai thừa: 
Ta có: GT(n) { if n=0 GT=1 
 else GT=n*GT(n-1); } 
 13
Giả sử với n = 3, khi đó thuật toán đệ quy tính n giai thừa sẽ được thực 
hiện như sau: 
Các lời gọi đệ quy khi thực hiện hàm GT(3) 
Qua hình 2, ta thấy khi thực hiện lời gọi GT(3) sẽ phát sinh lời gọi GT(2), 
đồng thời phải lưu trữ thông tin trạng thái xử lý còn dang dở (GT(3)=3*GT(2)), 
để thực hiện lời gọi GT(2) thì lại phát sinh lời gọi GT(1), đồng thời vẫn phải lưu 
trữ thông tin trạng thái xử lý còn dang dở (GT(2)=2*GT(1)), cứ tiếp tục như vậy 
cho đến khi gặp trường hợp neo GT(0)=1. 
Tiếp sau quá trình gọi là quá trình xử lý ngược được thực hiện như sau: 
- Dùng GT(0) để tính GT(1) theo sơ đồ xử lý còn lưu trữ. 
- Dùng GT(1) để tính GT(2) theo sơ đồ xử lý còn lưu trữ. 
- Dùng GT(2) để tính GT(3) theo sơ đồ xử lý còn lưu trữ. 
Đồng thời với quá trình xử lý ngược là quá trình xóa bỏ các thông tin về 
thuật toán xử lý trung gian (quá trình thu hồi bộ nhớ). 
Ví dụ 2: Xét thuật toán tính tính số Fibonacci thứ n như sau: 
Fib(n){if((n==0)||(n==1)) Fib=1; 
 else 
 Fib= Fib(n-1)+Fib(n-2); 
 } 
Lời gọi Fibo(5) sẽ dẫn đến việc thực hiện theo sơ đồ sau: 
GT(3)=3*GT(2) 
GT(2)=2*GT(1) 
GT(1)=1*GT(0) 
GT(0)=1 
 14
Các lời gọi đệ quy được thực hiện khi gọi hàm Fib(5) 
Khi thực hiện lời gọi Fib(5) sẽ phát sinh lời gọi Fib(4) tiếp đến là lời gọi 
Fib(3), đến khi thực hiện lời gọi Fib(4) lại dẫn đến lời gọi Fib(3) và Fib(2) và cứ 
tiếp tục như vậy cho đến khi gặp trường hợp neo Fib(1) hoặc Fib(0) thì dừng 
việc gọi đệ quy. Tiếp sau quá trình gọi là quá trình xử lý ngược được thực hiện 
để cho ra kết quả Fib(5). 
Qua hai ví dụ minh họa về cơ chế hoạt động của thuật toán đệ quy, ta rút 
ra được một nhận xét đó là mặc dù chương trình đệ quy ngắn gọn, thể hiện rõ 
bản chất của vấn đề cần giải quyết nhưng hoạt động của chương trình đệ quy 
không tường minh, làm người đọc khó hiểu, khó hình dung chương trình sẽ tính 
toán như thế nào trong lúc chạy chậm chương trình. 
1.7. Một số bài toán về đệ quy 
1.7.1. Bài toán tháp Hà Nội 
Có 3 cột A, B, C và cột A hiện có n đĩa, trong đó, đĩa nhỏ được nằm trên 
đĩa lớn. Yêu cầu của bài toán là hãy chuyển n đĩa từ cột A sang cột C theo cách: 
- Mỗi lần chỉ chuyển 1 đĩa. 
- Khi chuyển có thể dùng cột trung gian B. 
- Trong suốt quá trình chuyển các đĩa ở các cột thì đĩa có kích thước 
lớn hơn phải được đặt ở dưới. 
Fib(5)=Fib(4)+Fib(3) 
Fib(3)=Fib(2)+Fib(1) 
Fib(3)=Fib(2)+Fib(1) Fib(2)=Fib(1)+Fib(0) 
Fib(4)=Fib(3)+Fib(2) 
Fib(1)=1 Fib(2)=Fib(1)+Fib(0) 
Fib(2)=Fib(1)+Fib(0) Fib(1)=1 Fib(1)=1 Fib(0)=1 Fib(1)=1 Fib(0)=1 
Fib(0)=1 Fib(1)=1 
 15
Hình 1. Bài toán Tháp Hà Nội 
Phân tích bài toán 
Xác định Input, Output: 
- Input: số lượng đĩa n, 3 cột A, B, C. 
- Output: in ra màn hình quy trình để chuyển n đĩa từ cột A sang cột 
C đúng quy định. 
Phân tích bài toán: 
- Trường hợp n = 1: chuyển đĩa từ cột A sang cột C 
- Trường hợp n = 2: 
+ Chuyển đĩa thứ nhất từ cột A sang cột B. 
+ Chuyển đĩa thứ hai từ cột A sang cột C. 
+ Chuển đĩa thứ nhất từ cột B sang cột C. 
- Trường hợp n>2: 
+ Chuyển (n-1) đĩa từ cột A sang cột B. 
+ Chuyển đĩa thứ n từ cột A sang cột C. 
+ Chuển (n-1) đĩa từ cột B sang cột C. 
Thông số hóa bài toán 
Ta gọi thuật toán giải bài toán ở mức tổng quát là thủ tục 
ThapHN(n,A,B,C) chứa 4 thông số n, A, B, C. Trong đó, n thuộc kiểu số 
nguyên, A, B, C thuộc kiểu ký tự và trong 4 thông số thì thông số n là thông số 
quyết định độ phức tạp của bài toán. 
Trường hợp neo và thuật toán tương ứng 
Với n = 1, bài toán tổng quát suy biến thành bài toán đơn giản 
ThapHN(1,A,B,C) và trong trường hợp này thuật toán giải bài toán 
ThapHN(1,A,B,C) chỉ thực hiện một thao tác cơ bản đó là chuyển 1 đĩa từ cột A 
sang cột C (sử dụng lệnh đưa thông báo bước chuyển ra màn hình). 
Phân rã bài toán trong trường hợp tổng quát 
Ta có thể phân rã bài toán ThapHN(k,A,B,C): chuyển k (k>1) đĩa từ cột A 
sang cột C lấy cột B làm cột trung gian ta thực hiện tuần tự 3 công việc sau: 
Cột A Cột B Cột C 
 16
- Chuyển (k-1) đĩa từ cột A sang cột B lấy cột C làm cột trung gian 
khi đó ta có thủ tục ThapHN(k-1,A,C,B) (bài toán ThapHN với 
n=k-1, A=A, B=C, C=B). 
- Chuyển 1 đĩa thứ k từ cột A sang cột C: đưa thông báo bước 
chuyển ra màn hình 
- Chuyển (k-1) đĩa từ cột B sang cột C lấy cột A làm cột trung gian 
khi đó ta có thủ tục ThapHN(k-1,B,A,C) (bài toán ThapHN với 
n=k-1, A=B, B=A, C=C). 
Vậy thuật toán trong trường hợp tổng quát (n>1) là: 
 ThapHN(n,A,B,C) { ThapHN(k-1,A,C,B); 
 writeln(A,’->’,C); 
 ThapHN(k-1,B,A,C); 
 } 
Mã hóa thuật toán 
#include 
using namespace std; 
void THN(int n , char a, char b, char c ){ 
 if(n==1){ 
 cout<<"\t"<<a<<"-------"<<c<<endl; 
 return; 
 } 
 THN(n-1,a,c,b); 
 THN(1,a,b,c); 
 THN(n-1,b,a,c); 
} 
int main(){ 
 char a='A', b='B', c='C'; 
 int n; 
 cout<<"Nhap n: "; 
 cin>>n; 
 THN(n,a,b,c); 
} 
 17
1.7.2. Bài toán chia thưởng 
Có m phần thưởng đem chia cho n học sinh giỏi đã được xếp hạng sao cho 
học sinh giỏi hơn không ít phần thưởng hơn. Có bao nhiêu cách khác nhau để 
thực hiện cách chia? 
Ta thấy ngay rằng việc tìm ra lời giải cho bài toán sẽ không dễ dàng nếu ta 
không tìm ra cách thích hợp để tiếp cận với nó. Ta sẽ tìm thuật toán giải bài toán 
bằng phương pháp đệ quy. 
Phân tích bài toán 
Xác định Input, Output của bài toán: 
- Input: m, n 
- Output: số cách chia. 
Ta mã hóa n đối tượng theo thứ tự xếp hạng 1, 2, 3, 4, , n và Si là số 
phần thưởng mà học sinh thứ i nhận được. 
Khi đó, các điều kiện ràng buộc lên cách chia là: 
 Si0 
 S1 S2 S3 S4 Sn 
 S1 + S2 + S3 + S4 + + Sn = m 
Ví dụ: Với m = 5 và n = 3 ta có 5 cách chia như sau: 
 5 0 0 
 4 1 0 
 3 2 0 
 3 1 1 
 2 2 1 
Thông số hóa bài toán 
Ta sẽ giải bài toán ở mức độ tổng quát: Tìm số cách chia m vật (phần 
thưởng) cho n đối tượng (học sinh) có thứ tự. 
Gọi Chiathuong(m,n) là số cách chia m vật (phần thưởng) cho n đối tượng 
(học sinh). Chiathuong là hàm của hai biến m, n. 
Trường hợp neo và thuật toán tương ứng 
Khi m = 0: có duy nhất một cách chia, đó là mọi học sinh đều nhận được 0 
phần thưởng. Khi đó, ChiaThuong(0,n) = 1. 
Khi n = 0, m  0: không có cách nào để thực hiện việc chia. Khi đó, 
Chiathuong(m,0) = 0, với mọi m  0. 
 18
Khi n = 1, m 0: có duy nhất một cách chia, đó là m phần thưởng đều 
chia cho một học sinh. Khi đó, ta có Chiathuong(m,1) = 1. Vậy ta có thể thay 
trường hợp neo Chiathuong(m,0) = 0 bằng trường hợp Chiathuong(m,1) = 1. 
Phân rã bài toán trong trường hợp tổng quát 
Khi m<n (số phần thưởng m nhỏ hơn số học sinh n) thì n-m học sinh xếp 
cuối sẽ luôn không nhận được gì cả trong mọi cách chia. Khi đó, ta có 
Chiathuong(m,n) = Chiathuong(m,m). 
Khi mn (số phần thưởng m lớn hơn hoặc bằng số học sinh n) thì ta các 
cách chia làm hai nhóm: 
- Nhóm thứ nhất không dành cho học sinh xếp cuối cùng phần thưởng 
nào cả (Sn = 0). Số cách chia này sẽ bằng số cách chia m phần thưởng cho 
n-1 học sinh. Khi đó, số cách chia trong nhóm thứ nhất bằng hàm 
Chiathuong(m,n-1). 
- Nhóm thứ hai có phần thưởng cho người cuối cùng (Sn > 0). Dễ thấy 
rằng số cách chia của nhóm này bằng số cách chia m-n phần thưởng cho n 
học sinh (vì phương thức chia mà tất cả học sinh đều nhận được phần 
thưởng có thể thực hiện bằng cách cho mỗi người nhận trước một phần 
thưởng rồi mới chia). Khi đó, số cách chia trong nhóm thứ hai bằng hàm 
Chiathuong(m-n,n). 
- Vậy khi mn: Chiathuong(m,n) = Chiathuong(m,n-1) + 
Chiathuong(m-n,n). 
Mã hóa thuật toán 
#include 
using namespace std; 
int Chiathuong(int m,int n) 
 { 
 if ((m==0)||(n==1)) return 1; 
 else 
 if (m<n) return Chiathuong(m,m); 
 else 
 return Chiathuong(m,n-1)+Chiathuong(m-n,n); 
 } 
 int main(){ 
 cout<<"chia thuong "<<Chiathuong(2,7); 
 19
 return 0; 
 } 
1.7.3. Bài toán sắp xếp mảng – Thuật toán sắp xếp nhanh 
Sắp xếp là một bài toán thường gặp, ngoài ý nghĩa tổ chức lại dữ liệu theo 
một yêu cầu nào đó, việc sắp xếp còn tạo thuận lợi cho việc tìm kiếm. Có nhiều 
phương pháp sắp xếp khác nhau, trong đó Quicksort là một phương pháp sắp 
xếp được nghiên cứu và sử dụng rộng rãi trong lớp các thuật toán sắp xếp. 
Các đối tượng dữ liệu cần sắp xếp thường có nhiều thuộc tính, về cấu trúc 
dữ liệu được tổ chức khá đa dạng, và ta cần chọn một khóa để sắp xếp dữ liệu 
theo khóa này. Ví dụ như mô tả đối tượng con người có các thuộc tính cơ bản 
như họ tên, ngày sinh, giới tính, v.v.., và thuộc tính họ tên được chọn làm khóa 
để sắp xếp. Tuy nhiên, để thuận lợi cho việc trình bày cũng như tập trung vào 
thuật toán ta sẽ làm việc với mảng đơn giản gồm các số nguyên. 
Đối với các bài toán sắp xếp được xét ở đây chúng ta sẽ quan tâm tới việc 
sắp xếp mảng các số nguyên theo thứ tự không giảm. 
Phân tích bài toán 
Xác định Input, Output: 
- Input: mảng số nguyên gồm n phần tử 
- Output: mảng số nguyên được sắp xếp theo thứ tự không giảm. 
Ý tưởng cơ bản của Quicksort dựa trên phương pháp chia để trị và được 
mô tả dưới dạng đệ quy. Đầu tiên chọn một phần tử trong mảng làm mốc, sau đó 
chia mảng thành hai phần ở hai phía của mốc: các phần tử lớn hơn mốc được 
chuyển sang phải mốc và các phần tử không lớn hơn mốc được chuyển sang trái 
mốc. Để có được sự phân chia này, các phần tử sẽ được so sánh với mốc và hoán 
đổi vị trí cho nhau hoặc cho mốc nếu nó lớn hơn mốc mà lại nằm bên trái hoặc 
không lớn hơn mốc mà lại nằm bên phải. Áp dụng kỹ thuật trên cho hai phần 
vừa được chia và tiếp tục thực hiện như vậy cho đến khi mỗi mảng con chỉ còn 
một phần tử. Khi đó toàn bộ mảng đã được sắp xếp không giảm. 
Giả sử để chia mảng A[d..c] thành hai phần thỏa mãn yêu cầu trên. Ta tiến 
hành các bước cụ thể như sau: 
 - Lấy một phần tử trong mảng làm mốc. Ở đây ta sẽ chọn phần tử đầu tiên 
của mảng làm mốc là A[d]. 
 - Tiến hành duyệt mảng A đồng thời từ hai đầu, dùng hai biến i, j để duy trì 
hai vị trí duyệt. Khởi tạo i = d+1 và j = c. Duyệt từ bên trái mảng và tăng i cho 
tới khi gặp một phần tử có giá trị lớn hơn mốc (A[i]>A[d]), đồng thời tiến hành 
 20
duyệt từ bên phải sang và giảm j cho tới khi gặp một phần tử có giá trị nhỏ hơn 
hoặc bằng mốc (A[j]A[d]). Rõ ràng hai phần tử này nằm ở những vị trí không 
phù hợp khi đó đổi chỗ A[i] và A[j]. Quá trình này còn tiếp tục khi nào mà i<j. 
Cuối cùng đổi chỗ A[d] và A[j] để đặt mốc đúng chỗ. 
Ví dụ: Cho mảng A gồm 5 phần tử sau: 
Chỉ số 1 2 3 4 5 6 7 
Giá trị 15 6 18 1 12 24 49 
Chọn mốc: A[1] = 15; biến duyệt ban đầu: i = 2, j = 7. 
Quá trình duyệt từ bên trái với biến i sẽ dừng lại tại phần tử thứ 3, 
A[3]=18, vì đây là phần tử có giá trị lớn hơn mốc. 
Quá trình duyệt từ bên phải với biến j sẽ dừng lại tại phần tử thứ 5, 
A[5]=12, vì đây là phần tử có giá trị nhỏ hơn mốc. 
Chỉ số 1 2 3 4 5 6 7 
Giá trị 15 6 18 1 12 24 49 
Vì i<j nên ta đổi chỗ (A[i],A[j]) thu được mảng A có giá trị sau: 
Chỉ số 1 2 3 4 5 6 7 
Giá trị 15 6 12 1 18 24 49 
Tiếp tục quá trình duyệt, hai biến i, j gặp nhau (i = j) quá trình duyệt dừng 
lại, cuối cùng ta đổi chỗ (A[1],A[j]), khi đó mảng A được phân thành hai nữa 
như sau: 
Chỉ số 1 2 3 4 5 6 7 
Giá trị 1 6 12 15 18 24 49 
Thông số hóa bài toán 
Ta gọi thuật toán giải bài toán ở mức tổng quát là thủ tục SXnhanh(A[n], 
d, c), sắp xếp mảng A gồm n ứng với chỉ số đầu d và chỉ số cuối c theo thứ tự 
không giảm. Trong đó, n thuộc kiểu số nguyên và n chính là thông số quyết định 
độ phức tạp của bài toán. 
Trường hợp neo và thuật toán tương ứng 
Khi d = c, thuật toán sẽ dừng lại và hoàn tất việc sắp xếp. 
j 
i 
j 
i 
 21
Phân rã bài toán trong trường hợp tổng quát 
Ta có thể phân rã bài toán SXnhanh(A[n],d,c) theo kiểu đệ quy được biểu 
diễn bởi thuật toán sau: 
void SXnhanh(int A[100],int low,int hight) 
{ 
int pivot; 
 if (low<hight) 
 { 
 pivot = Chia(A,low,hight); //chia mảng A 
thành hai phần 
 Sxnhanh(A,low,pivot-1); 
 Sxnhanh(A,pivot+1,hight); 
 } 
} 
Mã hóa thuật toán 
#include 
#include 
using namespace std; 
void swap(int &a, int &b) 
{ 
 int tg = a; 
 a = b; 
 b = tg; 
} 
int Chia(int a[], int low, int high) 
{ 
 int pivot = a[high]; // pivot 
 int left = low; 
 int right = high - 1; 
 while(true){ 
 while(left <= right && a[left] < pivot) left++; 
 while(right >= left && a[right] > pivot) right--; 
 if (left >= right) break; 
 swap(a[left], a[right]); 
 left++; 
 22
 right--; 
 } 
 swap(a[left], a[high]); 
 return left; 
} 
void SXNhanh(int a[], int low, int high) 
{ 
 if (low < high) 
 { 
 /* pi là chỉ số nơi phần tử này đã đứng đúng 
vị trí và là phần tử chia mảng làm 2 mảng con trái & 
phải */ 
 int pi = Chia(a, low, high); 
 // Gọi đệ quy sắp xếp 2 mảng con trái và phải 
 SXNhanh(a, low, pi - 1); 
 SXNhanh(a, pi + 1, high); 
 } 
} 
/* Hàm xuất mảng */ 
void inmang(int a[], int size) 
{ 
 int i; 
 for (i=0; i < size; i++) 
 cout<<a[i]<<" "; 
 cout<<"\n"; 
} 
int main() 
{ 
 int a[] = {100,10, 80, 30, 20, 40, 50, 70}; 
 int n = sizeof(a)/sizeof(a[0]); 
 SXNhanh(a, 0, n-1); 
 cout<<"Sorted array: \n"; 
 inmang(a, n); 
 return 0; 
} 
 23
1.7.4. Bài toán tìm kiếm – Thuật toán tìm kiếm nhị phân 
Tìm kiếm nhị phân là một trong những phương pháp tìm kiếm phổ biến, 
một phương pháp tìm kiếm hiệu quả về mặt thời gian và thuật toán dựa trên kỹ 
thuật chia để trị. 
Phương pháp tìm kiếm nhị phân là phương pháp dùng để tìm kiếm một 
phần tử trong một mảng gồm n phần tử đã được sắp xếp theo thứ tự (ở đây ta xét 
trường hợp mảng được sắp theo thứ tự không giảm). 
Phân tích bài toán 
Xác định Input, Output: 
- Input: Mảng A gồm n phần tử đươc sắp theo thứ tự không giảm. Phần tử 
cần tìm là x. 
- Output: Vị trí của phần tử có giá trị x trong mảng A. 
Ý tưởng: Vì mảng đã được sắp theo thứ tự vì vậy ta dựa trên cách tiếp cận 
chia để trị ta sẽ chia phạm vi tìm kiếm thành hai phần và xác định sẽ tiếp tục tìm 
kiếm ở phần nào. Quá trình được lặp lại cho đến khi phạm vi tìm kiếm chỉ còn 
một phần tử và giá trị của phần tử đó bằng giá trị cần tìm hoặc đã tìm đươc phần 
tử có giá trị bằng giá trị cần tìm . 
Giả sử phạm vi đang tìm kiếm là [d,c], khi dó ta chia mảng thành hai phần 
có kích thước gần bằng nhau bởi vị trí giữa g. Do tính chất sắp theo thứ tự không 
giảm của mảng nên ta thấy: 
- Nếu A[g] = x thì ta dừng thuật toán và thông báo kết quả là g. 
- Ngược lại, nếu x>A[g] thì phạm vi tìm kiếm tiếp tục sẽ là [g+1,c]. 
Ngược lại (x<A[g]) thì phạm vi tìm kiếm tiếp tục sẽ là [d,g-1]. 
- Quá trình được lặp lại tương tự cho nửa phạm vị vừa được xác định 
cho đến khi phạm vi tìm kiếm chỉ còn một phần tử và giá trị của 
phần tử đó bằng x hoặc đã tìm đươc vị trí của phần tử có giá