THUẬT TOÁN NÂNG CAO
NHÓM THỰC HIỆN: NHÓM 2
HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
Đệ quy
Gvhd: ts.nguyễn xuân hải
www.ptit.edu.vn
NHÓM THỰC HIỆN: NHÓM 2
DANH SÁCH THÀNH VIÊN NHÓM:
1. Nguyễn Duy Hưng
2. Trần Danh Hưng
3. Hoàng Thị Diễm Hương
4. Võ Thị Diễm Hương
5. Võ Hà Quốc Huy
6. Nguyễn Đức Huy
7. Phạm Thị Thanh Huyền
www.ptit.edu.vn
NHÓM THỰC HIỆN: NHÓM 2
NỘI DUNG
I – TỔNG QUAN VỀ ĐỆ QUY
1. Khái niệm về đệ quy
2. Một số bài toán điển hình
A. Dãy số Fibonacci
B. Bài toán tháp Hà Nội
C. Bài toán 8 con hậu
II – KHỬ ĐỆ QUY (QUICK SORT):
3. Tổng quan về thuật toán Quick Sort
A. Giới thiệu thuật toán Quick Sort
B. Ý tưởng thuật toán Quick Sort
C. Giải thuật Quick Sort
D. Cài đặt Quick Sort
E. Ví dụ

F. Hiệu quả thuật toán Quick Sort
4. Khử đệ quy thuật toán Quick Sort
www.ptit.edu.vn
NHÓM THỰC HIỆN: NHÓM 2
I. TỔNG QUAN VỀ ĐỆ QUY
1. Khái niệm về đệ quy

Đệ quy là một khái niệm cơ bản trong toán học và khoa học
máy tính. Một đối tượng được gọi là đệ quy nếu nó hoặc một
phần của nó được định nghĩa thông qua khái niệm về chính nó.

Trong lĩnh vực lập trình: 1 chương trình gọi là đệ quy nếu nó
gọi lại chính nó.

Chương trình đệ quy luôn kiểm tra điều kiện dừng:

Nếu không thỏa, tiếp tục gọi đệ quy.

Nếu thỏa mãn  không gọi chính nó nữa, chấm dứt đệ quy.
www.ptit.edu.vn
NHÓM THỰC HIỆN: NHÓM 2

Ví dụ:

Định nghĩa số tự nhiên:
•
0 là số tự nhiên.
•
Nếu k là số tự nhiên thì k+1 cũng là số tự nhiên.


Định nghĩa xâu kí tự (chuỗi kí tự) bằng đệ quy:
•
Xâu rỗng là xâu kí tự
•
Một chữ cái bất kì ghép với 1 xâu sẽ tạo thành xâu mới

Định nghĩa hàm giai thừa n!:
•
Khi n = 0, định nghĩa 0! = 1
•
Khi n>0, định nghĩa n! = (n-1)! * n
I. TỔNG QUAN VỀ ĐỆ QUY
1. Khái niệm về đệ quy
www.ptit.edu.vn
NHÓM THỰC HIỆN: NHÓM 2

Đặc điểm của chương trình đệ quy:

Chương trình có thể gọi chính nó.

Khi chương trình gọi chính nó thì mục đích là để giải quyết một
vấn đề tương tự nhưng nhỏ hơn.

Vấn đề nhỏ hơn này một lúc nào đó sẽ đơn giản tới mức chương
trình có thể tự giải quyết mà không cần phải gọi chính nó nữa.
I. TỔNG QUAN VỀ ĐỆ QUY
1. Khái niệm về đệ quy
www.ptit.edu.vn
NHÓM THỰC HIỆN: NHÓM 2


Để xây dựng 1 chương trình đệ quy  1 công thức đệ quy.

Công thức này gồm 2 phần:

Phần đệ quy (recursive case)

Phần cơ bản (base case)

Ví dụ:

Định nghĩa hàm giai thừa n!:
•
Khi n = 0, định nghĩa 0! = 1
•
Khi n>0, định nghĩa n! = (n-1)! * n
I. TỔNG QUAN VỀ ĐỆ QUY
1. Khái niệm về đệ quy
base case
recursive case
www.ptit.edu.vn
NHÓM THỰC HIỆN: NHÓM 2

Ưu điểm của chương trình đệ quy:

Có thể thực hiện một lượng lớn các thao tác tính toán thông qua
1 đoạn chương trình ngắn gọn.

Có thể định nghĩa một tập vô hạn các đối tượng thông qua 1 số
hữu hạn lời phát biểu.


Nhược điểm:

Khi một hàm đệ quy gọi chính nó thì tập các đối tượng được sử
dụng trong hàm này như: biến, hằng, cấu trúc… và các thông số
cần cho việc chuyển giao điều khiển sẽ được sinh ra.

Đôi khi tạo ra những tính toán thừa, không cần thiết do tính chất
tự động gọi thực hiện thủ tục khi chưa kết thúc đệ quy.
I. TỔNG QUAN VỀ ĐỆ QUY
1. Khái niệm về đệ quy
Khi nào nên/không nên sử dụng đệ quy?
Nếu chương trình có thể viết dưới dạng lặp hoặc các cấu trúc
lệnh khác thì không nên sử dụng đệ quy.
www.ptit.edu.vn
NHÓM THỰC HIỆN: NHÓM 2
9
Minh họa: Chương trình tính giai thừa của một số tự nhiên
được cho như sau:
int GT (int N)
{
if (N==0)
GT=1;
else
GT=N*GT(N-1);
}
 Tính GT(5)?
I. TỔNG QUAN VỀ ĐỆ QUY
1. Khái niệm về đệ quy
www.ptit.edu.vn
NHÓM THỰC HIỆN: NHÓM 2

CT chính: Chưa xong: answer  GT(5)
GT. 1st: N=5, Chưa xong: 5*GT(4)
GT. 2nd: N=4, Chưa xong: 4*GT(3)
GT. 3rd: N=3, Chưa xong: 3*GT(2)
GT. 4th: N=2, Chưa xong: 2*GT(1)
GT. 5th: N=1, Chưa xong: 1*GT(0)
GT. 6th: N=0, Xong: return 1
I. TỔNG QUAN VỀ ĐỆ QUY
1. Khái niệm về đệ quy

Quy trình thực hiện:
www.ptit.edu.vn
NHÓM THỰC HIỆN: NHÓM 2
CT chính: Chưa xong: answer  GT(5)
GT. 1st: N=5, Chưa xong: 5*GT(4)
GT. 2nd: N=4, Chưa xong: 4*GT(3)
GT. 3rd: N=3, Chưa xong: 3*GT(2)
GT. 4th: N=2, Chưa xong: 2*GT(1)
GT. 5th: N=1, Chưa xong: 1*GT(0)
GT. 6th: N=0, Xong: return 1
I. TỔNG QUAN VỀ ĐỆ QUY
1. Khái niệm về đệ quy

Quy trình thực hiện:
GT. 5th: N=1, Xong: 1*1
GT. 4th: N=2, Xong: 2*1
GT. 3rd: N=3, Xong: 3*2
GT. 2nd: N=4, Xong: 4*6
GT. 1st: N=5, Xong: 5*24
CT chính: Xong: answer  120

www.ptit.edu.vn
NHÓM THỰC HIỆN: NHÓM 2
Nhận xét: Kỹ thuật đệ quy:
Kết luận:
•
Hạn chế sử dụng đệ quy nếu có thể sử dụng một phương pháp khác.
•
Có thể thay thế bằng lời giải không đệ quy (khử đệ quy) bằng
phương pháp lặp

Sẽ được trình bày cụ thể ở một số thuật toán
trong những phần sau.
Ưu điểm Khuyết điểm
Thuận lợi cho việc biểu
diễn bài toán
Có khi không được tối ưu
về thời gian
Gọn (đối với chương trình) Có thể gây tốn bộ nhớ
I. TỔNG QUAN VỀ ĐỆ QUY
1. Khái niệm về đệ quy
www.ptit.edu.vn
NHÓM THỰC HIỆN: NHÓM 2
A. Dãy số Fibonacci
B. Bài toán tháp Hà Nội
C. Bài toán 8 con hậu
I. TỔNG QUAN VỀ ĐỆ QUY
2. Một số bài toán điển hình
www.ptit.edu.vn
NHÓM THỰC HIỆN: NHÓM 2
I. TỔNG QUAN VỀ ĐỆ QUY

2. Một số bài toán điển hình
A. Dãy số Fibonacci:
www.ptit.edu.vn
NHÓM THỰC HIỆN: NHÓM 2
A. Dãy số Fibonacci (tt):
Phát biểu bài toán:
Dãy số F(n) được cho bởi công thức truy hồi như sau:

Tính số hạng thứ n của dãy?
I. TỔNG QUAN VỀ ĐỆ QUY
2. Một số bài toán điển hình
www.ptit.edu.vn
NHÓM THỰC HIỆN: NHÓM 2
I. TỔNG QUAN VỀ ĐỆ QUY
2. Một số bài toán điển hình
A. Dãy số Fibonacci (tt):
int Fibonacci (int n)
{
if (n<=1)
return 1;
else
return Fibonacci(n-1) + Fibonacci(n-2);
}
www.ptit.edu.vn
NHÓM THỰC HIỆN: NHÓM 2
B. Bài toán tháp Hà Nội
Phát biểu bài toán:

Có 3 chiếc cọc và bộ n đĩa. Các đĩa này có kích thước khác
nhau, các đĩa đều có lỗ để xuyên chúng qua đầu cọc.


Ban đầu các đĩa đều nằm trên 1 cọc, trong đó đĩa nhỏ sẽ nằm
trên đĩa lớn.

Yêu cầu: chuyển bộ n đĩa từ cọc ban đầu A sang cọc đích C
sao cho vẫn đảm bảo nguyên tắc đĩa nhỏ trên đĩa lớn dưới.
I. TỔNG QUAN VỀ ĐỆ QUY
2. Một số bài toán điển hình
www.ptit.edu.vn
NHÓM THỰC HIỆN: NHÓM 2
A
B C
1 đĩa
B. Bài toán tháp Hà Nội (tt):
I. TỔNG QUAN VÊ ĐỆ QUY
2. Một số bài toán điển hình
www.ptit.edu.vn
NHÓM THỰC HIỆN: NHÓM 2
A
B C
2 đĩa
B. Bài toán tháp Hà Nội (tt):
I. TỔNG QUAN VỀ ĐỆ QUY
2. Một số bài toán điển hình
www.ptit.edu.vn
NHÓM THỰC HIỆN: NHÓM 2
A
B C
N đĩa
B. Bài toán tháp Hà Nội (tt):

I. TỔNG QUAN VỀ ĐỆ QUY
2. Một số bài toán điển hình
www.ptit.edu.vn
NHÓM THỰC HIỆN: NHÓM 2

Nhận xét:

Ở đây ta thấy bài toán chuyển n đĩa thành bài toán đơn giản
hơn là chuyển n-1 đĩa.

Điểm dừng của thuật toán là n = 1, ta chuyển thẳng đĩa này
từ cọc ban đầu sang cọc đích.

Bài toán chuyển n đĩa được chia làm 2 bài toán nhỏ hơn là
chuyển n-1 đĩa:
•
Lần 1: chuyển n-1 đĩa từ cọc A sang cọc trung gian B.
•
Lần 2: chuyển n-1 đĩa từ cọc B sang cọc đích C.
B. Bài toán tháp Hà Nội (tt)
I. TỔNG QUAN VỀ ĐỆ QUY
2. Một số bài toán điển hình
www.ptit.edu.vn
NHÓM THỰC HIỆN: NHÓM 2
Chương trình minh họa bài toán Tháp Hà Nội:
void chuyen(int sodia, char CotNguon, char CotDich, char CotTG)
{
if (sodia>0) {
chuyen(sodia-1, CotNguon, CotTG, CotDich);
printf(“%c ->%c\n”, CotNguon , CotDich); // Dia lon nhat

hien tai
chuyen(sodia-1, CotTG, CotDich, CotNguon);
}
}
I. TỔNG QUAN VỀ ĐỆ QUY
2. Một số bài toán điển hình
B. Bài toán tháp Hà Nội (tt):
www.ptit.edu.vn
NHÓM THỰC HIỆN: NHÓM 2

Phát biểu bài toán: Tìm cách đặt 8 quân hậu trên 1 bàn cờ
mà không có 2 quân hậu nào có thể ăn được nhau.
i
j
Ω
C. Bài toán 8 quân hậu
I. TỔNG QUAN VỀ ĐỆ QUY
2. Một số bài toán điển hình
www.ptit.edu.vn
NHÓM THỰC HIỆN: NHÓM 2

Bài toán 8 quân hậu (mô phỏng)
Ω1
Ω2
Ω3
Ω4
Ω5
Ω6
Ω7
Ω8

1 2 3 4 5 6 7 8
8
7
6
5
4
3
2
1
C. Bài toán 8 quân hậu (tt):
I. TỔNG QUAN VỀ ĐỆ QUY
2. Một số bài toán điển hình
www.ptit.edu.vn
NHÓM THỰC HIỆN: NHÓM 2

Bài toán 8 quân hậu (mô phỏng)
Ω1
Ω2
Ω3
Ω4
Ω5
Ω8
1 2 3 4 5 6 7 8
8
7
6
5
4
3
2

1
Ω1
Ω2
Ω3
Ω4
Ω5
Ω6
Ω7
C. Bài toán 8 quân hậu (tt):
I. TỔNG QUAN VỀ ĐỆ QUY
2. Một số bài toán điển hình
Ω5
Ω4