Bài giảng Kỹ thuật lập trình – Chương 6: Kỹ thuật đệ quy

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:50

Thêm vào BST

Báo xấu

26
lượt xem 6
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Kỹ thuật lập trình – Chương 6: Kỹ thuật đệ quy. Chương này gồm có những nội dung chính sau: Mô tả đệ quy, thực hiện tính giai thừa, trạng thái hệ thống khi tính giai thừa, thành phần của mô tả đệ quy, phân loại đệ quy, đệ quy nhị phân, đệ quy phi tuyến, đệ quy tương hỗ,… Mời các bạn cùng tham khảo.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Kỹ thuật lập trình – Chương 6: Kỹ thuật đệ quy

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