Bài giảng Cấu trúc dữ liệu & thuật toán - Chương 2: Thuật toán đệ qui trình bày khái niệm về đệ qui, thuật toán đệ qui, một số ví dụ minh họa, phân tích thuật toán đệ qui, đệ qui có nhớ và chứng minh tính đúng đắn của thuật toán đệ qui.
AMBIENT/
Chủ đề:
Nội dung Text: Bài giảng Cấu trúc dữ liệu & thuật toán: Chương 2 - Nguyễn Đức Nghĩa
- Chương 2
Thuật toán đệ qui
Nội dung
2.1. Khái niệm đệ qui
2.2. Thuật toán đệ qui
2.3. Một số ví dụ minh hoạ
2.4. Phân tích thuật toán đệ qui
2.5. Đệ qui có nhớ
2.6. Chứng minh tính đúng đắn của thuật toán đệ qui
2
Cấu trúc dữ liệu và thuật toán - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội
- 2.1. Khái niệm đệ qui
• 2.1.1 Khái niệm đệ qui
• 2.1.2 Thuật toán đệ qui
3
Cấu trúc dữ liệu và thuật toán - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội
Khái niệm đệ qui
• Trong thực tế ta thường gặp những đối tượng bao gồm chính
nó hoặc được định nghĩa dưới dạng của chính nó. Ta nói các
đối tượng đó được xác định một cách đệ qui.
• Ví dụ:
– Điểm quân số
– Fractal
– Các hàm được định nghĩa đệ qui
– Tập hợp được định nghĩa đệ qui
– Định nghĩa đệ qui của cây
– ...
4
Cấu trúc dữ liệu và thuật toán - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội
- Đệ qui: Điểm quân
5
Cấu trúc dữ liệu và thuật toán - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội
Đệ qui: Điểm quân
6
Cấu trúc dữ liệu và thuật toán - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội
- Đệ qui: Điểm quân
7
Cấu trúc dữ liệu và thuật toán - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội
Đệ qui: Điểm quân
8
Cấu trúc dữ liệu và thuật toán - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội
- Đệ qui: Điểm quân
9
Cấu trúc dữ liệu và thuật toán - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội
Đệ qui: Điểm quân
10
Cấu trúc dữ liệu và thuật toán - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội
- Đệ qui: Điểm quân
11
Cấu trúc dữ liệu và thuật toán - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội
Đệ qui: Điểm quân
12
Cấu trúc dữ liệu và thuật toán - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội
- Đệ qui: Điểm quân
13
Cấu trúc dữ liệu và thuật toán - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội
Đệ qui: Điểm quân
14
Cấu trúc dữ liệu và thuật toán - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội
- Đệ qui: Điểm quân
15
Cấu trúc dữ liệu và thuật toán - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội
Fractals
fractals là ví dụ về hình ảnh được
xây dựng một cách đệ qui (đối tượng
lặp lại một cách đệ qui).
16
Cấu trúc dữ liệu và thuật toán - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội
- Hàm đệ qui (Recursive Functions)
Các hàm đệ qui được xác định phụ thuộc vào biến nguyên không
âm n theo sơ đồ sau:
Bước cơ sở (Basic Step): Xác định giá trị của hàm tại n=0: f(0).
Bước đệ qui (Recursive Step): Cho giá trị của f(k), k ≤ n, đưa ra
qui tắc tính giá trị của f(n+1).
Ví dụ 1:
f(0) = 3, n=0
f(n+1) = 2f(n) + 3, n>0
Khi đó ta có: f(1) = 2 × 3 + 3 = 9, f(2) = 2 × 9 + 3 = 21, ...
17
Cấu trúc dữ liệu và thuật toán - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội
Hàm đệ qui (Recursive Functions)
Ví dụ 2: Định nghĩa đệ qui của n! :
f(0) = 1
f(n+1) = f(n) × (n+1)
Để tính giá trị của hàm đệ qui ta thay thế dần theo định nghĩa đệ qui
để thu được biểu thức với đối số càng ngày càng nhỏ cho đến tận
điều kiện đầu.
Chẳng hạn: đệ qui
5! = 5 · 4! = 5 · 4 · 3! = 5 · 4 · 3 · 2! = 5 · 4 · 3 · 2 · 1! =
5 · 4 · 3 · 2 · 1 · 0! = 5 · 4 · 3 · 2 · 1 · 1 = 120
điều kiện đầu
18
Cấu trúc dữ liệu và thuật toán - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội
- Hàm đệ qui (Recursive Functions)
n
Ví dụ 3: Định nghĩa đệ qui của tổng sn ak
k 1
s1 = a1
sn = sn-1 + an
Ví dụ 4: Dãy số Fibonacci
f(0) = 0, f(1) = 1,
f(n) = f(n-1) + f(n-2) với n > 1
19
Cấu trúc dữ liệu và thuật toán - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội
Fibonacci Numbers
Sự phát triển của bày thỏ
Số lượng
cặp thỏ
20
Cấu trúc dữ liệu và thuật toán - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội
- Nói thêm về Fibonacci
21
Cấu trúc dữ liệu và thuật toán - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội
Số Fibonacci trong các cấu trúc tự nhiên
The left and right going
spirals are neighboring
Fibonacci numbers!
22
Cấu trúc dữ liệu và thuật toán - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội
- Tỷ lệ vàng (Golden Section)
x y
x y x 1
(1 5) 1.6180 Phi
x y 2
23
Cấu trúc dữ liệu và thuật toán - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội
Tập hợp được xác định đệ qui
(Recursively defined sets)
Tập hợp có thể xác định một cách đệ qui theo sơ đồ tương tự như
hàm đệ qui:
Basis Step: định nghĩa tập cơ sở (chẳng hạn tập rỗng).
Recursive Step : Xác định qui tắc để sản sinh tập mới từ các tập đã
có.
Ví dụ:
Basis Step: 3 là phần tử của S.
Recursive Step: nếu x thuộc S và y thuộc S thì x+y thuộc S.
3
3+3=6
3+6 = 9 & 6+6=12
...
24
Cấu trúc dữ liệu và thuật toán - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội
- Định nghĩa đệ qui của xâu
Giả sử = bảng chữ cái (alphabet).
Tập * các xâu (strings) trên bảng chữ cái được định nghĩa đệ
qui như sau:
Basic step: xâu rỗng là phần tử của *
Recursive step: nếu w thuộc * và x thuộc wx thuộc *
Ví dụ: Tập các xâu nhị phân thu được khi ={0,1}:
1) xâu rỗng
2) 0 & 1
3) 00 & 01 & 10 & 11
4) ...
25
Cấu trúc dữ liệu và thuật toán - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội
Độ dài của xâu
• Định nghĩa đệ qui độ dài length(w) của xâu w *
– (B) length(l)0
– (R) Nếu w* và x thì length(wx)= length(w)+1.
• Định nghĩa đệ qui của tập các xâu nhị phân độ dài chẵn.
– (B) lS (llà xâu rỗng)
– (R) Nếu b S thì 0b0, 0b1, 1b0, 1b1 S .
26
Cấu trúc dữ liệu và thuật toán - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội
- Công thức toán học
• Một công thức hợp lệ của các biến, các số và các phép toán từ tập
{+, -, *, /, ^} có thể định nghĩa như sau:
• Cơ sở: x là công thức hợp lệ nếu x là biến hoặc là số.
• Qui nạp: Nếu f, g là các công thức hợp lệ thì
(f + g), (f – g), (f * g), (f / g), (f ^ g)
là công thức hợp lệ.
• Theo định nghĩa ta có thể xây dựng các công thức hợp lệ như:
(x – y); ((z / 3) – y);
((z / 3) – (6 + 5)); ((z / (2 * 4)) – (6 + 5))
27
Cấu trúc dữ liệu và thuật toán - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội
Cây có gốc
Cây là cấu trúc dữ liệu quan trọng thường được dùng để tổ chức tìm kiếm và sắp
xếp dữ liệu
Cây có gốc (Rooted Trees): Cây có gốc bao gồm các nút, có một nút đặc biệt
được gọi là gốc (root) và các cạnh nối các nút.
Basic Step: Một nút là cây có gốc.
Recursive Step: Giả sử T1,...,Tn,... là các cây với gốc là r1,....rn,...
Nếu ta tạo một gốc mới r và nối gốc này với mỗi một trong số các gốc r1,...rn,...
bởi một cạnh tương ứng, ta thu được một cây có gốc mới.
Basis step: Step 2:
Step 1:
...
28
Cấu trúc dữ liệu và thuật toán - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội
- Cây nhị phân (Binary Trees)
Cây nhị phân mở rộng (Extended Binary Trees):
Basic Step: tập rỗng là cây nhị phân mở rộng.
Recursive Step: Nếu T1 và T2 là các cây nhị phân mở rộng, thì cây T1.T2 sau
đây cũng là cây nhị phân mở rộng: chọn một nút gốc mới và gắn T1 với gốc
bởi một cạnh như là cây con trái và gắn T2 như là cây con phải.
Bước 1: Bước 3: ví dụ
Bước 2:
29
Cấu trúc dữ liệu và thuật toán - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội
Cây nhị phân đầy đủ
Cây nhị phân đầy đủ (Full binary Trees): Chỉ khác định nghĩa
cây nhị phân mở rộng ở bước cơ sở:
Basic Step: Một nút là cây nhị phân đầy đủ.
Recursive Step: Giống như trong cây nhị phân mở rộng.
Kết quả là chúng ta không thể gắn cây rỗng vào bên trái cũng như
bên phải.
Khởi tạo:
Bước 1:
Không phải! Cây nhị phân đầy đủ có 0 hoặc 2 nút con.
30
Cấu trúc dữ liệu và thuật toán - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội
- Một số định nghĩa
Ký hiệu h(T) là độ cao của cây nhị phân đầy đủ. Định nghĩa đệ qui của h(T):
Basic Step: Chiều cao của cây T gồm duy nhất một nút gốc là h(T)=0.
Recursive Step: Nếu T1 và T2 là các cây nhị phân đầy đủ, thì cây nhị phân đầy
đủ T = T1.T2 có chiều cao h(T) = 1+max(h(T1), h(T2)).
Ký hiệu n(T) là số đỉnh trong cây. Ta có thể định nghĩa đệ qui n(T) như sau:
Basic Step: Số đỉnh trong cây T gồm duy nhất một nút gốc là n(T) = 1;
Recursive Step: Nếu T1 và T2 là các cây nhị phân đầy đủ, thì số đỉnh của cây
T = T1.T2 là n(T) = 1+n(T1)+n(T2).
31
Cấu trúc dữ liệu và thuật toán - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội
Định nghĩa đệ qui và Qui nạp
• Định nghĩa đệ qui và Qui nạp toán học có những nét tương
đồng và là bổ sung cho nhau. Định nghĩa đệ qui thường giúp
cho chứng minh bằng qui nạp các tính chất của các đối tượng
được định nghĩa đệ qui. Ngược lại, các chứng minh bằng qui
nạp toán học thường là cơ sở để xây dựng các thuật toán đệ
qui để giải quyết nhiều bài toán.
Chứng minh bằng qui nạp toán học thường bao gồm hai phần:
1. Bước cơ sở qui nạp – giống như bước cơ sở trong định
nghĩa đệ qui
2. Bước chuyển qui nạp – giống như bước đệ qui
32
Cấu trúc dữ liệu và thuật toán - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội
- Nội dung
2.1. Khái niệm đệ qui
2.2. Thuật toán đệ qui
2.3. Một số ví dụ minh hoạ
2.4. Phân tích thuật toán đệ qui
2.5. Đệ qui có nhớ
2.6. Chứng minh tính đúng đắn của thuật toán đệ qui
33
Cấu trúc dữ liệu và thuật toán - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội
Định nghĩa
• Thuật toán đệ qui là thuật toán tự gọi đến chính mình với đầu
vào kích thước nhỏ hơn.
• Việc phát triển thuật toán đệ qui là thuận tiện khi cần xử lý với
các đối tượng được định nghĩa đệ qui (chẳng hạn: tập hợp, hàm,
cây, ...trong các ví dụ nêu trong mục trước).
• Các thuật toán được phát triển dựa trên phương pháp chia để trị
thông thường được mô tả dưới dạng các thuật toán đệ qui (xem ví
dụ mở đầu)
• Các ngôn ngữ lập trình cấp cao thường cho phép xây dựng các
hàm (thủ tục) đệ qui, nghĩa là trong thân của hàm (thủ tục) có
chứa những lệnh gọi đến chính nó. Vì thế, khi cài đặt các thuật
toán đệ qui người ta thường xây dựng các hàm (thủ tục) đệ qui.
34
Cấu trúc dữ liệu và thuật toán - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội
- Cấu trúc của thuật toán đệ qui
• Thuật toán đệ qui thường có cấu trúc sau đây:
Thuật toán RecAlg(input)
begin
if (kích thước của input là nhỏ nhất) then
Thực hiện Bước cơ sở /* giải bài toán kích thước đầu vào nhỏ nhất */
else
RecAlg(input với kích thước nhỏ hơn); /* bước đệ qui */
/* có thể có thêm những lệnh gọi đệ qui */
Tổ hợp lời giải của các bài toán con để thu được lời_giải;
return (lời_giải)
endif
end;
35
Cấu trúc dữ liệu và thuật toán - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội
Thuật toán chia để trị
(Divide and conquer)
• Thuật toán chia để trị là một trong những phương pháp thiết kế
thuật toán cơ bản, nó bao gồm 3 thao tác
• Chia (Divide) bài toán cần giải ra thành một số bài toán
con
– Bài toán con có kích thước nhỏ hơn và có cùng dạng với
bài toán cần giải
• Trị (Conquer) các bài toán con
– Giải các bài toán con một cách đệ qui.
– Bài toán con có kích thước đủ nhỏ sẽ được giải trực tiếp.
• Tổ hợp (Combine) lời giải của các bài toán con
– Thu được lời giải của bài toán xuất phát.
36
Cấu trúc dữ liệu và thuật toán - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội
- Thuật toán chia để trị
• Sơ đồ của phương pháp có thể trình bày trong thủ tục đệ qui sau
đây:
procedure D-and-C (n);
begin
if n n0 then
Gi¶i bµi to¸n mét c¸ch trùc tiÕp
else
begin
Chia bµi to¸n thµnh a bµi to¸n con kÝch thíc n/b;
for (mçi bµi to¸n trong a bµi to¸n con) do D-and-C(n/b);
Tæng hîp lêi gi¶i cña a bµi to¸n con ®Ó thu ®îc lêi gi¶i cña bµi to¸n gèc;
end;
end;
37
Cấu trúc dữ liệu và thuật toán - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội
Thuật toán chia để trị
• Các thông số quan trọng của thuật toán:
– n0 - kích thước nhỏ nhất của bài toán con (còn gọi là neo đệ
qui). Bài toán con với kích thước n0 sẽ được giải trực tiếp.
– a - số lượng bài toán con cần giải
– b - liên quan đến kích thước của bài toán con được chia
38
Cấu trúc dữ liệu và thuật toán - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội
- Ví dụ: Sắp xếp trộn (Merge Sort)
• Bài toán: Cần sắp xếp mảng A[1 .. n]:
• Chia (Divide)
– Chia dãy gồm n phần tử cần sắp xếp ra thành 2 dãy, mỗi dãy có n/2
phần tử
• Trị (Conquer)
– Sắp xếp mỗi dãy con một cách đệ qui sử dụng sắp xếp trộn
– Khi dãy chỉ còn một phần tử thì trả lại phần tử này
• Tổ hợp (Combine)
– Trộn (Merge) hai dãy con được sắp xếp để thu được dãy được sắp xếp
gồm tất cả các phần tử của cả hai dãy con
39
Cấu trúc dữ liệu và thuật toán - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội
Merge Sort
p q r
1 2 3 4 5 6 7 8
MERGE-SORT(A, p, r)
5 2 4 7 1 3 2 6
if p < r Kiểm tra điều kiện neo
then q ← (p + r)/2 Chia (Divide)
MERGE-SORT(A, p, q) Trị (Conquer)
MERGE-SORT(A, q + 1, r) Trị (Conquer)
MERGE(A, p, q, r) Tổ hợp (Combine)
endif
• Lệnh gọi thực hiện thuật toán: MERGE-SORT(A, 1, n)
40
Cấu trúc dữ liệu và thuật toán - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội
Thêm vào BST
Báo xấu
Download
Vui lòng tải xuống để xem tài liệu đầy đủ
