Bài giảng Kỹ thuật lập trình - Bài 6: Đệ quy, các giải thuật đệ quy - Lê Gia Minh

Nội dung text: Bài giảng Kỹ thuật lập trình - Bài 6: Đệ quy, các giải thuật đệ quy - Lê Gia Minh

1. Đệ quy – Các giải thuật đệ quy
2. Nội dung l Đệ quy là gì ? l Viết hàm đệ quy l Phân lọai đệ quy l Khử đệ quy l Kết luận
3. Đệ Quy là gì ? l Định nghĩa tường minh: Giải thích khái niệm mới bằng những khái niệm đã có. l Người = Động vật cấp cao. l Định nghĩa khác: Giải thích 1 khái niệm bằng chính khái niệm đó. l Đệ quy: Đưa ra 1 định nghĩa có sử dụng chính khái niệm đang cần định nghĩa( quay về ). l Người = con của hai người khác.
4. Kiểu dữ liệu đệ quy l Một người được mô tả bằng: tên, năm sinh, cha (một người khác), mẹ (một người khác). struct NGUOI { char Ten[51]; int namsinh; Cấu trúc này không NGUOI cha; khả thi trong máy tính vì không thể NGUOI me; cấp bộ nhớ };
5. Kiểu dữ liệu đệ quy l Sửa lại: struct NGUOI { char Ten[51]; pMe (4 bytes) int namsinh; pCha (4 bytes) NGUOI* pCha; namsinh (2 bytes) Ten (51 bytes) NGUOI* pMe; x }; NGUOI x;
6. Tác vụ đệ quy l Có thể diễn đạt nhiều tác vụ hướng đệ quy. l 1+2+3+ + (n-2) + (n-1) + n l Sum( N) = N + Sum(N-1) l Điều kiện biên là điều kiện ngưng không đệ quy nữa. l Điều kiện biên: Sum (1 ) = 1
7. Cách viết hàm đệ quy l Định nghĩa tác vụ đệ quy theo ngôn ngữ tự nhiên thế nào thì hàm cũng viết như thế. l Thí dụ: n! = 1*2*3*4*5* * n n! = 1, n<=1 n* (n-1)!
8. Cách viết hàm đệ quy 2 dòng Điều kiện biên n! = 1, n<=1 n* (n-1)! 2 dòng
9. Phân loại hàm đệ quy l Tùy thuộc cách diễn đạt tác vụ đệ quy mà có các loại đệ quy sau. (1) Đệ quy tuyến tính. (2) Đệ quy nhị phân. (3) Đệ quy phi tuyến (4) Đệ quy hỗ tương.
10. Đệ quy tuyến tính l if ( dk dừng ) return giá trị hay kết thúc hàm l else l /* Làm 1 số công việc */ l Gọi đệ quy
11. Đệ quy tuyến tính l Thân hàm gọi 1 lần chính nó l Un = a , n=1 ( trị thứ n của cấp số cộng) r + Un-1 , n>1 double U (int n, double a, double r) { if (n==1) return a; return r + U(n-1,a,r); }
12. Đệ quy đầu l Sau lệnh gọi đệ quy phía sau vẩn còn lệnh void DequyDau(int A[],int n) { if (n>1) DequyDau(A,n-1); printf(“%d “ , A[n-1]); }
13. Đệ quy đuôi l Lệnh gọi đệ quy là lệnh sau cùng l void DequyDuoi(int A[],int n) l { l if (!n) return; l else l { l printf(“%d “ , A[n-1]); l DequyDuoi(A,n-1); l } l }
14. Bài tập l Viết hàm đệ quy tính chiều dài một chuỗi l Viết hàm đệ quy tìm giá trị lớn nhất có trong mãng A có n phần tử l In dang nhi phan cua so nguyen n
15. Giải l int mystrlen( char* s ) l { l return ( !*s ? 0 : 1 + mystrlen(++s) ); l }
16. Tìm trị lớn nhất của mảng a, n phần tử l Thông số hóa: int*a, int n l Điều kiện biên: Mảng 1 phần tử thì trị lớn nhất là a[0]. l Giải thuật chung: Max(a,n) = a[0] a[1] a[2] a[n-2] +a[n-1] Max(a,n-1) Max (a,n) = a[0] , n=1 a[n-1] > Max(a, n-1)? a[n-1] : Max(a,n-1) l Thuật toán đệ quy tìm trị nhỏ nhất của mảng? Do yourself.
17. Trung binh cong cac so <0 trong mang
18. De quy nhi phan if ( dk dừng ) return giá trị hay kết thúc hàm else { /* Làm 1 số công việc */ Gọi đệ quy (1) giải bài toán nhỏ hơn Gọi đệ quy (2) giải bài toán nhỏ hơn }
19. Đệ quy nhị phân l Thân hàm gọi 2 lần chính nó. l Chuỗi số Fibonacci: 1 1 2 3 5 8 13 l Un = 1, n=1,2 Un-2 + Un-1 , n>2 long Fibo (int n) { if (n<=2) return 1; return Fibo(n-2) + Fibo(n-1); }
20. Bài tập l Viết lại hàm tìm giá trị lớn nhất bằng đệ quy nhị phân l Viết lại hàm tính xn bằng đệ quy nhị phân
21. Giải l int max(int a[] , int n ) l { l if ( n ==1 ) return a[0] ; l int n1 , n2 ; l double m1 , m2 ; l n1 = n/2 ; n2 = n-n1; l m1 = max(a,n1); l m2 = max(a+n1, n2); l return ( m1 > m2 ? m1 : m2 ); l }
22. Đệ quy phi tuyến l Thân hàm lặp gọi 1 số lần chính nó l Un = n , n 6 long U ( int n) { if (n 0; i ) S+= U(n-i); return S; }
23. Bài toán Tháp Hà Nội A B C
24. Hanoi Tower l void HaNoi(int source,int dest,int n) l { l int trunggian ; l if (n == 1 ) l printf("Chuyen dia tu coc %d sang coc %d\n” , source,dest); l else l { l trunggian = 6 - (source + dest ); l HaNoi(source,trunggian,n-1); l HaNoi(source,dest,1); l HaNoi(trunggian,dest,n-1); l } l }
25. Tháp Hà Nội 1 2 3 3 2 1 1 2 3 2 1 3 A B C
26. Nhận xét về hàm đệ quy HÀM ĐỆ QUY: Vừa tốn bộ nhớ vừa chạy chậm Giải thuật đệ quy đẹp (gọn gàng, dễ chuyển thành chương trình. Nhiều ngôn ngữ không hỗ trợ giải thuật đệ quy (Fortran). Nhiều giải thuật rất dễ mô tả dạng đệ quy nhưng lại rất khó mô tả với giải thuật không-đệ-quy.
27. Khử đệ quy l Là quá trình chuyển đổi 1 giải thuật đệ quy thành giải thuật không đệ quy. l Chưa có giải pháp cho việc chuyển đổi này một cách tổng quát. l Cách tiếp cận: (1) Dùng vòng lặp. (2) Dùng Stack.
28. Thí dụ: Hàm tính giai thừa của n long GiaiThua( int n) Trị cần lưu { if (n<2) return 1; return n * GiaiThua(n-1); } Điều kiện biên long GiaiThua( int n) K chính là kết qủa của trị { long K=1; giai thừa trước đó for (int i =2; i<=n;i++) K=K*i; return K; }
29. Thí dụ hàm tính trị thứ n của dãy Fibonacci: long Fibo(int n) 1 1 2 3 5 8 { if (n<=2) return 1; // hai chặn return Fibo(n-2) + Fibo (n-1); t t t3=t1+t } 1 2 2 long Fibo(int n) t1 t2 t3 { if (n<=2) return 1; // hai chặn long t1=1, t2=1; t1 t2 t3 for (int i=3; i<=n;i++) t1 t2 t3 { t3=t1+t2; t1=t2; i = 3 4 5 6 t2= t3; } return t3; }
30. In dạng nhị phân của 1 số nguyên N Dùng Stack typedef struct STACK { int top ; // dinh stack int *Arr ; }
31. Kết luận l Hàm đệ quy là hàm mà trong thân hàm lại gọi chính nó. l Hàm đệ quy kém hiệu quả vì: tốn bộ nhớ va gọi hàm qúa nhiều lần. Tuy nhiên viết hàm đệ quy rất ngắn gọn. l Vòng lặp và stack là những kỹ thuật giúp khử giải thuật đệ quy.