›
›

Bài giảng Cấu trúc dữ liệu và Giải thuật - Chương II: Giải thuật đệ qui - Đỗ Bích Diệp

Download
Cấu trúc dữ liệu và giải thuật  
Cấu trúc dữ liệu và Giải thuật  
Chương II  
Giải thuật đệ qui  
Giải thuật đệ qui  
Nội dung  
™ Các khái niệm cơ bản  
™ Một số ví dụ  
™ Phân tích giải thuật đệ qui  
Đố Bích Diệp- Khoa CNTT-ĐHBKHN  
1
Cấu trúc dữ liệu và giải thuật  
Một số đối tượng đệ qui  
Một số đối tượng đệ qui  
z Hàm đệ qui:  
– Là hàm được xác định phụ thuộc vào một biến  
nguyên không âm n theo sơ đồ:  
z Bước cơ sở : xác định giá trị hàm tại một giá trị n giá trị  
nhỏ nhất có thể của biến  
z Bước đệ qui: Cho giá trị f(k) , đưa ra qui tắc để tính  
f(k+1)  
Đố Bích Diệp- Khoa CNTT-ĐHBKHN  
2
Cấu trúc dữ liệu và giải thuật  
Một số đối tượng đệ qui  
z Tập hợp đệ qui  
– Là tập được xác định như sau  
z Bước cơ sở: Định nghĩa tập cơ sở  
z Bước đệ qui: Xác định qui tắc để sản sinh tập mới từ  
tập đã có  
Một số đối tượng đệ qui  
z Định nghĩa đệ qui của xâu ký tự  
– A = bảng chữ cái, tập các xâu S trên bảng chữ  
cái A được xác định  
z Xâu rỗng là xâu trong S  
z Nếu w thuộc S và x là một ký tự trong A thì wx là xâu  
trong S  
Đố Bích Diệp- Khoa CNTT-ĐHBKHN  
3
Cấu trúc dữ liệu và giải thuật  
Một số đối tượng đệ qui  
z Cây  
– Định nghĩa đệ qui của cây  
z Một nút tạo thành 1 cây  
z Nếu có n cây T1, T2, …, Tn với nút gốc là r1, r2, … , rn; r  
là một nút có quan hệ cha-con r1, r2, … , rn thì tồn tại một  
cây mới T nhận r làm gốc  
Giải thuật đệ qui  
– Định nghĩa: Giải thuật đệ qui là giải thuật được  
định nghĩa sử dụng chính giải thuật có dạng  
giống nó  
– Cấu trúc của một thuật toán đệ qui bao gồm 2  
bước  
z Bước cơ sở  
– Với những giá trị đầu vào đủ nhỏ, bài toán có thể giải quyết  
trực tiếp  
z Bước đệ qui  
– Lời gọi đến giải thuật đang định nghĩa  
– Lời gọi đệ qui phải được định nghĩa để nó tiến gần hơn đến  
bước cơ sở  
Đố Bích Diệp- Khoa CNTT-ĐHBKHN  
4
Cấu trúc dữ liệu và giải thuật  
Các dạng giải thuật đệ qui  
– Đệ qui trực tiếp : AÆ A  
– Đệ qui gián tiếp: AÆB Æ…ÆA  
– Đệ qui đuôi  
z Lời gọi đệ qui luôn luôn nằm cuối cùng trong giải thuật  
Giải thuật đệ qui  
– Ví dụ: Hàm tính n!  
1if n = 0  
⎧
⎨
⎩
Fact(n) =  
n* Fact(n −1) if n > 0  
Function recursiveFactorial(n)  
Begin  
{Tính giá trị n! }  
Trường hợp cơ sở  
Lời gọi đệ qui  
1. if n = 0 then return 1  
else return n*FACT(n-1);  
2. End.  
Tổ hợp kết quả  
Đố Bích Diệp- Khoa CNTT-ĐHBKHN  
5
Cấu trúc dữ liệu và giải thuật  
Giải thuật đệ qui  
– Hình dung việc thực hiện giải thuật tính n!  
return 4 *6 = 24  
final answer  
call  
recursiveFactorial  
(4 )  
call  
return 3*2 = 6  
recursiveFactorial  
(3 )  
call  
return 2 *1 = 2  
recursiveFactorial  
(2 )  
call  
return 1*1 = 1  
recursiveFactorial  
(1 )  
return  
1
call  
recursiveFactorial  
(0 )  
Giải thuật đệ qui  
– Dãy Fibonacci  
0
if n = 0  
if n =1  
Fibonacci (n −1) + Fibonacci (n − 2) otherwise  
⎧
⎪
Fibonacci (n) = 1  
⎨
⎪
⎩
Function Fibonacci(n)  
Begin  
{Tính giá trị n! }  
1. if n <= 1 then return n  
else return (Fibonacci(n-1)+Fibonacci(n-2));  
2. End.  
Đố Bích Diệp- Khoa CNTT-ĐHBKHN  
6
Cấu trúc dữ liệu và giải thuật  
Giải thuật đệ qui  
– Thực hiện tính Fibonacci(6)  
Fibonacci(6)  
Fibonacci(5)  
Fibonacci(4) Fibonacci(3)  
Fibonacci(3) Fibonacci(2) Fibonacci(2)  
Fibonacci(1)  
Fionacci(4)  
Fibonacci(3) Fibonacci(2)  
Fibonacci(2)  
Fibonacci(1)  
Fibonacci(2)  
Fibonacci(1)  
Giải thuật đệ qui  
– Bài toán Tháp Hà nội  
z Có 3 cọc A, B, C và n đĩa có kích thước khác nhau  
z Ban đầu, các đĩa được xếp có thứ tự đĩa to ở trên, đĩa  
nhỏ ở dưới tại cọc A  
z Mục tiêu là chuyển n đĩa này sang cọc C với điều kiện  
mỗi lần được chuyển 1 đĩa, không được đặt đĩa to ở  
trên đĩa nhỏ  
B
n đĩa  
A
C
Đố Bích Diệp- Khoa CNTT-ĐHBKHN  
7
Cấu trúc dữ liệu và giải thuật  
Giải thuật đệ qui  
z Bước cơ sở : n <= 1, giải quyết trực tiếp  
B
B
A
C
A
C
Move(A, C)  
Giải thuật đệ qui  
z Bước đệ qui: Giả sử rằng bài toán chuyển n-1 đĩa đã  
được giải quyết , vậy có thể thực hiện với n đĩa ?  
B
B
A
C
A
C
B
A
C
Đố Bích Diệp- Khoa CNTT-ĐHBKHN  
8
Cấu trúc dữ liệu và giải thuật  
Giải thuật đệ qui  
B
B
B
A
A
C
C
A
C
B
A
C
Giải thuật đệ qui  
B
B
TOWER(n-1, A, C, B)  
Move(A, C)  
B
A
C
C
A
C
TOWER(n, A, B, C)  
A
TOWER(n-1, B, A, C)  
B
A
C
Đố Bích Diệp- Khoa CNTT-ĐHBKHN  
9
Cấu trúc dữ liệu và giải thuật  
Giải thuật đệ qui  
Procedure TOWER( n, A, B, C)  
Begin  
{n là số đĩa ban đầu trên cọc A, cọc đầu tiên được chỉ  
định là cọc chứa các đĩa cần chuyển, cọc thứ 2 là cọc  
trung chuyển, cọc thứ 3 là cọc cần chuyển đĩa đến }  
if n < 1 then return  
else begin  
call TOWER(n-1, A, C, B)  
call MOVE(A,C)  
call TOWER( n-1, B, A, C)  
end  
End  
Phân tích thuật toán đệ qui  
– Hàm thời gian thực hiện giải thuật T(n) là hàm đệ  
qui với tham số n  
Đố Bích Diệp- Khoa CNTT-ĐHBKHN  
10  
Cấu trúc dữ liệu và giải thuật  
Phân tích thuật toán đệ qui  
– Ví dụ 1  
Procedure f(n)  
{n là số nguyên không âm}  
Begin  
z T(0) = 1  
z T(n) = 2 + T(n-1)  
if (n > 0) then begin  
writeln(n) ;  
Call f(n-1);  
end  
End  
Phân tích giải thuật đệ qui  
– Ví dụ 2  
Function g( n)  
Begin  
z Trường hợp cơ sở  
T(1) = 2  
if (n =1) then  
z Đệ qui  
T(n) = c + 2* T(n/2)  
return 2;  
else  
return 3 * g(n / 2) + g( n / 2) + 5;  
End.  
Đố Bích Diệp- Khoa CNTT-ĐHBKHN  
11  
Cấu trúc dữ liệu và giải thuật  
Phân tích thời gian thực hiện giải thuật  
– Cách thức giải công thức đệ qui của thời gian  
thực hiện giải thuật đệ qui  
z Phương pháp lặp  
Phân tích giải thuật đệ qui  
z Phương pháp lặp  
– Giải công thức đệ qui của thời gian thành một  
tổng các toán hạng cụ thể  
z Lặp lại việc thay thế hàm cho đến khi bắt gặp trường  
hợp cơ sở  
z Tính tổng  
Đố Bích Diệp- Khoa CNTT-ĐHBKHN  
12  
Cấu trúc dữ liệu và giải thuật  
Phân tích giải thuật đệ qui  
– Ví dụ: T(n) = c + T(n/2)  
T(n) = c + T(n/2)  
= c + c + T(n/4)  
= c + c + c + T(n/8)  
Giả sử n = 2k  
T(n) = c + c + … + c + T(1)  
= clogn + T(1)  
Vậy ta có T(n) = O(logn)  
Phân tích giải thuật đệ qui  
– Ví dụ: T(n) = n + 2T(n/2)  
T(n) = n + 2T(n/2)  
= n + 2(n/2 + 2T(n/4))  
= n + n + 4T(n/4)  
= n + n + 4(n/4 + 2T(n/8))  
= n + n + n + 8T(n/8)  
… = in + 2iT(n/2i)  
Giả sử n = 2k thì ta sẽ rút gọn được  
T(n) = kn + 2kT(1)  
= nlogn + nT(1)  
Vậy T(n)= O(nlogn)  
Đố Bích Diệp- Khoa CNTT-ĐHBKHN  
13  
Cấu trúc dữ liệu và giải thuật  
Phân tích giải thuật đệ qui  
z Phân tích giải thuật tính giai thừa  
T(0) = c  
Function recursiveFactorial(n)  
Begin  
{Tính giá trị n! }  
1. if n = 0 then return 1  
T(n) = b + T(n - 1)  
= b + b + T(n - 2)  
= b +b +b + T(n - 3)  
…
else return n*FACT(n-1);  
2. End.  
= kb + T(n - k)  
Khi k = n, ta có:  
T(n) = nb + T(n - n)  
= bn + T(0)  
= bn + c.  
Vậy T(n) = O(n).  
Phân tích giải thuật đệ qui  
z Phân tích giải thuật Tháp Hà Nội  
T(1) = a  
Procedure TOWER( n, A, B, C)  
T(n) = b+ 2T(n-1)  
Begin  
if n < 1 then return  
else begin  
call TOWER(n-1, A, C, B);  
call MOVE(A,C);  
call TOWER( n-1, B, A, C);  
end  
End  
Đố Bích Diệp- Khoa CNTT-ĐHBKHN  
14  
Cấu trúc dữ liệu và giải thuật  
Phân tích giải thuật đệ qui  
T(n) = 2T(n – 1) + b  
= 2[2T(n – 2) + b] + b  
= 22 [2T(n – 3) + b] + 2b + b  
= 22 T(n – 2) + 2b + b  
= 23 T(n – 3) + 22b + 2b + b  
= 23 [2T(n – 4) + b] + 22b + 2b + b = 24 T(n – 4) + 23 b + 22b  
+ 21b + 20b  
= ……  
= 2k T(n – k) + b[2k- 1 + 2k– 2 + . . . 21 + 20]  
Khi n = k-1 ta có  
Khử đệ qui  
– Một hàm đệ qui có thể được giải quyết tương  
đương bằng việc sử dụng vòng lặp và stack  
Đố Bích Diệp- Khoa CNTT-ĐHBKHN  
15  
Cấu trúc dữ liệu và giải thuật  
Khử đệ qui  
Algorithm P (val n <integer>)  
1 if (n = 0)  
1
print ("Stop")  
2 else  
1
2
3
Q(n)  
P(n - 1)  
R(n)  
End P  
Khử đệ qui  
Algorithm P (n)  
Algorithm P (n)  
1 if (n = 0)  
1 createStack (s)  
2 loop (n > 0)  
1 Q(n)  
1
print ("Stop")  
2 else  
1
2
3
Q(n)  
P(n - 1)  
R(n)  
2 push(s, n)  
3 n = n - 1  
print ("Stop")  
3
4
End P  
loop (not emptyStack (s))  
1 popStack(s, n)  
2 R(n)  
End P  
Đố Bích Diệp- Khoa CNTT-ĐHBKHN  
16  
Cấu trúc dữ liệu và giải thuật  
Khử đệ qui  
Algorithm P (n)  
1 if (n = 0)  
1
2 else  
1
print("Stop")  
Q(n)  
2
P(n - 1)  
End P  
Khử đệ qui  
Algorithm P (n)  
Algorithm P (n)  
1 if (n = 0)  
1 loop (n > 0)  
1 Q(n)  
1
print("Stop")  
2
else  
1
Q(n)  
P(n - 1)  
2 n = n - 1  
2 print("Stop")  
2
End P  
End P  
Đố Bích Diệp- Khoa CNTT-ĐHBKHN  
17  
Cấu trúc dữ liệu và giải thuật  
Đệ qui có nhớ  
z Một kỹ thuật sử dụng khi trong các bài toán đệ qui có  
việc lặp đi lặp lại lời gọi một bài toán con nào đó  
z Làm tăng tính hiệu quả của giải thuật đệ qui  
Fibonacci(6)  
Fibonacci(5)  
Fibonacci(4) Fibonacci(3)  
Fibonacci(3) Fibonacci(2) Fibonacci(2)  
Fibonacci(1)  
Fionacci(4)  
Fibonacci(3) Fibonacci(2)  
Fibonacci(2)  
Fibonacci(1)  
Fibonacci(2)  
Fibonacci(1)  
Đệ qui có nhớ  
– Ý tưởng khắc phục:  
z Ghi lại lời giải của các bài toán con sử dụng một biến  
trong giải thuật  
z Ví dụ: Bài toán tính hệ số nhị thức  
C(n,0) =1 (n ≥ 0)  
C(n,n) =1 (n ≥ 0)  
C(n,k) = C(n −1,k −1) + C(n −1,k) 0 < k < n  
Đố Bích Diệp- Khoa CNTT-ĐHBKHN  
18  
Cấu trúc dữ liệu và giải thuật  
Đệ qui có nhớ  
z Hàm đệ qui của bài toán  
Function C(n,k)  
Begin  
if ( k == 0) || (k ==n) then return 1;  
else return C(n-1,k-1) + C( n-1,k);  
End  
z Hàm đệ qui có nhớ  
Function C(n,k)  
Begin  
if D[n,k] > 0 then return D[n,k];  
else D[n,k] = C(n-1,k-1) + C( n-1,k);  
return D[n,k];  
End  
Đố Bích Diệp- Khoa CNTT-ĐHBKHN  
19  
pdf 19 trang baolam 24040 Free
Download
Bạn đang xem tài liệu "Bài giảng Cấu trúc dữ liệu và Giải thuật - Chương II: Giải thuật đệ qui - Đỗ Bích Diệp", để 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_giai_thuat_chuong_ii_giai_thua.pdf