›
›

Bài giảng Cấu trúc dữ liệu và thuật toán - Chương 2: Thuật toán đệ qui - Nguyễn Đức Nghĩa

Download
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, ...  
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  
17  
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 s a  
n
k
k1  
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  
  (15) 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) lS (llà xâu rỗng)  
– (R) Nếu bS thì 0b0, 0b1, 1b0, 1b1S .  
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 1:  
Step 2:  
...  
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 2:  
Bước 3: ví dụ  
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  
Gii 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 gii 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  
r
8
p
q
1
2
3
4
5
6
7
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  
MERGE-SORT(A, p, q)  
MERGE-SORT(A, q + 1, r)  
MERGE(A, p, q, r)  
endif  
Chia (Divide)  
Trị (Conquer)  
Trị (Conquer)  
Tổ hợp (Combine)  
• 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  
Tải về để xem bản đầy đủ
pdf 96 trang Thùy Anh 18760 Free
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Cấu trúc dữ liệu và thuật toán - Chương 2: Thuật toán đệ qui - Nguyễn Đức Nghĩa", để tải tài liệu gốc về máy hãy click vào nút Download ở trên

File đính kèm:

  • pdfbai_giang_cau_truc_du_lieu_va_thuat_toan_chuong_thuat_toan_d.pdf