Bài giảng Cấu trúc dữ liệu và thuật toán - Chương 1: Các khái niệm cơ bản - Nguyễn Khánh Phương

= 7 ?
• Giải: Phương trình đặc trưng của công thức đệ quy là
 r2 – r – 2 = 0.
Có 2 nghiệm phân biệt r1 = 2 và r2 = -1.
Do đó, dãy {an} là lời giải của công thức đệ quy khi và chỉ khi: 
 n n
 an = 12 + 2(-1) với giá trị nào đó của 1 và 2.
 n n
Cho biểu thức an = 12 + 2(-1) và các điều kiện đầu a0 = 2 và a1 = 7, ta có
 a0 = 2 = 1 + 2
 a1 = 7 = 1 2 + 2 (-1)
Giả hệ phương trình này ta có:
 = 3 và = -1.
 1 2
Do đó, lời giải của công thức đệ quy với ddieuf kiện đầu đã cho là dãy {an} với
 n n
 an = 3 2 – (-1)
 135
Giải CTĐQ TTTNHSH
Ví dụ 2: Tìm lời giải cho công thức đệ quy (dãy Fibonacci)
 Fn = Fn-1 + Fn-2, n 2,
 F0 = 0, F1 = 1
Giả: Phương trình đặc trưng của công thức đệ quy
 r2 – r – 1 = 0.
Có 2 nghiệm phân biệt là Leonardo Fibonacci
 1170-1250
 136
Trường hợp nghiệm kép
Định lý 2: Cho c1, c2 là các hằng số thực, c2 0. Giả sử phương
 2
trình r - c1 r - c2 = 0 có nghiệm kép r0. Khi đó dãy số {an } là
nghiệm của công thức đệ qui an = c1 an-1 + c2 an-2
khi và chỉ khi
 n n
 a n 1 r0 2 nr0
n = 0, 1, ..., trong đó 1 , 2 là các hằng số.
 NGUYỄN KHÁNH PHƢƠNG137
 Bộ môn KHMT – ĐHBK HN
Ví dụ 3
Tìm nghiệm cho công thức đệ quy
 an = 6 an-1 - 9 an-2
 với điều kiện đầu a0 = 1 và a1 = 6.
Giải: 
Phương trình đặc trưng: 
r2 - 6 r + 9 = 0 có nghiệm kép r = 3. Do đó nghiệm của hệ thức có dạng: 
 n n
 an = 1 3 + 2 n 3 .
Để tìm 1, 2 , sử dụng điều kiện đầu ta có
 a0 = 1 = 1 , 
 a1 = 6 = 1 . 3 + 2 .1. 3
Giải hệ này ta tìm được 1 = 1 và 2 = 1. 
Từ đó nghiệm của hệ thức đã cho là:
 n n
 an = 3 + n 3 .
 CTĐQ: an = c1an−1 +  + ckan−k
 k k−1
 Phương trình đặc trưng: r − c1r −  − ck = 0
 138
Trường hợp tổng quát
Định lý 3. Cho c1, c2, ..., ck là các số thực, ck 0. Giả sử phương trình
đặc trưng:
 k k-1 k-2
 r - c1 r - c2 r - . . . - ck = 0
 có k nghiệm phân biệt r1, r2, ..., rk . Khi đó dãy số {an} là nghiệm của
 công thức:
 an = c1 an-1 + c2 an-2 +...+ ck an-k,
 khi và chỉ khi
 n n n
 an = 1 r1 + 2 r2 + . . . + k rk
 với n = 0, 1, 2,..., trong đó , , ..., là các hằng số
 1 2 k
 139
Ví dụ 4
Tìm nghiệm của công thức đệ quy
 an = 6 an-1 - 11 an-2 + 6 an-3
 với điều kiện đầu
 a0 = 2, a1 = 5, a2 = 15.
Giải: Phương trình đặc trưng
 r3 - 6 r2 + 11 r - 6 = 0
 có 3 nghiệm r1 = 1, r2 = 2, r3 = 3. 
Vì vậy, nghiệm có dạng
 n n n
 an = 1 1 + 2 2 + 3 3 .
 CTĐQ: an = c1an−1 +  + ckan−k
 k k−1
 Phương trình đặc trưng: r − c1r −  − ck = 0
 140
Ví dụ 4
Sử dụng các điều kiện đầu ta có hệ phương trình sau đây để xác
định các hằng số 1, 2, 3:
 a0 = 2 = 1 + 2 + 3
 a1 = 5 = 1 + 2.2 + 3.3
 a2 = 15 = 1 + 2.4 + 3.9.
Giải hệ phương trình trên ta thu được
 1 = 1, 2 = -1 vµ 3 = 2. 
Vậy nghiệm của công thức đã cho là
 n n
 an = 1 - 2 + 2. 3
 141
Trường hợp tổng quát
 k
 k k i
 r c i r 0
 i 1
 k
 a n c i a n i
 i 1
 t m i 1
 j n
 a n i , j n ri
 i 1 j 0
 142
Ví dụ 5
Giải công thức đệ qui:
 cn = – 4cn-1 + 3cn-2 + 18cn-3 , n 3,
 c0 = 1; c1 = 2; c2 = 13.
Giải: Phương trình đặc trưng
 r3 + 4r2 – 3r – 18 = (r – 2)(r + 3)2 = 0 
Vậy nghiệm tổng quát của công thức:
 143
1.6. Giải công thức đệ quy: Các phương pháp khác
• Trên thực tế, khi phân tích độ phức tạp của một thuật toán nào đó nhờ
 sử dụng công thức đệ quy tuyến tính, thì công thức đệ quy ít khi có
 bậc lớn hơn 2.
• Do đó, ta cũng có thể sử dụng hai phương pháp sau đây để giải công
 thức đệ quy
 – Thay thế quay lui: xuất phát từ công thức đã cho, ta thế lần lượt lùi về các số
 hạng phía trước của công thức đệ quy
 – Cây đệ quy: biểu diễn công thức đệ quy bởi một cây đệ quy. Xuất phát từ công
 thức đệ quy đã cho, ta biểu diễn các số hạng đệ quy có kích thước dữ liệu đầu
 vào lớn ở mức A nào đó trên cây bởi các dữ liệu đầu vào nhỏ hơn ở mức A+1 
 của vây, và tính các số hạng không đệ quy. Cuối cùng, tính tổng tất cả các số
 hạng không đệ quy ở tất cả các mức của cây.
1.6. Giải công thức đệ quy:
Phương pháp 2: Thay thế quay lui
Ví dụ 1: Giải công thức đệ quy
 T(n)= T(n-1) + 2n
 với T(1) = 5
Giải:
Ta tiến hành thay thế lần lượt các số hạng của công thức đệ quy bằng cách lùi
lại các số hạng phía trước:
T(n) = T(n-1) + 2n
 = T((n-1) -1) + 2(n-1) + 2n
 = T(n-2) + 2 (n-1) + 2n
 = T((n-2)-1) + 2(n-2) + 2(n-1) + 2n
 = T(n-3) +2(n-2) + 2(n-1) + 2n 
1.6. Giải công thức đệ quy:
Phương pháp 2: Thay thế quay lui
1.6. Giải công thức đệ quy:
Phương pháp 2: Thay thế quay lui
Ví dụ 2: Giải công thức đệ quy
 T(n)= T(n/2) + c
 với T(1) = 2, và c là hằng số
T(n) = T(n/2) + c thay thế T(n/2)
 = T(n/4) + c + c thay thế T(n/4)
 = T(n/8) + c + c + c
 = T(n/23) + 3c 
 = 
 = T(n/2k) + kc
 logn
T(n) = T(n/2 ) + clogn “chọn k = logn”
 = T(n/n) + clogn
 = T(1) + clogn = 2 +clogn
Ví dụ 3
Hàm tính giai thừa
Xét thuật toán đệ quy tính n!
 NGUYỄN KHÁNH PHƢƠNG
 Bộ môn KHMT – ĐHBK HN
Ví dụ 3
Factorial(n);
Bao nhiêu lần hàm Factorial được gọi khi chúng ta thực hiện lệnh Factorial(n); ?
• Khi n = 1, hàm Factorial được gọi 1 lần T(1) = 1
• Khi n > 1:
 – Gọi hàm Factorial 1 lần, T(n) = 1 + T(n-1)
 – Cộng với số lần gọi trong lệnh đệ quy Factorial(n − 1) T(n-1)
Do đó ta có công thức đệ quy:
 T(1) = 1 Tìm công thức dạng hiện tính T(n) với
 T(n) = 1 + T(n − 1), n >1 mọi giá trị của n
1.6. Giải công thức đệ quy:
Phương pháp 2: Thay thế quay lui
Factorial(n);
T(n) = T(n − 1) + 1, n >1
 = [T(n-2) +1] + 1 [có 2 số “1”]
 =[[T(n-3)+1]+1]+1 [có 3 số “1”]
 =.
 = T(n – (n-1)) + (n-1) [có n-1 số “1”]
 = T(1) + (n-1)
 = 1 + (n-1)
 = n
Ví dụ 4
Có bao nhiêu phép nhân M(n) được thực thi khi thực hiện hàm Factorial?
• Khi n = 1 không phép nhân nào được thực hiện M(1) = 0
• Khi n > 1:
 – Ta thực hiện 1 lần phép nhân. 
 – Cộng với số lần thực hiện phép nhân trong lệnh gọi đệ quy Factorial(n − 1) M(n-1)
Do đó ta có công thức đệ quy:
 M(0) = 0; M(1) = 0 
 M(n) = 1 + M(n − 1), n >1
1.6. Giải công thức đệ quy:
Phương pháp 2: Thay thế quay lui
VÝ dô 5. (Bµi to¸n th¸p Hµ néi). Trß ch¬i th¸p Hµ néi ®ư•îc trình bµy như• sau: “Cã 3
cäc a, b, c. Trªn cäc a cã mét chång gåm n c¸i ®Üa ®ư•êng kÝnh gi¶m dÇn tõ d•ưíi lªn
trªn. CÇn ph¶i chuyÓn chång ®Üa tõ cäc a sang cäc c tu©n thñ qui t¾c:
1. Mỗi lần chỉ chuyển 1 đĩa
2. Chỉ được xếp đĩa có đường kính nhỏ hơn lên trên đĩa có đường kính lớn hơn.
 Trong qu¸ trình chuyÓn ®•ưîc phÐp dïng cäc b lµm cäc trung gian.
Bµi to¸n ®Æt ra lµ: Tìm công thức đệ qui cho hn là sè lÇn di chuyÓn ®Üa Ýt nhÊt cÇn thùc
hiÖn ®Ó hoàn thành nhiÖm vô ®Æt ra trong trß ch¬i th¸p Hµ néi.
 Cọc a Cọc c Cọc b 152
 Tower of Hanoi: n=5
1. Mỗi lần chỉ chuyển 1 đĩa
2. Chỉ được xếp đĩa có đường kính nhỏ hơn lên trên đĩa có đường kính lớn hơn
 Cọc a Cọc c Cọc b 153
 Bài toán: chuyển n đĩa từ cọc a sang cọc c sử dụng cọc b làm trung gian
 Cần tìm hn là sè lÇn di chuyÓn ®Üa Ýt nhÊt cÇn thùc hiÖn
 hn = 2hn-1 + 1, n ≥ 2.
ViÖc di chuyÓn ®Üa gåm 3 bư•íc:
 (1) ChuyÓn n-1 ®Üa tõ cäc a ®Õn cäc b sö dông cäc c lµm trung gian.
 Bài toán kích thước n-1 Số lần di chuyển = hn-1
 (2) ChuyÓn 1 ®Üa (®Üa víi ®•ưêng kÝnh lín nhÊt) tõ cäc a ®Õn cäc c.
 Số lần di chuyển = 1
 (3) ChuyÓn n-1 ®Üa tõ cäc b ®Õn cäc c (sö dông cäc a lµm trung gian).
 Bài toán kích thước n-1 Số lần di chuyển = hn-1
 Cọc a Cọc c Cọc b 154
Tower of Hanoi: n=5
 (1) ChuyÓn n-1 ®Üa tõ cäc a ®Õn cäc b sö dông cäc c lµm trung gian.
 Bài toán kích thước n-1 Số lần di chuyển = hn-1
 (2) ChuyÓn 1 ®Üa (®Üa víi ®•ưêng kÝnh lín nhÊt) tõ cäc a ®Õn cäc c.
 Số lần di chuyển = 1
 (3) ChuyÓn n-1 ®Üa tõ cäc b ®Õn cäc c (sö dông cäc a lµm trung gian).
 Bài toán kích thước n-1 Số lần di chuyển = hn-1
 Cọc a Cọc c Cọc b 155
1.6. Giải công thức đệ quy:
Phương pháp 2: Thay thế quay lui
Ta có thể tìm được công thức trực tiếp cho hn bằng phương pháp thế
quay lui:
 hn = 2 hn−1 + 1
 2 
 = 2 (2 hn−2 + 1) + 1 = 2 hn−2 + 2 + 1
 2 3 2
 = 2 (2 hn−3 + 1) + 2 + 1 = 2 hn−3 + 2 + 2 + 1
 n−1 n−2
 = 2 h1 + 2 +  + 2 + 1
 n−1 n−2
 = 2 + 2 +  + 2 + 1 (do h1 = 1)
 = 2n − 1
 156
1.6. Giải công thức đệ quy:
Phương pháp 3: Cây đệ quy
• Để giải công thức đệ quy bằng phương pháp này: ta sẽ vẽ cây đệ quy mô tả công thức đã
 cho
• Mỗi nút của cây tương ứng với 1 hàm dữ liệu đầu vào. Càng đi xuống phía dưới cây, 
 kích thước dữ liệu đầu vào càng giảm.
• Mức cuối cùng của cây tương ứng với kích thước dữ liệu đầu vào nhỏ nhất
Ví dụ 1: Thuật toán đệ quy giải bài toán dãy con lớn nhất
 O(n)
 O(n)
 T(n) = 2T(n/2)+O(n)
 Giải bằng phương pháp cây đệ
 T(n/2) quy, ta sẽ thu được:
 T(n/2) T(n) = O(nlogn)
 158
Ví dụ 1: Giải công thức đệ quy: 
 T(n) = 2T(n/2) + n, T(1) = 4
 n*4
• Giá trị hàm T(n) bằng tổng các giá trị tại tất cả các mức:
• Vì mức cuối (sâu nhất) log2n có giá trị = 4n, ta có
1.6. Giải công thức đệ quy:
Phương pháp 3: Cây đệ quy
• Ví dụ 2: Giải công thức đệ quy
 T(n) = T(n/ ) + f(n), T( ) = c 
Ví dụ 2: Giải công thức đệ quy
T(n) = T(n/ ) + f(n), T( ) = c 
 Iteration Cost
 0 TT(n) f(n)
 1 f(n/ )
 T(n/ ) T(n/ ) T(n/ )
 2f(n/ 2)
 2 T(n/ 2) T(n/ 2) T(n/ 2) T(n/ 2)
 . .
 . .
 i i f(n/ i)
 . .
 log n
 • Giá trị của hàm bằng tổng các giá trị trên tất cả các mức của cây:
Ví dụ 3: Tìm kiếm nhị phân dưới dạng đệ quy
Đầu vào: Mảng S gồm n phần tử: S[0],,S[n-1] đã sắp xếp theo thứ tự
tăng dần; Giá trị key.
Đầu ra: chỉ số của phần tử có giá trị key nếu có; -1 nếu key không xuất
hiện trong mảng S
int binsearch(int low, int high, int S[], int key)
{
 if (low <= high) 
 {
 mid = (low + high) / 2; 
 if (S[mid]==key) return mid; 
 else if (key < S[mid])
 return binsearch(low, mid-1, S, key); 
 else 
 return binsearch(mid+1, high, S, key); 
 }
 else return -1; NGUYỄN KHÁNH PHƢƠNG
 Bộ môn KHMT – ĐHBK HN
} 162
Ví dụ 3: Tìm kiếm nhị phân dưới dạng đệ quy
int binsearch(int low, int high, int S[], int key)
{
 if (low <= high) 
 {
 mid = (low + high) / 2; 
 if (S[mid]==key) return mid; 
 else if (key < S[mid]) key=33
 return binsearch(low, mid-1, S, key); 
 else 
 return binsearch(mid+1, high, S, key); 
 }
 else return -1; 
}
 6 13 14 25 33 43 51 53 64 72 84 93 95 96 97
 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
 lo hi
 163
Ví dụ 3: Tìm kiếm nhị phân dưới dạng đệ quy
int binsearch(int low, int high, int S[], int key)
{
 if (low <= high) 
 {
 mid = (low + high) / 2; 
 if (S[mid]==key) return mid; 
 else if (key < S[mid]) key=33
 return binsearch(low, mid-1, S, key); 
 else 
 return binsearch(mid+1, high, S, key); 
 }
 else return -1; 
}
 6 13 14 25 33 43 51 53 64 72 84 93 95 96 97
 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
 lo mid hi
 164
Ví dụ 3: Tìm kiếm nhị phân dưới dạng đệ quy
int binsearch(int low, int high, int S[], int key)
{
 if (low <= high) 
 {
 mid = (low + high) / 2; 
 if (S[mid]==key) return mid; 
 else if (key < S[mid]) key=33
 return binsearch(low, mid-1, S, key); 
 else 
 return binsearch(mid+1, high, S, key); 
 }
 else return -1; 
}
 6 13 14 25 33 43 51 53 64 72 84 93 95 96 97
 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
 lo hi
 165
Ví dụ 3: Tìm kiếm nhị phân dưới dạng đệ quy
int binsearch(int low, int high, int S[], int key)
{
 if (low <= high) 
 {
 mid = (low + high) / 2; 
 if (S[mid]==key) return mid; 
 else if (key < S[mid]) key=33
 return binsearch(low, mid-1, S, key); 
 else 
 return binsearch(mid+1, high, S, key); 
 }
 else return -1; 
}
 6 13 14 25 33 43 51 53 64 72 84 93 95 96 97
 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
 lo mid hi
 166
Ví dụ 3: Tìm kiếm nhị phân dưới dạng đệ quy
int binsearch(int low, int high, int S[], int key)
{
 if (low <= high) 
 {
 mid = (low + high) / 2; 
 if (S[mid]==key) return mid; 
 else if (key < S[mid]) key=33
 return binsearch(low, mid-1, S, key); 
 else 
 return binsearch(mid+1, high, S, key); 
 }
 else return -1; 
}
 6 13 14 25 33 43 51 53 64 72 84 93 95 96 97
 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
 lo hi
 167
Ví dụ 3: Tìm kiếm nhị phân dưới dạng đệ quy
int binsearch(int low, int high, int S[], int key)
{
 if (low <= high) 
 {
 mid = (low + high) / 2; 
 if (S[mid]==key) return mid; 
 else if (key < S[mid]) key=33
 return binsearch(low, mid-1, S, key); 
 else 
 return binsearch(mid+1, high, S, key); 
 }
 else return -1; 
}
 6 13 14 25 33 43 51 53 64 72 84 93 95 96 97
 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
 lo mid hi
 168
Ví dụ 3: Tìm kiếm nhị phân dưới dạng đệ quy
int binsearch(int low, int high, int S[], int key)
{
 if (low <= high) 
 {
 mid = (low + high) / 2; 
 if (S[mid]==key) return mid; 
 else if (key < S[mid]) key=33
 return binsearch(low, mid-1, S, key); 
 else 
 return binsearch(mid+1, high, S, key); 
 }
 else return -1; 
}
 6 13 14 25 33 43 51 53 64 72 84 93 95 96 97
 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
 lo
 hi
 169
Ví dụ 3: Tìm kiếm nhị phân dưới dạng đệ quy
int binsearch(int low, int high, int S[], int key)
{
 if (low <= high) 
 {
 mid = (low + high) / 2; 
 if (S[mid]==key) return mid; 
 else if (key < S[mid]) key=33
 return binsearch(low, mid-1, S, key); 
 else 
 return binsearch(mid+1, high, S, key); 
 }
 else return -1; 
}
 6 13 14 25 33 43 51 53 64 72 84 93 95 96 97
 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
 lo
 hi
 mid
 170
Ví dụ 3: Tìm kiếm nhị phân dưới dạng đệ quy
int binsearch(int low, int high, int S[], int key)
{
 if (low <= high) 
 {
 mid = (low + high) / 2; 
 if (S[mid]==key) return mid; 
 else if (key < S[mid]) key=33
 return binsearch(low, mid-1, S, key); 
 else 
 return binsearch(mid+1, high, S, key); 
 } key=31??
 else return -1; 
}
 6 13 14 25 33 43 51 53 64 72 84 93 95 96 97
 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
 lo
 hi
 mid
 171
Ví dụ 3: Tìm kiếm nhị phân dưới dạng đệ quy
Đầu vào: Mảng S gồm n phần tử: S[0],,S[n-1] đã sắp xếp theo thứ tự
tăng dần; Giá trị key.
Đầu ra: chỉ số của phần tử có giá trị key nếu có; -1 nếu key không xuất
hiện trong mảng S
int binsearch(int low, int high, int S[], int key)
{
 if (low <= high) 
 {
 mid = (low + high) / 2; 
 if (S[mid]==key) return mid; 
 else if (key < S[mid])
 return binsearch(low, mid-1, S, key); 
 else 
 return binsearch(mid+1, high, S, key); 
 }
 else return -1; 
}
 binsearch(0, n-1, S, key);
 Có bao nhiêu lần hàm binsearch được gọi trong trường hợp tồi nhất ?
 172
Ví dụ 3: Tìm kiếm nhị phân dưới dạng đệ quy
int binsearch(int low, int high, int S[], int key)
{
 if (low <= high) T(0) = ?
 { binsearch(0, -1, S, key);
 mid = (low + high) / 2; 
 if (S[mid]==key) return mid; T(1) = ?
 else if (key < S[mid])
 return binsearch(low, mid-1, S, key); binsearch(0, 0, S, key);
 else 
 return binsearch(mid+1, high, S, key); binsearch(0, -1, S, key);
 } binsearch(1, 0, S, key);
 else return -1; 
}
 binsearch(0, n-1, S, key);
Gọi T(n): số lần hàm binsearch được gọi trong trường hợp tồi nhất khi mảng S có n phần tử
 • T(0) = 1 Công thức đệ quy:
 • T(1) = 2 T(n) = T(n/2) + 1
 • T(2) = T(1) + 1 = 3 T(0) = 1
 • T(4) = T(2) + 1 = 4 T(1) = 2
 • T(8) = T(4) + 1 = 4 + 1 = 5 ậ ả ứ ệ
 Bài t p: Hãy gi i công th c đ quy này 173
 • T(n) = T(n/2) + 1