1
GIớI THIệU MÔN HọC
Trong ngôn ngữ lậ p trì nh, dữ liệ u bao gồm hai kiể u chí nh là :
- Kiể u dữ liệ u đơn giả n: char, int, long, float, enumeration, subrange.
- Kiể u dữ liệ u có cấ u trúc : struct, array, file (kiể u dữ liệ u có kí ch thước
không đổi)...
Giá o trì nh nà y tậ p trung và o việ c nghiê n cứu cá c kiể u dữ liệ u có cấ u trúc
có kí ch thước không đổi hoặ c thay đổi trong ngôn ngữ lậ p trì nh, mô tả thông qua
ngôn ngữ C. Ngoà i ra còn giới thiệ u cá c giả i thuậ t chung quanh cá c cấ u trúc dữ
liệ u nà y như cá ch tổ chức, thực hiệ n cá c phé p toán tì m kiế m, sắ p thứ tự nội, sắp
thứ tự ngoạ i...
Điề u kiệ n để có thể tì m hiể u rõ rà ng về môn học nà y là học viê n đ biế t
cá c khá i niệ m về kỹ thuậ t lậ p trì nh trê n ngôn ngữ C. Trong phầ n mở đầ u, bà i
giả ng nà y sẽ giới thiệ u cá ch thức phâ n tí ch & thiế t kế một giả i thuậ t trước khi
tì m hiể u về cá c cấ u trúc dữ liệ u cụ thể .
Và o cuối khóa học, sinh viê n có thể :
- Phâ n tí ch độ phức tạ p của cá c chương trì nh có kí ch thước nhỏ và trung
bì nh.
- Nhậ n thức đ ược sự cầ n thiế t của việ c thiế t kế cấ u trúc dữ liệ u.
- Là m quen với cá c khá i niệ m stacks, queues, danh sá ch đặ c, danh sá ch
liê n kế t, câ y nhị phâ n, câ y nhị phâ n tì m kiế m, ....
- Hiể u đ ược nguyê n lý của việ c xâ y dựng một chương trì nh má y tí nh.
- Có thể chọn lựa việ c tổ chức dữ liệ u phù hợp và cá c giả i thuậ t xử lý dữ
liệ u có hiệ u quả trong khi xâ y dựng chương trì nh. Sinh viê n cầ n lưu ý rằ ng, tùy
và o công việ c cụ thể mà ta nê n chọn cấ u trúc dữ liệ u nà o là thí ch hợp theo hướng
tối ưu về thời gian thực hiệ n hay tối ưu về bộ nhớ.
2
Chươn g I
PHÂN Tí CH & THIếT Kế
GIảI THUậT
I. mở đầu


(n) :
Ta đá nh giá tỷ lệ phá t triể n cá c hà m T(n) qua ký hiệ u O(n).
Ta nói thời gian chạ y T(n) của chương trì nh là O(n
2
) có nghĩ a là :
c > 0 và n
0
sao cho n n
0
ta có T(n) c.n
2
.
Ví dụ
: Giả sử T(0) = 1, T(1) = 4, v v...
Tổng quá t T(n) = (n +1)
2
thì ta nói T(n) là O(n
2
) vì có thể đặ t c
1
= 4, n
0
= 1,
thì khi n 1 ta có (n +1)
2
4n
2
.
Nhưng không thể lấ y n

= 0).
* Sự trá i ngược của tỷ lệ phá t triể n
:
Ta giả sử cá c chương trì nh có thể đá nh giá bằ ng cá ch so sá nh cá c hà m thời
gian của chúng với cá c hằ ng tỷ lệ không đá ng kể . Khi đó ta nói chương trì nh có
thời gian chạ y O(n
2
). Nế u chương trì nh 1 chạ y mấ t 100.n
2
thời gian (mili giâ y)
thì chương trì nh 2 chạ y mấ t 5.n
3
thời gian, thì ta có tỷ số thời gian của 2 chương
trì nh là 5.n
3
/100.n
2
= n/20, nghĩ a là khi n = 20 thì thời gian chạ y 2 chương trì nh
là bằ ng nhau, khi n < 20 thì chương trì nh 2 chạ y nhanh hơn chương trì nh 1. Do
đó khi n > 20 thì nê n dùng chương trì nh 1.
Ví dụ
: Có 4 chương trì nh có 4 độ phức tạ p khá c nhau đ ược biể u diễ n trong
bả ng dưới đây.
Thời gian
chạ y T(n)
Kí ch thước bà i toá n
tối đa cho 10
3
s
Kí ch thước bà i toá n

1
(n) và T
2
(n) là thời gian chạ y chương trì nh P
1
và P
2
tương ứng đ ược
đá nh giá là O(f(n)) và O(g(n)). Khi đó T
1
(n) + T
2
(n) sẽ là O(max(f(n),g(n)))
(chạ y xong chương trì nh P
1
thì chạ y P
2
).
Chứng minh
:
Theo đị nh nghĩ a O(f(n)) và O(g(n)) thì c
1
, n
1
, c
2
, n
2
sao cho
T

2. Qui tắc tí ch:

T
1
(n). T
2
(n) là O(f(n).g(n)).
Chứng minh
: tương tự như tổng.
Ví dụ
: Có 3 chương trì nh có thời gian chạ y tương ứng là O(n
2
), O(n
3
),
O(n.logn). Thế thì thời gian chạ y 3 chương trì nh đồng thời là O(max(n
2
, n
3
,
nlogn)) sẽ là O(n
3
).
Nói chung thời gian chạ y một d y cố đị nh cá c bước là thời gian chạ y lớn
nhấ t của một bước nào đó trong d y. Cũng có trường hợp có 2 hay nhiề u bước có
thời gian chạ y không tương xứng (không lớn hơn mà cũng không nhỏ hơn). Khi
đó qui tắ c tí nh tổng phả i đ ược tí nh trong từng trường hợp.
n
4
nế u n chẵ n

+ n) = O(n
2
)
Trước khi đ ưa ra qui tắ c chung để phâ n tí ch thời gian chạ y của chương trì nh
thì ta xé t ví dụ đơn giả n sau.
5
Ví dụ : Xé t chương trì nh Bubble dùng sắ p d y số nguyê n theo chiề u tă ng.
Procedure Bubble (var A: array [1..n] of integer);
Var i, j, temp : integer ;
Begin
1 For i := 2 to n do
2 For j := n downto i do
3 If A[j-1] > A[j] then
Begin
4 temp := A[j-1] ;
5 A[j-1] := A[j] ;
6 A[j] := temp ;
End ;
End ;
Phâ n tí ch
:
- N là số phầ n tử - kí ch thước của bà i toá n. Mỗi lệ nh gá n từ dòng 4 - > dòng
6 mấ t 3 đơn vị thời gian, theo qui tắ c tí nh tổng sẽ là O(max(1,1,1) = O(1).
- Vòng If và For lồng nhau, ta phả i xé t từ trong ra ngoà i. Đối với điề u kiệ n
sau If phả i kiể m tra O(1) thời gian. Ta không chắ c thâ n lệ nh If từ 4 - 6 có thực
hiệ n hay không. Vì xé t trong trường hợp xấ u nhấ t nê n ta giả thuyế t là cá c lệ nh từ
4 - 6 đề u có thực hiệ n. Vậ y nhóm If từ cá c lệ nh 3 -6 là m mấ t O(1) thời gian.
- Ta xé t vòng lặ p ngoà i từ 2 - 6. Nguyê n tắ c chung của vòng lặ p: thời gian
vòng lặ p là tổng thời gian mỗi lầ n lặ p trong thâ n vòng lậ p. í t nhấ t là O(1) cho
mỗi lầ n lặ p khi chỉ số tă ng. Số lầ n lặ p từ 2 - 6 là n - i +1

là đệ qui thì ta có thể tí nh thời gian chạ y cùng một lúc, bắ t đầ u từ cá c thủ tục
không gọi đế n cá c thủ tục khá c. Tấ t nhiê n phả i có í t nhấ t 1 thủ tục như vậ y trong
trường hợp nà y, nế u không thì phả i có thủ tục đệ qui. Sau đó ta có thể đá nh giá
thời gian chạ y của cá c thủ tục có gọi, đế n cá c thủ tục không chứa lời gọi đ đ ược
đá nh giá . Cứ như thế ta lạ i đá nh giá thời gian chạ y của cá c thủ tục có lời gọi đế n
cá c thủ tục đ đá nh giá , nghĩ a là mỗi thủ tục đ ược đá nh giá sau khi đá nh giá hế t
cá c thủ tục mà đ ược nó gọi.
Nế u có thủ tục đệ qui thì không thể tì m đ ược thứ tự của tấ t cả cá c thủ tục
sao cho mỗi thủ tục chỉ gọi đế n cá c thủ tục đ đá nh giá . Khi đó ta phả i lậ p 1 liê n
hệ giữa mỗi thủ tục đệ qui với 1 hà m thời gian chưa biế t T(n) trong đó n là kí ch
thước của đối số của thủ tục. Lúc đó ta có thể nhậ n đ ược sự truy hồi đối với T(n),
nghĩ a là 1 phương trì nh diễ n tả T(n) qua cá c T(k) với cá c giá trị k khá c nhau.
Ví dụ
: Xé t chương trì nh đệ qui tí nh n giai thừa (n!), trong đó n là kí ch
thước của hà m nê u trê n.
Function Fact (n:integer) : LongInt ;
Begin
1 If n <= 1 then
2 Fact := 1
Else
3 Fact := n*fact (n-1)
End ;
Phâ n tí ch
:
Ta ký hiệ u T(n) là thời gian chạ y để tí nh hà m Fact(n).
Thời gian chạ y đối với cá c dòng 1, 2 là O(1) và đối với dòng 3 là O(1) +
T(n-1). Vậ y với cá c hằ ng c, d nà o đó ta có phương trì nh:
7
c + T(n-1) nế u n > 1
T(n) =

số là 10; là 10 nế u cơ số là 2 ; khi N là 1000000, logN đ ược nhân gấp đôi. Bất cứ
khi nà o N được nhâ n gấ p đôi, logN đ ược tă ng lê n thê m một hằ ng số, nhưng logN
không đ ược nhâ n gấ p đôi tới khi N tă ng tới N
2
.
3. N
Khi thời gian chạ y của chương trì nh là tuyế n tí nh, nói chung đâ y là
trường hợp mà một số lượng nhỏ cá c xử lý đ ược là m cho mỗi phầ n tử dữ liệ u nhậ p
.

{

8
Khi N là 1.000.000 thì thời gian chạ y cũng cỡ như vậ y.
Khi N đ ược nhâ n gấ p đôi thì thời gian chạ y cũng đ ược nhâ n gấ p đôi.
Đâ y là tì nh huống tối ưu cho 1 thuậ t toá n mà phả i xử lý N dữ liệ u nhậ p (hay sản
sinh ra N dữ liệ u xuấ t).
4. NlogN
Đâ y là thời gian chạ y tă ng dầ n lê n cho cá c thuậ t toá n mà giả i 1 bà i toá n
bằ ng cá ch tá ch nó thà nh cá c bà i toá n con nhỏ hơn, kế đế n giả i quyế t chúng 1
cá ch độc lậ p và sau đó tổ hợp cá c lời giả i. Bởi vì thiế u 1 tí nh từ tốt hơn (có lẽ là
"tuyế n tí nh logarit" ?), chúng ta nói rằ ng thời gian chạ y của thuậ t toán như thế là
"NlogN".
Khi N là 1000000, NlogN có lẽ khoả ng 6 triệ u.
Khi N đ ược nhâ n gấ p đôi, thời gian chạ y bị nhâ n lê n nhiề u hơn gấ p đôi
(nhưng không nhiề u lắ m).
5. N
2

Khi thời gian chạ y của 1 thuậ t toá n là bậc hai, trường hợp nà y chỉ có ý

2
phầ n tử dữ liệ u nhậ p mà có thời
gian chạ y là bậ c 3 theo N thì sẽ đ ược phâ n lớp như 1 thuậ t toá n N
3/2
. Một số
thuậ t toá n có 2 giai đoạ n phâ n tá ch thà nh cá c bà i toá n con và có thời gian chạ y
xấ p xỉ với Nlog
2
N.
VI. các công thức truy hồi cơ sở
:
Phầ n lớn cá c thuậ t toá n đề u dựa trê n việ c phâ n r đệ qui một bà i toá n lớn
thà nh cá c bà i toá n nhỏ hơn, rồi dùng cá c lời giả i của cá c bà i toá n nhỏ để giả i bà i
toá n ban đầ u. Thời gian chạ y của cá c thuậ t toá n như thế đ ược xá c đị nh bởi kí ch
thướ c và số lượng cá c bà i toá n con và giá phả i trả của sự phâ n r . Trong phầ n
nà y ta quan sá t cá c phương phá p cơ sở để phâ n tí ch cá c thuậ t toá n như thế và
trì nh bà y một và i công thức chuẩ n thường đ ược á p dụng trong việ c phâ n tí ch
nhiề u thuậ t toá n.
Tí nh chấ t rấ t tự nhiê n của 1 chương trì nh đệ qui là thời gian chạ y cho dữ
liệ u nhậ p có kí ch thước N sẽ phụ thuộc và o thời gian chạ y cho cá c dữ liệ u nhậ p
có kí ch thước nhỏ hơn : điề u nà y đ ược diễ n dị ch thà nh 1 công thức toá n học gọi
là quan hệ truy hồi. Cá c công thức như thế mô tả chí nh xá c tí nh nă ng của cá c
thuậ t toá n tương ứng, do đó để có đ ược thời gian chạ y chúng ta phả i giả i cá c bà i
toá n truy hồi. Bâ y giờ chúng ta chú ý và o cá c công thức chứ không phả i cá c
thuậ t toá n.
Công thức 1
:
Công thức nà y thường dùng cho cá c chương trì nh đệ qui mà có vòng lặ p
duyệ t qua dữ liệ u nhậ p để bỏ bớt 1 phầ n tử.
C

Công thức nà y dùng cho chương trì nh đệ qui mà chia dữ liệ u nhậ p thà nh 2
phầ n trong mỗi bước.
C
n
= C
n/2
+ 1, với n >= 2 và C
1
= 0
Chứng minh
:
C
n
khoả ng logn. Phương trì nh nà y vô nghĩ a trừ phi n chẵ n hay chúng ta giả
sử rằ ng n/2 là phé p chia nguyê n : bâ y giờ chúng ta giả sử rằ ng n = 2
m
để cho
công thức luôn luôn có nghĩ a. Chúng ta viế t như sau :
1
22
1
+=

CC
mm

2
2
2
+=

nhưng có thể kiể m tra mỗi phầ n tử của dữ liệ u nhậ p.
C
n
= C
n/2
+ n, với n >= 2 và C
1
= 0
Chứng minh
:
C
n
khoả ng 2n. Tương tự trê n, công thức nà y chí nh là tổng n + n/2 + n/4 + ...
(dĩ nhiê n điề u nà y chỉ chí nh xá c khi n là lũy thừa của 2).
Nế u d y là vô hạ n, thì đâ y là 1 chuỗi hì nh học đơn giả n mà đ ược ước lượng
chí nh xá c là 2n. Trong trường hợp tổng quá t lời giả i chí nh xá c phụ thuộc và o
biể u diễ n nhị phâ n của n.
Công thức 4
:
Công thức nà y dùng cho chương trì nh đệ qui mà duyệ t tuyế n tí nh xuyê n
qua dữ liệ u nhậ p, trước, trong, hay sau khi dữ liệ u nhậ p đ ược chia đôi.
C
n
= 2C
n/2
+ n, với n >= 2 và C
1
= 0
Chứng minh
:

2
2
2
++=


m
m
C

m
C
mm
mm
+=


2
2

mm
C
=+=
2
0nn
mC
m

:
Để giả i phương trì nh truy hồi có nhiề u cá ch giả i khá c nhau, ở đâ y chúng tôi
trì nh bà y cá ch giả i phương trì nh truy hồi bằ ng cá ch truy về phương trì nh đặ c
trưng. Chúng tôi dùng cá ch giả i nà y để viế t chương trì nh giả i tự động phương
trì nh truy hồi.
a) Ta xé t phương trì nh truy hồi thuầ n nhấ t tuyế n tí nh với cá c hệ số không
đổi sau đây :
a
0
t
n
+ a
1
t
n-1
+ ... + a
k
t
n-k
= 0 (VII.1)
trong đó t
i
(i=n, n-1,..., n-k) là cá c ẩ n số cầ n tì m.
Tuyế n tí nh vì cá c t
i
chỉ có bậ c nhấ t, thuầ n nhấ t vì vế phả i bằ ng không và
cá c hệ số a
0
, a
1

x
k-1
+...+ a
k
) = 0
Rõ rà ng x = 0 là nghiệ m hiể n nhiê n, nhưng ta quan tâ m nghiệ m phương
trì nh a
0
x
k
+ a
1
x
k-1
+...+ a
k
= 0 (VII.2) và đâ y chí nh là phương trì nh đặ c trưng bậ c
k của phương trì nh truy hồi (VII.1)
Giả sử r
1
, r
2
,..., r
k
là k nghiệ m của phương trì nh (VII.2) và chúng khá c nhau
(có thể phức). Dễ dà ng kiể m tra:
r
ct
n
i

1
=1
Phương trì nh đặ c trưng tương ứng của nó là :
x
2
- 3x - 4 = 0
có nghiệ m bằ ng -1 và 4. Vậ y nghiệ m tổng quá t là :

)4()1(
21
nn
n
cct
+=


Theo điề u kiệ n ban đầ u (khi n =0 và n = 1) ta có :
c
1
+ c
2
= 1 = t
0
- c
1
+ 4c
2
=1
Vậ y c
1

= 0
Phương trì nh đặ c trưng tương ứng :
x
2
- x -1 = 0
13
Nghiệ m :
2/)51(
r
1
+=
,
2/)51(
r
2
=

Nghiệ m tổng quá t : t
n
= c
1
r
1
n

+ c
2
r
2
n

=
5/)nn(
rr
21


Giả sử cá c nghiệ m phương trì nh đặ c trưng là không phâ n biệ t, P(x) là 1 đa
thức.
P(x) = a
0
x
k
+ a
1
x
k-1
+ ... + a
k

và r là nghiệ m ké p.
Với mỗi r > k, ta xé t đa thức bậ c n đ ược xá c đị nh như sau :
h(x) = x [x
n-k
P(x)] = a
0
nx
n
+ a
1
(n-1)x

n-1
+ ... + a
k
(n-k) r
n-k
= 0
Nghĩ a là t
n
= nr
n
cũng là nghiệ m của (5.13). Tổng quá t hơn, nế u nghiệ m r
trùng nhau m lầ n (r bội m) thì
t
n
= r
n
, t
n
= nr
n
, t
n
= n
2
r
n
,...., t
n
= n
m-1

n-2
- 4t
n-3
= 0
và phương trì nh đặ c trưng tương ứng là :
x
3
- 5x
2
+ 8x - 4 = 0
hay (x-1) (x-2)
2
= 0
14
Ta có cá c nghiệ m 1 (có bội 1), 2 (có bội 2). Vậ y nghiệ m tổng quá t là :
t
n
= c
1
1
n
+ c
2
2
n
+ c
3
n2
n


- n2
n-1
- 2
b) Phương trì nh truy hồi không thuầ n nhấ t:

Ta xé t phư ơng trì nh có dạ ng sau :
a
0
t
n
+ a
1
t
n-1
+ ... + a
k
t
n-k
= b
n
P(n) (VII.3)
Trong đó vế trá i như trong (VII.1), vế phả i là b
n
P(n) với b là hằ ng và P(n) là
đa thức.
Ví dụ 4
:
t
n
- 2t

n-1
= 0
Đế n đâ y ta có thể giả i phương trì nh đ trì nh bà y ở mục a.
Phương trì nh đặ c trưng của nó là :
x
2
- 5x + 6 = 0
hay (x-2) (x-3) = 0
Trực giá c cho ta thấ y rằ ng thà nh phầ n (x-2) tương ứng với vế trá i
phương trì nh ban đầ u; còn (x-3) là biể u hiệ n kế t quả của việ c biến đổi và trừ vế
phả i.
Ví dụ 5
:
t
n
- 2t
n-1
= (n+5)3
n

15
Sự biến đổi có phức tạp như sau :
-
Nhâ n 2 vế cho 9
-
Thay n bởi n+2
-
Thay n bởi n+1,sau đó nhâ n cho -6
-
Ta đ ược kế t quả :

= 0
Phương trì nh đặ c trưng.
x
2
- 8x
2
+ 21x - 18 = 0 hay (x-2) (x-3)
2
= 0
Ta lạ i thấ y (x-2) tương ứng vế trá i phương trì nh ban đầ u và (x-3)
2
là kế t quả
của sự biế n đổi.
Như vậ y chúng ta có thể nói rằ ng để giả i phương trì nh truy hồi không thuầ n
nhấ t có dạ ng (VII.3) ta chỉ cầ n giả i phương trì nh đặ c trưng sau.
(a
0
x
k
+ a
1
x
k-1
+ ... + a
k
) (x-b)
d+1
= 0 (VII.4)
Ví dụ 6
: (bà i toá n thá p Hà Nội)

1
n
+ c
2
2
n
. Từ t
0
= 0 để tì m t
1
ta viế t :
t
1
= 2t
o
+ 1 = 1
Vậ y c
1
+ c
2
= 0, n = 0
c
1
+ 2c
2
= 1, n = 1
Suy ra c
1
= -1, c
2

n-1
= n
ở đâ y b = 1, P(n) = n bậ c 1
Ta có phương trì nh đặ c trưng:
(x-2) (x-1)
2
= 0
Vậ y nghiệ m tổng quá t là :
t
n
= c
1
2
n
+ c
2
1
n
+ c
3
n1
n

Nế u t
n
> 0 với mỗi n thì ta có thể kế t luậ n T(n)= O(2n),
Bâ y giờ ta xé t phương trì nh truy hồi không thuầ n nhấ t tổng quá t hơn.
a
o
t

o
x
k
+ a
1
x
k-1
+ ... + a
k
) (x-b
1
)
d1+1
(x-b
2
)
d2+1
= 0 (VII.6)
Ví dụ 8
: Giả i phương trì nh
t
n
= 2t
n-1
+ n + 2
n
n 1
với t
o
= 0, ta có

1
n
+ c
2
n1
n
+ c
3
2
n
+ c
4
n2
n

Sử dụng dạ ng truy hồi t
n
= 2t
n-1
+ n+ 2
n
với t
o
= 0 ta có thể tí nh đ ược t
1
,
t
2
và t
3

4
= 12 n = 2
c
1
+ 3c
2
+ 8c
3
+ 24c
4
= 35 n = 3
17
Kế t quả cuối cùng là :
t
n
= -2 -n + 2
n+1
+ n2
n

Dễ dà ng nhậ n thấ y t
n
có O(n2
n
)
Ví dụ 9
:
Giả sử n là lũy thừa của 2. Tì m T(n) từ phương trì nh:
T(n) = 4T(n/2) + n, n > 1
Thay n bằ ng 2k (với k = logn), ta có T(2k) = 4T(2k-1) + 2k. Khi đó ta có

2
n
Do đó T(n) có 0(n
2
) khi n là lũy thừa của 2.
Ví dụ 10
:
T(n) = 4t(n/2) + n
2
, n > 1, lũy thừa của 2. Đặ t n = 2
k
, ta có.
T(2
k
) = 4T(2
k-1
) + 4
k

Phương trì nh đặ c trưng (x-4)2 = 0 và ta có t
k
= c
1
4
k
+ c
2
k4
k


= c
1
2
k
+ c
2
k2
k
+ c
3
k
2
2
k
.
Vậ y T(n) = c
1
n + c
2
nlogn + c
3
nlog
2
n có 0(nlog
2
n), n lũy thừa 2.
18
Ví dụ 12 :
T(n) = 3T(n/2) + cn (c là const, n = 2
k

n
Do alogb = bloga nê n T(n) = c
1
n
log3
+ c
2
n có 0(n
log3
),n lũy thừa 2.
c) Phương trì nh truy hồi có hệ số biế n đổi

Ta xé t ví dụ cụ thể :
T(1) = 6
T(n) = nT
2
(n/2), n > 1,n lũy thừa của 2
(hệ số ở vế phải là biến n)
Trước hế t ta đặ t t
k
= T(2
k
) và từ đấ y ta có :
t
k
= 2
k
t
2
K-1

+ c
3
k1
k

Từ V
o
= 1 + lg3, V
1
= 3+2lg3 và V
2
= 8 + 4lg3 ta tì m ra
c
1
= 3 + lg3, c
2
= -2 và c
3
= -1.
Vậ y V
3
= (3 + lg3) 2
k
- K -2
Cuối cùng, sử dụng tk = 2
vk
và T(n) = tlgn, ta đ ược :

n
nT

S(3)...., cứ như vậ y có S(n-1) ta sẽ tí nh đ ược S(n)
Cũng như cá c lệ nh lặ p, cá c thủ tục đệ qui cũng có thể thực hiệ n cá c tí nh
toá n không kế t thúc, vì vậ y ta phả i xé t đế n vấ n đề kế t thúc cá c tí nh toá n trong
giả i thuậ t đệ qui. Rõ rà ng 1 thủ tục P đ ược gọi đệ qui chỉ khi nà o thỏa 1 điều
kiệ n B, và dĩ nhiê n điề u kiệ n B nà y phả i không được thỏa m n tạ i 1 thời điể m
nào đó. Như vậ y mô hì nh về cá c giả i thuậ t đệ qui là :
P if (B) P(S
i
, P)
hay P P(S
i
, if (B) P).
Thông thường trong cá c vòng lặ p while, để đả m bả o cho vòng lặ p kế t thúc
ta phả i đị nh nghĩ a một hà m f(x) (x là 1 biế n trong chương trì nh) sao cho nó phả i
trả về trị bằ ng 0 tạ i một thời điể m nà o đó. Tương tự như vậ y, chương trì nh đệ qui
cũng có thể đ ược chứng minh là sẽ dừng bằ ng cá ch chứng minh rằ ng hà m f(x) sẽ
giả m sau mỗi lầ n thực hiệ n. Một cá ch thường là m là kế t hợp một giá trị n với P
và gọi P một cá ch đệ qui với giá trị tham số là n-1. Điề u kiệ n B bâ y giờ là n > 0
thì sẽ đả m bả o đ ược sự kế t thúc của giả i thuậ t đệ qui. Như vậ y, ta có mô hì nh đệ
qui mới:
P(n) if (n >0) P(S
i
, P(n-1))
Hay P P (S
i
, if (n>0) P(n-1) )
20
II. Hàm đệ qui và Stack:
Một chương trì nh C thường gồm có hà m main() và cá c hà m khá c. Khi chạ y
chương trì nh C thì hà m main() sẽ được gọi chạ y trước, sau đó hà m main() gọi cá c

{.....;
D();
}
C()
{......;
D();
.....;
}
D()
{........;
........;
}
Hì nh sau đâ y cho ta thấ y sự chiế m dụng bộ nhớ stack khi chạ y chương trì nh
C như mô tả ở trê n.
MMMMMMMMMMMMM
AAAAAAA BBB
CCC D D
D
Boọ nhụự
Stack
Thụứi gian

Tương tự với trường hợp hà m đệ qui, khi gọi đệ qui lẫ n nhau thì một loạ t
cá c khung kí ch hoạ t sẽ đ ược tạ o ra và nạ p và o bộ nhớ Stack. Cấ p đệ qui cà ng cao
21
thì số khung kí ch hoạ t trong Stack cà ng nhiề u, do đó, có khả nă ng dẫ n đế n trà n
Stack (Stack overflow). Trong nhiề u trường hợp khi lậ p trì nh, nế u có thể được, ta
nê n gỡ đệ qui cho cá c bà i toá n.
III. ví dụ


- Hà m không đệ qui
:
long giaithua (int n)
{ long gt=1;
for (int i=1; i<=n; i++)
gt= gt * i ;
return (gt);
}
22
Ví dụ 2: Hà m FIBONACCI:

F
n
=
{

1 ; n =0,1
F
n-1
+ F
n-2
; n>1
Nhận xé t
:
- Theo đị nh nghĩ a trê n, hà m Fibonacci có lời gọi đệ qui.
- Quá trì nh tí nh dừng lạ i khi n= 1
- Hà m đệ qui
:
long fib(int n)
{ if (n==0 || n==1)

+ Dời (n-1) dĩ a từ cột A sang cột B ( với cột C là cột trung gian)
+ Dời dĩ a thứ n từ cột A sang cột C
+ Dời (n-1) dĩ a từ cột B sang cột C ( với cột A là cột trung gian)
- Chương trì nh
:
void hanoi (int n, char cotA, char cotC, char cotB)
{
if(n == 1)
printf("\n%s%c%s%c", " chuyen dia 1 tu cot ", cotA, " den cot ", cotC);
else
{
hanoi(n-1, cotA, cotB, cotC);
printf("\n%s%d%s%c%s%c", " chuyen dia ", n, " tu cot ", cotA,
" den cot ", cotC);
hanoi(n-1, cotB, cotC, cotA);
}
}
IV. CáC THUậT TOáN LầN NGƯợC
:
Trong lậ p trì nh, đôi khi ta phả i xá c đị nh cá c thuậ t giả i để tì m lời giả i cho
cá c bà i toá n nhấ t đị nh nhưng không phả i theo một luậ t tí nh toán cố đị nh, mà
bằ ng cá ch thử-và -sai. Cá ch chung là phâ n tí ch thử-và -sai thà nh những công việ c
cục bộ. Thông thường công việ c nà y đ ược thực hiệ n trong dạ ng đệ qui và bao
gồm việ c thă m dò một số hữu hạ n cá c nhiệ m vụ nhỏ. Trong bà i giả ng nà y ta
không tì m hiể u cá c qui tắ c tì m kiế m tổng quá t, mà chỉ tì m những nguyê n lý
chung để chia việ c giả i bà i toá n thà nh những việ c nhỏ và ứng dụng của sự đệ qui
là chủ đề chí nh. Trước hế t, ta minh họa kỹ thuậ t că n bản bằ ng cá ch xé t bà i toá n
m đi tuầ n.
Ví dụ 1
. Bà i toá n m đi tuầ n.

, hàng y
0
.
Với tọa độ bắ t đầ u (x
0
,y
0
), có tấ t cả 8 ô (u,v) mà con m có thể đi đến được.
Chúng đ ược đánh số từ 1 đế n 8 trong hì nh 2.1
Phương pháp đơn giản để có được u,v từ x,y là cộng cá c chê nh lệ ch cột,
dòng về tọa độ đ ược lưu trong 2 mả ng a và b. Cá c giá trị trong 2 mả ng a, b đ
đ ược khởi động thí ch ứng như sau:
Ta xem như có 1 hệ trục tọa độ (Oxy) ngay tạ i vị trí (x
0
,y
0
) của con m , thì :
+ Vị trí 1 mà con m có thể đi đ ược là :
u= x
0
+ 2, v = y
0
+ 1
+ Vị trí 2 mà con m có thể đi đ ược là :
u= x
0
+ 1, v = y
0
+ 2
+ Vị trí 3 mà con m có thể đi đ ược là :

{ chọn một nước đi;
if chấ p nhậ n đ ược
{ ghi nhậ n nước đi;
if bà n cờ chưa đầ y
{ thử nước đi kế tạ i vị trí vừa ghi nhậ n đ ược;
if không đ ược
xóa nước đi trước
}
}
} while (không đi đ ược && còn nước đi)
}
* Nhận xé t
:
- Để xá c đị nh tọa độ (u,v) của nước đi kế ( 0 i 7 ), ta thực hiệ n như sau:
u = x + a[i] ; v = y + b[i]
- Điề u kiệ n để nước đi kế chấ p nhậ n đ ược là (u,v) phả i thuộc bà n cờ và con
m chưa đi qua ô đó, nghĩ a là ta phả i thỏa cá c điề u kiệ n sau:
(0 u <KICHTHUOC && 0 v< KICHTHUOC && BanCo[u][v]==0 )
- Ghi nhậ n nước đi thứ n, nghĩ a là BanCo [u][v] = n; còn bỏ việ c ghi nhậ n
nước đi là BanCo [u][v] = 0
- Bà n cờ đầ y khi ta đ đi qua tấ t cả cá c ô trong BanCo, lúc đó :
n = KICHTHUOC
2
.
Qua nhậ n xé t trê n, ta có thuậ t giả i chi tiế t hơn như sau:
void thu_nuoc_di(int n, int x, int y, int &q) // thử 8 cá ch đi của con m tạ i
// nước thứ n xuất phát từ ô (x,y)
{ int u,v, q1;
khởi động cá c chọn lựa có thể đi