Bài giảng Công nghệ phần mềm - Chương 1: Cấu trúc dữ liệu và giải thuật - Ngô Công Thắng

CHƯƠNG 1
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT
GV. Ngô Công Thắng
Bộ môn Công nghệ phần mềm Khoa 
Công nghệ thông tin
Website: dse.vnua.edu.vn/ncthang
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.2
1. Mối quan hệ giữa cấu trúc dữ liệu và 
giải thuật
1.1. Giải thuật (thuật toán, algorithms)
l Khái niệm: Giải thuật là một hệ thống các 
thao tác, các phép toán được thực hiện 
theo trình tự nhất định trên một số đối 
tượng dữ liệu nào đó, sao cho sau một số 
bước hữu hạn ta có được kết quả mong 
muốn.
l Giải thuật phản ánh các phép xử lý, còn 
đối tượng xử lý là dữ liệu.
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.3
1.1. Giải thuật (thuật toán, algorithms)
l Giải thuật phải có các tính chất cơ bản sau:
l Tính thực hiện được:
l Tính kết thúc:
l Tính kết quả: Phải cho kết quả mong muốn.
l Tính hiệu quả:
l Tính duy nhất:
l Tính tổng quát: Phải áp dụng cho mọi bài toán cùng 
loại.
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.4
1.2. Cấu trúc dữ liệu 
l Khái niệm dữ liệu: Dữ liệu là các phần tử biểu 
diễn các thông tin cần thiết cho bài toán.
l Một bài toán có thể có các loại dữ liệu: Dữ liệu 
vào, dữ liệu trung gian, dữ liệu ra.
l Dữ liệu vào là dữ liệu cần đưa vào để xử lý, đây 
chính là đầu vào của bài toán.
l Dữ liệu trung gian là dữ liệu chứa các kết quả trung 
gian trong quá trình xử lý.
l Dữ liệu ra là dữ liệu chứa kết quả mong muốn của 
bài toán.
l Giải thuật thực hiện biến đổi từ các dữ liệu vào 
thành các dữ liệu ra.
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.5
1.2. Cấu trúc dữ liệu (tiếp)
l Ví dụ 1: Ta xét bài toán tính học bổng cho 
sinh viên theo chế độ hiện hành. Các dữ 
liệu của bài toán bao gồm:
l Dữ liệu vào: Họ và tên, Điểm các môn, Số 
trình các môn học.
l Dữ liệu trung gian: Điểm trung bình
l Dữ liệu ra: Học bổng
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.6
1.2. Cấu trúc dữ liệu (tiếp)
l Ví dụ 2: Xét bài toán giải phương trình bậc 
hai ax2 + bx + c = 0 . Các dữ liệu của bài 
toán này như sau:
l Dữ liệu vào: a, b, c
l Dữ liệu trung gian: delta 
l Dữ liệu ra: x1, x2
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.7
1.2. Cấu trúc dữ liệu (tiếp)
l Dữ liệu nguyên tử là phần tử dữ liệu cơ sở 
không thể tách nhỏ ra được, có thể là một chữ 
số, một kí tự, một giá trị logic,... Trong một bài 
toán, dữ liệu bao gồm một tập các dữ liệu 
nguyên tử.
l Từ các dữ liệu nguyên tử ta có thể tạo thành các 
cấu trúc dữ liệu bằng các cách thức liên kết 
khác. Chẳng hạn liên kết các kí tự lại với nhau 
tạo thành cấu trúc dữ liệu kiểu xâu kí tự, liên kết 
các số lại với nhau theo kiểu một dãy số ta được 
cấu trúc dữ liệu kiểu mảng một chiều.
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.8
1.2. Cấu trúc dữ liệu (tiếp)
l Tóm lại, Cấu trúc dữ liệu là cách tổ chức 
các phần tử dữ liệu của bài toán.
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.9
1.2. Cấu trúc dữ liệu (tiếp)
l Khái niệm về Cấu trúc lưu trữ: Cách biểu diễn 
một cấu trúc dữ liệu trong bộ nhớ được gọi là 
cấu trúc lưu trữ, đó chính là cách cài đặt cấu 
trúc dữ liệu trên máy vi tính.
l Có thể có nhiều cấu trúc lưu trữ khác nhau cho một 
cấu trúc dữ liệu. Chẳng hạn một cấu trúc dữ liệu kiểu 
mảng ta có thể lưu trữ bằng các ô nhớ kế tiếp nhau 
trong bộ nhớ hoặc có thể lưu trữ bằng các ô nhớ 
không kế tiếp nhau trong bộ nhớ.
l Có thể có nhiều cấu trúc dữ liệu khác nhau được cài 
đặt trong bộ nhớ bằng một cấu trúc lưu trữ. Chẳng 
hạn cấu trúc xâu kí tự, cấu trúc mảng đều có thể cài 
đặt trong bộ bằng các ô kế tiếp nhau.
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.10
1.2. Cấu trúc dữ liệu (tiếp)
l Mỗi một ngôn ngữ lập trình đều có các 
cấu trúc dữ liệu tiền định (định sẵn), bởi 
vậy khi chọn ngôn ngữ lập trình nào thì ta 
phải chấp nhận cấu trúc dữ liệu tiền định 
của nó, phải vận dụng linh hoạt các cấu 
trúc dữ liệu này vào bài toán cần giải 
quyết.
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.11
1.3. Mối quan hệ giữa cấu trúc dữ liệu
và giải thuật
l Xét tới giải thuật thì phải xét giải thuật đó tác 
động trên cấu trúc dữ liệu nào.
l Xét tới cấu trúc dữ liệu thì phải hiểu cấu trúc dữ 
liệu đó cần được tác động bằng giải thuật gì để 
được kết quả mong muốn.
l Cấu trúc dữ liệu nào thì giải thuật đó. Khi cấu 
trúc dữ liệu thay đổi giải thuật cũng thay đổi 
theo.
l Mối quan hệ giữa cấu trúc dữ liệu và giải thuật 
được Niklaus Wirth tổng kết như sau:
Cấu trúc dữ liệu + Giải thuật = Chương trình
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.12
2. Các cách diễn đạt giải thuật
2.1. Liệt kê các bước bằng lời
l Trong cách diễn đạt này ta phải viết từng bước 
làm công việc gì: Bước 1, Bước 2.
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.13
2. Các cách diễn đạt giải thuật
2.2. Lưu đồ giải thuật
l Lưu đồ giải thuật là một sơ đồ có hướng diễn 
đạt các bước thực hiện của giải thuật.
l Lưu đồ giải thuật giúp người lập trình xem xét 
sự làm việc của giải thuật khá chi tiết và cụ thể.
l Lưu đồ giải thuật bao gồm các hình cơ bản nối 
với nhau bởi các đường có hướng.
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.14
2.1. Lưu đồ giải thuật (tiếp)
l Các hình cơ bản trong lưu đồ giải thuật 
gồm có:
l Hình elíp thể hiện sự bắt đầu và kết thúc của 
giải thuật.
l Hình chữ nhật chỉ các thao tác, công việc cần 
thực hiện.
Công việc
Bắt đầu Kết thúc
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.15
2.1. Lưu đồ giải thuật (tiếp)
l Các hình cơ bản trong lưu đồ giải thuật 
gồm có:
l Hình thoi thể hiện các điệu kiện. Hình này có 
một đường vào và hai đường ra ứng với hai 
trường hợp điều kiện đúng hoặc điều kiện sai.
Điều kiện
Đúng
Sai
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 0 ... thể 
tính theo đơn vị giây, phút
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.20
3.2.3. Độ phức tạp tính toán của giải thuật
l Cách đánh giá thời gian thực hiện giải thuật không phụ 
thuộc vào máy tính và các yếu tố liên quan mà chỉ phụ thuộc 
vào kích thước dữ liệu đầu vào được gọi là đánh giá theo 
“Độ phức tạp tính toán của giải thuật”.
l Nếu thời gian thực hiện một giải thuật là T(n) = Cn2, trong đó 
C là hằng số, thì ta nói độ phức tạp tính toán của giải thuật 
này có cấp n2, và được kí hiệu là: T(n)= O(n2)
l Tổng quát: Hàm f(n) có độ phức tạp tính toán cấp g(n), kí 
hiệu là f(n) = O(g(n)), nếu tồn tại các hằng số C và n0 sao 
cho:
f(n) ≤ Cg(n) với n ³ n0
nghĩa là hàm f(n) bị chặn trên bởi Cg(n), với C là hằng số và 
với mọi n từ một điểm nào đó. 
l Ví dụ 1: f(n) = O(n3) có nghĩa độ phức tạp tính toán cấp n3
l Ví dụ 2: f(n) = O(2n) có nghĩa độ phức tạp tính toán cấp 2n
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.21
3.2.3. Độ phức tạp tính toán của 
giải thuật (tiếp) 
l Các hàm thể hiện độ phức tập tính toán của giải thuật 
có các dạng sau: nn, n!, 2n, n3, n2, nlog2n, n, log2n. Các 
hàm này đã được sắp theo giá trị giảm dần, có nghĩa là 
với cùng một giá trị của n, hàm nn là lớn nhất, log2n là 
nhỏ nhất. Các hàm này có dạng đồ thị như sau:
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.22
3.2.3. Độ phức tạp tính toán của 
giải thuật (tiếp)
l Các hàm nn , n! , 2n gọi là các hàm mũ. 
Một gíải thuật có độ phức tạp tính toán 
cấp hàm mũ thì rất chậm, do đó khó được 
chấp nhận.
l Các hàm n3, n2, nlog2n, n, log2n là các 
hàm loại đa thức. Độ phức tạp tính toán 
của giải thuật có cấp đa thức thì chấp 
nhận được.
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.23
3.2.4. Xác định độ phức tạp tính toán
l Quy tắc cộng:
l Giả sử T1(n) và T2(n) là thời gian thực hiện 2 
đoạn chương trình P1 và P2 mà T1(n)= 
O(f(n)), T2(n)=O(g(n)), thì thời gian thực hiện 
P1 rồi đến P2 tiếp theo sẽ là: T1(n) + T2(n) = 
O(max(f(n),g(n)))
l Ví dụ: Chương trình có 3 bước, mỗi bước có 
độ phức tạp tính toán lần lượt là O(n3), O(n), 
O(nlog2n). Vậy thời gian thực hiện 3 bước là:
T1(n) + T2(n) + T3(n) = O(max(n3, n, nlog2n) 
= O(n3)
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.24
3.2.4. Xác định độ phức tạp tính toán 
(tiếp)
l Quy tắc nhân:
l Nếu tương ứng với 2 bước P1 và P2 là T1(n) = 
O(f(n)),T2(n) = O(g(n)) thì thời gian thực hiện P1 và 
P2 lồng nhau là : T1(n).T2(n) = O(f(n).g(n))
l Ví dụ: Câu lệnh x:=x+1 có thời gian thực hiện bằng 
hằng số C => T(n) =O(1)
Câu lệnh: For i :=1 To n Do x :=x+1;
có thời gian thực hiện là: T(n)=O(n.1)=O(n)
Câu lệnh
For i :=1 To n Do 
For j :=1 To n Do x:=x+1;
có thời gian thực hiện được đánh giá là: T(n)= O(n.n) 
= O(n2)
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.25
3.2.4. Xác định độ phức tạp tính toán 
(tiếp)
l Quy tắc bỏ hằng số
l O(c.f(n)) = O(f(n), trong đó c là một hằng số.
l Ví dụ: O(n2/3) = O(n2)
l Chú ý 1: Khi đánh giá thời gian thực hiện 
giải thuật ta chỉ cần chú ý tới các bước 
tương ứng với một phép toán được gọi là 
phép toán tích cực. Đó là phép toán mà 
thời gian thực hiện nó không ít hơn thời 
gian thực hiện các phép toán khác.
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.26
3.2.4. Xác định độ phức tạp tính toán 
(tiếp)
l Ví dụ: ex = 1+ x/1! + x2/2! + . . .+ xn/n! với x và n 
cho trước.
l Giải thuật 1:
1) Read(x,n); s:=1;
2) For i :=1 To n Do begin
p:=1;
For j :=1 To i Do p:=p*x/j ;
s:=s+p;
end;
end.
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.27
3.2.4. Xác định độ phức tạp tính toán 
(tiếp)
l Trong giải thuật 1 phép toán tích cực ở 
đây là p:=p*x/j. Ta thấy nó được thực hiện 
với số lần là: 1+2+3+ . . . + n = n(n+1)/2
Vậy thời gian thực hiện giải thuật là: T(n) = 
O(n2)
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.28
3.2.4. Xác định độ phức tạp tính toán 
(tiếp)
l Giải thuật 2:
1) Read(x,n); s:=1; p:=1;
2) For i :=1 To n Do begin
p:=p*x/i;
s:=s+p;
end;
end.
Thời gian thực hiện giải thuật 2 là: T(n) = O(n)
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.29
3.2.4. Xác định độ phức tạp tính toán 
(tiếp)
l Chú ý 2: Có những trường hợp thời gian thực hiện giải 
thuật không chỉ phụ thuộc vào kích thước của dữ liệu 
vào mà còn phụ thuộc vào chính tình trạng của dữ liệu 
đó nữa.
l Khi phân tích thời gian thực hiện giải thuật ta phải xét 
xem với mọi dữ liệu vào có kích thước n thì T(n) trong 
trường hợp thuận lợi nhất, trường hợp trung bình và 
trường hợp xấu nhất như thế nào?
l Việc xác định T(n) trong trường hợp trung bình thường 
khó vì phải dùng tới những công cụ toán đặc biệt. Bởi 
vậy người ta thường đánh giá giải thuật bằng T(n) trong 
trường hợp xấu nhất.
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.30
3.2.4. Xác định độ phức tạp tính toán 
(tiếp)
l Ví dụ: Cho véc tơ a có n phần tử a1, a2,..., an. Tìm trong a phần tử 
đầu tiên có giá trị = x cho trước.
l Giải thuật như sau:
Found := False;
i:=1;
While (i<=n) and Not Found Do
If a[i] =x then begin
Found:=True;
k:=i;
Write(k);
end
else i:=i+1;
End.
T(n) trong trường hợp tốt T(n)=O(1)
T(n) trong trường hợp xấu T(n)=O(n) . Vây suy ra T(n)=O(n)
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 02 2.31
4. Giải thuật đệ quy
4.1. Khái niệm đệ quy
l Ta nói một đối tượng là đệ quy nếu nó được định nghĩa
dưới dạng chính nó.
l Ví dụ 1: Trên màn hình của vô tuyến truyền hình lại xuất
hiện hình ảnh của chính cái màn hình vô tuyến đó.
l Ví dụ 2: Trong toán học hay gặp định nghĩa đệ quy:
1. Định nghĩa số tự nhiên
a) x là số tự nhiên nếu x-1 là số tự nhiên
b) 1 là số tự nhiên
2. Hàm n!
a) n! = n*(n-1)! nếu n>0
b) n!=1 nếu n=0
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 02 2.32
4.2. Giải thuật đệ quy và thủ tục đệ quy
l Nếu lời giải của một bài toán T được thực hiện 
bằng lời giải của bài toán T’ có dạng giống như 
T thì đó là một lời giải đệ quy. Trong đó T’ tuy 
giống T nhưng nó phải nhỏ hơn T.
l Giải thuật tương ứng với lời giải đệ quy gọi là 
giải thuật đệ quy.
l Thủ tục viết cho bài toán có lời giải đệ quy gọi là 
thủ tục đệ quy.
Trong thủ tục đệ quy có lời gọi tới chính nó, mỗi 
lần gọi thì kích thước bài toán thu nhỏ hơn và 
dần dần tiến tới trường hợp đặc biệt là trường 
hợp suy biến.
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 02 2.33
Ví dụ: Bài toán tìm 1 từ trong cuốn 
từ điển
l Giải thuật đệ quy của bài toán này như sau:
IF từ điển là một trang THEN tìm từ trong 
trang ấy
ELSE BEGIN
Mở từ điển vào trang giữa; Xác định xem 
nửa nào chứa từ
IF từ nằm trong nửa trước THEN tìm trong 
nửa trước
ELSE tìm trong nửa sau
END
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 02 2.34
Ví dụ: Bài toán tìm 1 từ trong cuốn 
từ điển
l Trong giải thuật này có 2 điểm cần chú ý:
l Điểm 1: Sau mỗi lần từ điển được tách đôi, một nửa 
thích hợp sẽ được tìm kiếm theo chiến thuật đã dùng.
l Điểm 2: Có trường hợp đặc biệt là sau khi tách đôi từ 
điển chỉ còn 1 trang, giải quyết trực tiếp bằng cách 
tìm từ trong trang đó. Trường hợp đặc biệt này gọi là 
trường hợp suy biến.
l Giải thuật này gọi là giải thuật chia đôi: Bài toán 
được tách đôi ra bài toán nhỏ hơn, bài toán nhỏ 
hơn lại dùng chiến thuật chia đôi, cho tới khi gặp 
trường hợp suy biến.
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 02 2.35
Ví dụ: Bài toán tìm 1 từ trong cuốn 
từ điển
l Thủ tục đệ quy của bài toán được viết như sau:
Procedure timkiem(Tudien, tu)
IF Tudien chỉ còn một trang THEN tìm từ trong trang ấy
ELSE BEGIN
Mở từ điểm vào trang giữa
Xác định xem nửa nào chứa từ
IF Từ nằm ở nửa trước
THEN CALL timkiem(Tudien1, tu)
ELSE CALL timkiem(Tudien2, tu)
END
RETURN
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 02 2.36
4.3. Thiết kế giải thuật đệ quy
l Khi bài toán đang xét hoặc dữ liệu đang xử lý
được định nghĩa dưới dạng đệ quy thì việc thiết
kế các giải thuật đệ quy tỏ ra rất thuận lợi.
l Khi thiết kế giải thuật đệ quy cần trả lời các câu
hỏi sau:
1. Có thể định nghĩa bài toán dưới dạng một bài toán
cùng loại nhưng nhỏ hơn như thế nào?
2. Như thế nào là kích thước của bài toán được giảm đi
ở mỗi lần gọi đệ quy?
3. Trường hợp đặc biệt nào của bài toán sẽ được gọi là
trường hợp suy biến?
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 02 2.37
Bài toán 1: Tính n! 
l Định nghĩ đệ quy của hàm n! như sau:
FAC(n) = 1 nếu n=0
FAC(n)=n´FAC(n-1) nếu n>0
Thuật giải đệ quy được viết dưới dạng hàm:
Function FAC(n)
If n=0 then begin FAC :=1; return; end;
Else FAC := n * FAC(n-1);
Return
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 02 2.38
Bài toán 1: Tính n! 
l Khử đệ quy của hàm tính giai thừa:
Function FAC(n)
If n=0 then gt:=1; 
Else begin
gt:=1;
For i:=1 to n do gt:=gt*I;
end;
FAC:=gt;
Return
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 02 2.39
Bài toán 1: Tính n! 
l Đối chiếu với 3 đặc điểm của thủ tục đệ 
quy ta thấy:
l Lời gọi tới chính nó đứng sau Else
l Mỗi lần gọi đệ quy giá trị giảm đi: 
FAC(4)®FAC(3)®FAC(2)® FAC(1)
l Trường hợp suy biến là FAC(0): FAC(0) = 1
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 02 2.40
Bài toán 2: Lập dãy số FIBONACCI 
1 1 2 3 5 8 13...
l Định nghĩa F(n) như sau:
F(n) = 1 nếu n £ 2
F(n)=F(n-2)+F(n-1) nếu n>2
l Thủ tục đệ quy thể hiện giải thuật tính F(n) như 
sau:
Function F(n:integer)
If n<=2 then F:=1
Else F:=F(n-2)+F(n-1)
Return
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 02 2.41
Bài toán 3: Bài toán “Tháp Hà nội” 
l Nội dung: Có n đĩa kích thước nhỏ dần, đĩa có lỗ 
ở giữa. Có thể xếp chồng chúng lên nhau xuyên 
qua một cái cọc, to dưới nhỏ trên để cuối cùng 
có một chồng đĩa dạng như hình tháp.
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 02 2.42
Bài toán 3: Bài toán “Tháp Hà nội” 
l Yêu cầu đặt ra: Chuyển chồng đĩa từ cọc 
A sang cọc C theo những điều kiện sau:
l Mỗi lần chỉ được chuyển một đĩa
l Không khi nào có tình huống đĩa to ở trên đĩa 
nhỏ ở dưới
l Được phép sử dụng 1 cọc trung gian (cọc B) 
để đặt tạm thời.
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 02 2.43
Bài toán 3: Bài toán “Tháp Hà nội” 
l Ta xét một vài trường hợp đơn giản:
l Trường hợp 1 đĩa: 
lChuyển từ cọc A sang cọc C
l Trường hợp 2 đĩa:
lChuyển đĩa thứ nhất từ cọc A sang cọc B
lChuyển đĩa thứ hai từ cọc A sang cọc C
lChuyển đĩa thứ nhất từ cọc B sang cọc C
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 02 2.44
Bài toán 3: Bài toán “Tháp Hà nội” 
l Trường hợp n đĩa (n>2): Ta coi n-1 đĩa ở trên như 
đĩa thứ nhất và xử lý giống như trường hợp 2 đĩa:
l Chuyển n-1 đĩa từ cọc A sang cọc B
l Chuyển đĩa thứ n từ cọc A sang cọc C
l Chuyển n-1 đĩa từ cọc B sang cọc C
l Chuyển n-1 đĩa từ cọc B sang cọc C thuật giải sẽ 
là:
l Chuyển n-2 đĩa từ cọc B sang cọc A
l Chuyển 1 đĩa từ cọc B sang cọc C
l Chuyển n-2 đĩa từ cọc B sang cọc C
l Cứ làm như vậy cho đến khi trường hợp suy biến 
xảy ra, đó là trường hợp ứng với bài toán chuyển 1 
đĩa.
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 02 2.45
Bài toán 3: Bài toán “Tháp Hà nội” 
l Thủ tục của bài toán “Tháp Hà nội” như sau:
Procedure Hanoi(n,A,B,C)
If n=1 then chuyển đĩa từ A sang C
Else Begin
Call Hanoi(n-1,A,C,B)
Call Hanoi(1,A,B,C)
Call Hanoi(n-1,B,A,C)
End;
Return
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 02 2.46
Bài tập
1. Thế nào là giải thuật đệ quy?
2. Ưu nhược điểm của giải thuật đệ quy? 
3. Trong bộ nhớ của máy tính dùng vùng nhớ nào để dùng
cho giải thuật đệ quy.
4. Trường hợp suy biến là trường hợp như thế nào trong
giải thuật đệ quy.
5. Thường hay dùng cấu trúc lập trình nào để thể hiện giải
thuật đệ quy
6. Viết giải thuật đệ quy cho bài toán sau:
Acker(m,n)= n+1 nếu m=0
Acker(m,n)= Acker(m-1,1) nếu n=0
Acker(m,n)= Acker(m-1,Acker(m,n-1)) với các trường
hợp khác.
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 02 2.47
Thủ tục đệ quy Bài 6
Function Acker(m,n:integer)
If m=0 then Acker:=n+1
else if n=0 then Acker:=Acker(m-1,1)
else Acker:=Acker(m-1,Acker(m,n-1))
Return
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 02 2.48
Bài tập (tiếp)
7. Giải thuật tính ước số chung lớn nhất của 
hai số nguyên dương a và b (a>b) như 
sau: Gọi r là số dư của phép chia a cho b.
- Nếu r=0 thì b là ước số chung lớn nhất
- r khác 0 thì gán a:=b; b:=r rồi lặp lại. 
Hãy xây dựng giải thuật đệ quy tính ước 
số chung lớn nhất USCLN(a,b)
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 02 2.49
Thủ tục đệ quy bài 7
Bài toán: Tìm USCLN của 2 số nguyên dương a,b
Cách 1: Dùng đệ quy
Function USCLN(a,b)
If b=0 then begin USCLN := a; return; end;
If b # 0 then USCLN := USCLN(b,a mod b);
Return
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 02 2.50
Thủ tục đệ quy bài 7
Bài toán: Tìm USCLN của 2 số nguyên dương a,b
Cách 2: Khử đệ quy
Function USCLN(a,b)
1) r := a mod b;
2) while r # 0 do begin
a:=b; b:=r; r:= a mod b
end;
3) USCLN:=b;
Return
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 02 2.51
Bài tập (tiếp)
8. Hàm C(n,k) với n, k là các giá trị nguyên không 
âm và k<=n, được định nghĩa như sau:
C(n,n)=1
C(n,0)=1
C(n,k)=C(n-1,k-1)+C(n-1,k) nếu 0< k<n
Hãy xây dựng giải thuật đệ quy cho bài toán trên
9. Viết thủ tục đệ quy in ngược một dòng kí tự cho 
trước.
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 02 2.52
Thủ tục đệ quy bài 8
Function C(n,k:integer)
If k=0 then C:=1
else if k=n then C:=1
else C:=C(n-1,k-1)+C(n-1,k);
Return