Xem mẫu
- om
.c
ng
co
Kỹ thuật đệ quy
an
th
o ng
du
u
cu
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- om
.c
ng
co
Nhắc lại kỹ thuật Đệ quy
an
Recursive
th
o ng
du
u
cu
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- Mô tả đệ quy
Recursive
om
.c
ng
co
Mô tả theo cách phân tích
an
đối tượng thành nhiều
th
thành phần mà trong số
ng
các thành phần có thành
o
phần mang tính chất của
du
chính đối tượng được mô
u
cu
tả
Mô tả đối tượng
thông qua chính nó
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- Ví dụ Mô tả đệ quy tập số tự nhiên N
Số 1 là số tự nhiên (1-N).
Số tự nhiên bằng số tự nhiên cộng 1.
om
Mô tả đệ quy cấu trúc danh sách kiểu T
.c
Cấu trúc rỗng là một danh sách kiểu T.
ng
Ghép nối một thành phần kiểu T (nút kiểu
co
T) với một danh sách kiểu T ta có một
an
danh sách kiểu T.
th
ng
Mô tả đệ quy cây gia phả
o
du
Gia phả của một người bao gồm người đó
và gia phả của cha và gia phả của mẹ
u
cu
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- Ví dụ Tính giai thừa của n
Định nghĩa không đệ quy n!
om
n! = n * (n-1) * … * 1
.c
Định nghĩa đệ quy:
n! = 1 nếu n=0
ng
n * (n-1)! nếu n>0
co
an
Mã C++
th
ng
int factorial(int n) {
if (n==0) return 1;
o
du
else
u
return (n * factorial(n - 1));
cu
}
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- Thực hiện tính
giai thừa
om
.c
factorial (3)
ng
n=3
co
… factorial (2)
an
n=2
th
3*factorial(2) … factorial (1)
ng
6
o
n=1
du
2*factorial(1)
2 … factorial (0)
u
cu
1*factorial(0) n=0
1 …
return 1;
1
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- Trạng thái hệ thống
khi tính giai thừa
om
.c
Stack hệ thống
ng
co
factorial(0)
an
factorial(1) factorial(1) factorial(1)
th
factorial(2) factorial(2) factorial(2) factorial(2) factorial(2)
ng
factorial(3) factorial(3) factorial(3) factorial(3) factorial(3) factorial(3) factorial(3)
o
t
du
u
Thời gian hệ thống
cu
Trả về từ Trả về từ Trả về từ Trả về từ
Gọi hàm Gọi hàm Gọi hàm Gọi hàm hàm hàm hàm hàm
factorial(3) factorial(2) factorial(1) factorial(0) factorial(0 factorial(1 factorial(2 factorial(3
) ) ) )
t
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- Thành phần của
mô tả đệ quy
om
.c
▪ Phần neo: trường hợp suy biến của đối tượng
ng
▫ Ví dụ: 1 là số tự nhiên, cấu trúc rỗng là danh sách kiểu T, 0!=1,
co
SM (a[x:x]) là thao tác rỗng.
an
▪ Phần qui nạp: mô tả đối tượng (giải thuật) thông qua chính
th
đối tượng (giải thuật) đó một cách trực tiếp hoặc gián tiếp.
ng
Ví dụ:
o
du
▫ n! = n * (n –1)!
▫ SM (a[m:n]) ≡Merge (SM (a[m:( m+n) div 2] , SM (a[(m+n) div 2
u
cu
+1 : n]) )
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- Phân loại
đệ quy
om
.c
Đệ quy trực tiếp Đệ quy gián tiếp
ng
co
▸Đệ quy tuyến tính ▸Đệ quy hỗ tương
an
▸Đê qui nhị phân
▸Đệ quy phi tuyến
th
o ng
du
u
cu
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- KieuDuLieu TenHam(Thamso)
{
if(Dieu Kien Dung)
{
Đệ quy ...;
return Gia tri tra ve;
tuyến tính }
om
...;
TenHam(Thamso)
.c
...;
▪ Là đệ quy có dạng }
ng
P( ) {
co
If (B) thực hiện S;
an
else { thực hiện S* ; gọi P }
}
th
Với S , S* là các thao tác không đệ quy.
o ng
▪ VD: Hàm FAC(n) tính số hạng n của dãy n!
du
int FAC( int n )
u
cu
{
if ( n == 0 ) return 1 ;
else return ( n * FAC(n-1 )) ;
}
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- Ví dụ Tính
S(n) = 1/(1*2) + 1/(2*3) + ... + 1/( n*(n+1) )
om
S(n) = 1/2 khi n==1
= S(n-1)+1/(n*(n+1))
.c
ng
float S(int n) {
co
if ( n==1) return 0.5;
an
else return S(n-1)+1.0/(n*(n+1));
th
}ng
o
du
u
cu
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- KieuDuLieu TenHam(Thamso)
{
if(Dieu Kien Dung)
{
Đệ quy ...;
return Gia tri tra ve;
nhị phân }
om
...;
TenHam(Thamso);
.c
...;
▪ Là đệ quy có dạng TenHam(Thamso);
ng
P ( ) { ...;
co
If (B) thực hiện S; }
else {
an
thực hiện S*;
th
gọi P ; gọi P;
}
ng
}
o
Với S , S* là các thao tác không đệ quy.
du
▪ Ví dụ: Hàm FIBO(n) tính số hạng n của dãy FIBONACCI
u
cu
int F(int n) {
if ( n < 2 ) return 1;
else
return (F(n -1) + F(n -2));
}
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- Ví dụ Tính tổng các giá trị của dãy số H(n), biết
H(n) = n khi n2
om
long H(int n) {
.c
if (n
- KieuDuLieu TenHam(Thamso)
{
if(Dieu Kien Dung)
{
Đệ quy ...;
return Gia tri tra ve;
phi tuyến }
om
...;
vonglap(dieu kien lap)
.c
{
...TenHam(Thamso)...;
ng
}
co
return Gia tri tra ve;
}
an
▪ Là đệ quy mà lời gọi đệ quy được thực hiện bên trong vòng
lặp. th
o ng
P ( ) {
du
for ( to ) {
u
thực hiện S ;
cu
if (điều kiện dừng) then thực hiện S*;
else gọi P;
}
}
Với S , S* là các thao tác không đệ quy.
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- Đệ quy
phi tuyến
om
.c
▪ Ví dụ: Cho dãy { An } xác định theo công thức truy hồi :
ng
A0= 1 ;
co
An = n2A0+(n-1)2A1+ . . . + 22An-2+ 12An-1
an
th
int A( int n ) { ng
if (n==0) return 1 ;
else {
o
du
int tg = 0 ;
for (int i=0; i
- KieuDuLieu TenHamX(Thamso)
{
if(Dieu Kien Dung)
{
Đệ quy ...;
return Gia tri tra ve;
tương hỗ }
om
...;
return TenHamX(Thamso) TenHamY(Thamso);
▪ Là một loại đệ quy gián }
ng
tiếp
co
KieuDuLieu TenHamY(Thamso)
▪ Trong đệ quy tương hỗ {
an
if(Dieu Kien Dung)
có 2 hàm, và trong thân
th
{
của hàm này có lời gọi ...;
ng
return Gia tri tra ve;
của hàm kia, điều kiện
o
}
du
dừng và giá tri trả về ...;
return TenHamY(Thamso)TenHamX(Thamso);
cu
giống nhau hoặc khác }
nhau
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- X(n) = 1,2,3,5,11,41……
Ví dụ Y(n) = 1,1,2,6,30,330 …..
void main() {
int n;
om
printf("\n Nhap n = ");
scanf("%d",&n);
.c
printf( "\n X = %d " ,X(n));
ng
printf( "\n Y = %d " , Y(n));
getch();
co
}
an
long Y(int n); //prototype cua ham y
th
long X(int n) {
if(n==0)
ng
return 1;
o
else
du
return X(n-1) + Y(n-1);
}
u
cu
long Y(int n) {
if(n==0)
return 1;
else
return X(n-1)*Y(n-1);
CuuDuongThanCong.com
} https://fb.com/tailieudientucntt
- Tìm giải thuật
đệ quy
om
.c
1. Thông số hóa bài toán .
ng
▫ Tổng quát hóa bài toán cụ thể cần giải thành bài toán tổng
co
quát (một họ các bài toán chứa bài toán cần giải )
an
▫ Tìm ra các thông số cho bài toán tổng quát
th
▸ các thông số điều khiển: các thông số mà độ lớn của chúng đặc
ng
trưng cho độ phức tạp của bài toán , và giảm đi qua mỗi lần gọi đệ
o
quy.
du
▸ Vídụ
u
▸ n trong hàm FAC(n) ;
cu
▸ a , b trong hàm USCLN(a,b) .
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- Tìm giải thuật
đệ quy
om
.c
2. Tìm các trường hợp neo cùng giải thuật giải tương ứng
ng
▫ trường hợp suy biến của bài toán tổng quát
co
▫ các trường hợp tương ứng với các gía trị biên của các biến điều
an
khiển
th
▫ VD: FAC(1) =1
ng
USCLN(a,0) = a
o
3. Tìm giải thuật giải trong trường hợp tổng quát bằng phân
du
rã bài toán theo kiểu đệ quy
u
cu
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- Tìm giải thuật
đệ quy
om
.c
▪ Phân rã bài toán tổng quát theo phương thức đệ quy
ng
▫ Tìm phương án (giải thuật ) giải bài toán trong trường hợp
co
tổng quát phân chia nó thành các thành phần
an
▸ giải thuật không đệ quy
th
▸ bài toán trên nhưng có kích thước nhỏ hơn.
ng
▫ Vídụ
o
FAC(n) = n * FAC(n -1) .
du
Tmax(a[1:n]) = max(Tmax(a[1:(n-1)]) , a[n] )
u
cu
CuuDuongThanCong.com https://fb.com/tailieudientucntt
nguon tai.lieu . vn
