Chương 2: Đệ qui và giải thuật đệ qui
Khái niệm đệ qui
Giải thuật đệ qui và chương trình đệ qui
Các bài toán đệ qui căn bản
36 trang |
Chia sẻ: phuongt97 | Lượt xem: 483 | Lượt tải: 0
Bạn đang xem trước 20 trang nội dung tài liệu Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 2: Đệ qui và giải thuật đệ qui - Ngô Quang Thạch, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
CẤU TRÚC DỮ LIỆU VÀ
GIẢI THUẬT
NGÔ QUANG THẠCH
Email: thachnq@gmail.com
ĐT: 01273984123
Chương 2: Đệ qui và giải thuật đệ qui
Khái niệm đệ qui
Giải thuật đệ qui và chương trình đệ qui
Các bài toán đệ qui căn bản
Khái niệm đệ qui
Ta nói một đối tượng là đệ quy nếu nó được định nghĩa
qua chính nó hoặc một đối tượng khác cùng dạng với
chính nó bằng quy nạp
Ví dụ: Đặt hai chiếc gương cầu đối diện nhau.
Trong chiếc gương 1 chứa hình chiếc gương 2. Chiếc gương 2
lại chứa hình chiếc gương 1 nên tất nhiên nó chứa lại hình ảnh
của chính nó trong chiếc gương 1 Ở một góc nhìn hợp lý, ta
có thể thấy một dãy ảnh vô hạn của cả hai chiếc gương
Ví dụ:
Định nghĩa số tự nhiên
0 là số tự nhiên bé nhất.
Nếu k là số tự nhiên thì k + 1 cũng là số tự nhiên
Như vậy, số tự nhiên bắt đầu từ 0, ta có các số tự nhiên
là: 0 + 1 = 1, 1 + 1 = 2,
Chuỗi ký tự
Chuỗi rỗng là một chuỗi ký tự.
Một chuỗi ký tự ghép với một ký tự bất kỳ là một chuỗi
ký tự.
Quá trình đệ qui
Quá trình đệ qui gồm 2 phần:
. Trường hợp cơ sở (base case)
. Trường hợp đệ qui: cố gắng tiến về trường hợp cơ sở
Ví dụ:
Hàm giai thừa: n!
a) 0!=1
b) Nếu n>0 thì n! = n*(n -1)!
Ví dụ:
Ước chung lớn nhất của hai số nguyên không âm m, n
(với m >n) như sau:
Nếu n = 0 thì UCLN(m, n) = m
Nếu n ≠ 0 thì UCLN(m, n) = UCLN(n, m % n)
Hàm đệ qui
Trong lập trình, một hàm được gọi trong chính hàm đó
thì được gọi là đệ qui.
Hàm()
{
Lời gọi Hàm()
}
Giải thuật đệ qui
Hai bước giải bài toán đệ qui
Bước 1: Phân tích bài toán thành bài toán đồng dạng
nhưng đơn giản hơn và dừng lại ở bài toán đồng dạng
đơn giản nhất có thể xác định ngay kết quả.
Bước 2: Xác định kết quả bài toán đồng dạng từ đơn
giản đến phức tạp để có kết quả cuối cùng.
Mục đích để giải quyết 1 vấn đề tương tự, nhưng nhỏ hơn.
Vấn đề nhỏ hơn này, cho tới 1 lúc nào đó sẽ đơn giản tới
mức chương trình có thể tự giải quyết được mà không cần
gọi tới chính nó nữa.
Hàm đệ qui
Cấu trúc hàm đệ qui
()
{
if ()
{
return ;
}
... Gọi lại hàm với tham số bé hơn
...
}
Hàm đệ qui
Viết hàm tính n!, với n 0 Đệ qui: N!=N*GiaiThua(N-1)
long GiaiThua(int n) GT=4*giaithua(3)
{ if(n == 0) =4*(3*giaithua(2))
return 1; =4*(3*(2*giaithua(1)))
=4*(3*(2*(1*giaithua(0))))
return n*GiaiThua(n – 1);
=4*(3*(2*(1*1)))
}
=4*(3*(2*1))
=4*(3*2)
=4*6
=24
Giải thuật đệ qui và chương trình đệ qui
#include
long int gthua(int n);
void main(void)
{
int n;
scanf(“%d”,&n);
printf(“Giai thừa của%d là: %d”,n,gthua(n));
}
int long gthua(int n)
{
if(n==0)
return 1;
else
return(n*gthua(n-1));
}
Phân loại đệ qui
Đệ qui tuyến tính
Đệ qui nhị phân
Đệ qui hỗ tương
Đệ qui phi tuyến
Phân loại đệ qui
Đệ qui tuyến tính
Tính S(n) = 1 + 2 + + n
S(n) = S(n – 1) + n
Điều kiện dừng: S(0) = 0
long Tong(int n)
{
if (n == 0)
return 0;
return Tong(n–1) + n;
}
Phân loại đệ qui
Đệ qui nhị phân
Trong thân hàm có hai lời gọi hàm gọi lại chính nó một
cách tường minh.
()
{
if ()
{
return ;
}
();
();
}
Phân loại đệ qui
Đệ qui nhị phân
Tính số hạng thứ n của dãy Fibonacy
f(0) = f(1) = 1 và f(n) = f(n – 1) + f(n – 2) n > 1
Điều kiện dừng: f(0) = 1 và f(1) = 1
long Fibo(int n)
{
if (n == 0 || n == 1)
return 1;
return Fibo(n–1) + Fibo(n–2);
}
Phân loại đệ qui
Đệ qui hỗ tương
Trong thân hàm này có lời gọi hàm tới hàm kia và ngược lại
()
{ if ()
{
return ;
}
();
}
()
{ if ()
{
return ;
}
();
}
Phân loại đệ qui
Đệ qui hỗ tương
Tính số hạng thứ n của dãy sau:
x(0) = 1, y(0) = 0
x(n) = x(n – 1) + y(n – 1)
y(n) = 3*x(n – 1) + 2*y(n – 1)
Điều kiện dừng: x(0) = 1, y(0) = 0
long xn(int n)
{ if (n == 0) return 1;
return xn(n-1) + yn(n-1);
}
long yn(int n)
{
if (n == 0) return 0;
return 3*xn(n-1) + 2*yn(n-1);
}
Phân loại đệ qui
Đệ qui phi tuyến
Trong thân hàm có lời gọi hàm lại chính nó được đặt bên
trong thân vòng lặp.
()
{
if ()
{
return ;
}
Vòng lặp
{
();
}
}
Phân loại đệ qui
Đệ qui phi tuyến
Tính số hạng thứ n của dãy:
x(0) = 1
x(n) = n2x(0) + (n-1)2x(1) + + 22x(n – 2) + 12x(n – 1)
Điều kiện dừng: x(0) = 1
long xn(int n)
{
if (n == 0)
return 1;
long s = 0;
for (int i=1; i<=n; i++)
s = s + i*i*xn(n–i);
return s;
}
Các bước xây dựng hàm đệ quy
Bước 1: Thông số hóa bài toán.
Tổng quát hóa bài toán cụ thể thành bài toán tổng quát.
Thông số hóa bài toán tổng quát.
Ví dụ: n trong hàm tính tổng S(n) = 1 + 2 + 3 + + n
Bước 2: Tìm thuật giải tổng quát.
Phần không đệ quy.
Phần như bài toán trên nhưng kích thước nhỏ hơn.
Ví dụ: S(n) = S(n – 1) + n
Bước 3: Tìm các trường hợp suy biến.
Các trường hợp suy biến của bài toán.
Kích thước bài toán trong trường hợp này là nhỏ nhất.
Ví dụ: S(0) = 0
Một số lỗi thường gặp
Công thức đệ qui chưa đúng, không tìm được bài toán
đồng dạng đơn giản hơn
Không xác định các trường hợp suy biến – neo (điều kiện
dừng).
Thông điệp thường gặp là StackOverflow do:
. Thuật giải đệ quy đúng nhưng số lần gọi đệ quy quá lớn làm
tràn STACK.
. Thuật giải đệ quy sai do không hội tụ hoặc không có điều kiện
dừng.
Các vấn đề đệ quy thường gặp
Truy hồi
Hệ thức truy hồi của 1 dãy An là công thức biểu diễn phần tử An
thông qua 1 hoặc nhiều số hạng trước của dãy.
Gửi ngân hàng 1000 USD, lãi suất 12%/năm. Tính số tiền có được
sau 30 năm. Gọi An là số tiền có được sau n năm.
Ta có:
An = A(n – 1) + 0.12*A(n – 1) = 1.12*A(n – 1)
A(0) = 1000
Đệ quy tuyến tính với A(n)=1.12*A(n – 1) và điều kiện dừng A(0)
= 1000
Các vấn đề đệ qui thường gặp
Chia để trị
// Tìm nghiệm x của bài toán A.
void DivideConquer(A, x)
{
if (A đủ nhỏ) Solve(A);
else
{ Phân A thành các bài toán con A1, A2, , Am
for ( i = 1; i <= n; i++) DivideConquer(Ai, xi);
Kết hợp các nghiệm xi của Ai để nhận được x của A.
}
}
Các vấn đề đệ quy thường gặp
Phương pháp quay lui
. Tại bước có nhiều lựa chọn, ta chọn thử 1 bước để đi tiếp.
. Nếu không thành công thì “lần ngược” chọn bước khác.
. Nếu đã thành công thì ghi nhận lời giải này đồng thời “lần
ngược” để truy tìm lời giải mới.
. Thích hợp giải các bài toán kinh điển như bài toán 8 hậu và bài
toán mã đi tuần.
Các bài toán đệ qui căn bản
Bài toán tháp Hà Nội
Có 3 cọc a, b, c. Trên cọc a có n đĩa xếp chồng lên nhau
sao cho đĩa nhỏ trên đĩa lớn.
Cần chuyển chồng đĩa từ cọc a sang cọc c tuân thủ
quy tắc: Mỗi lần chỉ chuyển được một đĩa, luôn đảm bảo
đĩa nhỏ trên đĩa lớn, có thể sử dụng cọc b làm trung
gian.
Bài toán tháp Hà Nội
Phương pháp di chuyển đĩa như sau:
Chuyển n – 1 đĩa từ cọc a sang cọc b sử dụng cọc c làm
trung gian.
Chuyển đĩa lớn nhất từ cọc a sang cọc c.
Chuyển n – 1 đĩa từ cọc b sang cọc c sử dụng cọc a
làm trung gian.
Bài toán tháp Hà Nội
Giải thuật đệ qui:
void HaNoi(int n, char A, char B, char C){
If (n==1)
printf(“Di chuyển đĩa %d từ %c sang %c”,n,A,C);
Else{
HaNoi(n -1, A, C, B); {I}
HaNoi(1, A, B, C); {II}
HaNoi(n -1, B, A, C); {III}
}
}
Tháp Hà Nội với N=3
1
2
3
A B c
Trạng thái di chuyển Tháp Hà Nội với N=3
1
2
3
A B c
Bài tập tháp Hà Nội với N=4
1
2
3
4
A B c
Trạng thái di chuyển Tháp Hà Nội với N=4
1
2
3
4
A B c
Trạng thái di chuyển Tháp Hà Nội với N=4
1
2
4 3
A B c
So sánh đệ qui với các giải thuật khác
So sánh cách tính N!
Với N=4, Tính 4!
Đệ qui: N!=N*giaithua(N-1) Phương pháp lặp:
GT=4*giaithua(3) N!=N*(N-1)2*1
=4*(3*giaithua(2)) Bước lặp 1 GT=4
=4*(3*(2*giaithua(1))) Bước lặp 2 =4*3=12
=4*(3*(2*(1*giaithua(0)))) Bước lặp 3 =12*2=24
=4*(3*(2*(1*1))) Bước lặp 4 =24*1=24
=4*(3*(2*1))
=4*(3*2)
=4*6
=24
Tổng kết
Chỉ nên dùng phương pháp đệ qui để giải các bài toán
kinh điển như giải các vấn đề “chia để trị”, “lần ngược”.
Vấn đề đệ qui không nhất thiết phải giải bằng phương
pháp đệ qui, có thể sử dụng phương pháp khác thay thế
(khử đệ qui)
Phương pháp đệ qui tiện cho người lập trình nhưng không
tối ưu khi chạy trên máy.
Bước đầu nên giải bằng đệ qui nhưng từng bước khử đệ
qui để nâng cao hiệu quả.
34
Bài tập 1
Cho một mảng a có n phần tử, viết hàm đệ qui để tìm
giá trị lớn nhất (nhỏ nhất) trong mảng a đó:
Gợi ý chung
Điều kiện biên: Mảng 1 phần tử thì giá trị lớn nhất là a[0]
Giải thuật chung:
n=1 Max(a,n)=a[0];
n>1 Nếu a[n-1]>Max(a,n-1) thì giá trị lớn nhất là a[n-1]
Ngược lại thì giá trị lớn nhất là Max(a,n-1)
Bài tập 2
1. Cho một mảng a có n phần tử, viết hàm đệ qui để tính
tổng giá trị các phần tử trong mảng a đó.
2. Cho một mảng a có n phần tử, viết hàm đệ qui để tính
tổng giá trị các phần tử LẺ/CHẴN trong mảng a đó.
Các file đính kèm theo tài liệu này:
- bai_giang_cau_truc_du_lieu_va_giai_thuat_chuong_2_de_qui_va.pdf