Bài giảng Lập trình C - Chương 5: Lập trình đệ quy - Trần Minh Thái

Nội dung text: Bài giảng Lập trình C - Chương 5: Lập trình đệ quy - Trần Minh Thái

1. Lập trình C Chương 5. Lập trình đệ quy (3 tiết) Trần Minh Thái Email: minhthai@huflit.edu.vn Website: www.minhthai.edu.vn Cập nhật: 20/03/2017
2. Nội dung • Giới thiệu về lập trình đệ quy • Xây dựng giải thuật đệ quy • Phân loại các dạng đệ quy • Hoạt động của đệ quy • Các giải pháp thay thế cho đệ quy • Bài tập 2
3. GIỚI THIỆU VỀ LẬP TRÌNH ĐỆ QUY
4. Giới thiệu về lập trình đệ quy • Khi lập trình, gặp dạng bài toán: đối tượng khó định nghĩa một cách tường minh • Kỹ thuật định nghĩa đối tượng qua chính nó: kỹ thuật đệ quy (recursion) • Định nghĩa theo đệ quy của một khái niệm là định nghĩa khái niệm mới thông qua chính khái niệm đang muốn định nghĩa 4
5. Giới thiệu về lập trình đệ quy Ví dụ • Giai thừa của n (n!) • Nếu n=0 hoặc n=1 thì n!=1. • Nếu n>1 thì n!=(n-1)! * n • Tập số tự nhiên • Số 1 là số tự nhiên (1 N) • Số tự nhiên bằng số tự nhiên cộng 1 (n N (n+1) N) 5
6. Giới thiệu về lập trình đệ quy • Cấu trúc danh sách liên kết (linklist/xâu) kiểu T • Cấu trúc rỗng là danh sách liên kết kiểu T • Kết nối một thành phần kiểu T (nút kiểu T) vào một danh sách liên kết kiểu T, ta có một danh sách liên kết kiểu T 6
7. Giới thiệu về lập trình đệ quy → Để định nghĩa đệ quy gồm 2 phần: 1. Phần cố định (cơ sở - neo – anchor): các trường hợp suy biến của thuật toán qua một điều kiện cụ thể (phần dừng của đệ quy) 2. Phần đệ quy (quy nạp): mô tả thuật toán trong trường hợp phổ biến qua chính đối tượng (gọi hàm đệ quy) một cách gián tiếp hay trực tiếp !!! Phần đệ quy phải tiến về phần không đệ quy 7
8. Xây dựng giải thuật đệ quy • Bước 1: Thông số hóa bài toán • Bước 2: Phát hiện các trường hợp suy biến và tìm giải thuật cho bài toán này • Bước 3: Phân rã bài toán theo hướng đệ quy 8
9. Bước 1: Thông số hóa bài toán • Tổng quát hóa bài toán, tìm ra nhóm các bài toán, các thông số kích thước, thông số điều khiển. • Ví dụ: thông số n trong hàm tính giai thừa, trong hàm Fibonaci, thông số a, b trong hàm tìm ước số chung lớn nhất 9
10. Bước 2: Phát hiện TH suy biến, tìm giải thuật Là các trường hợp tương ứng với giá trị biên của biến điều khiển (trường hợp kích thước nhỏ nhất, trường hợp đặc biệt) mà không cần đệ quy • Ví dụ: • GiaiThua(1) = 1 • USCLN(a, 0) = a • SUM(a[m:m]) = a[m] 10
11. Bước 3: Phân rã theo hướng đệ quy • Tìm giải thuật trong trường hợp tổng quát bằng cách phân rã thành các thành phần nhỏ hơn không đệ quy hoặc là bài toán đệ quy nhưng với kích thước nhỏ hơn 11
12. Phân loại đệ quy 1. Đệ quy tuyến tính 2. Đệ quy nhị phân 3. Đệ quy phi tuyến 4. Đệ quy hỗ tương 12
13. ĐỆ QUY TUYẾN TÍNH
14. Đệ quy tuyến tính Bước 1 Nếu thỏa điều kiện dừng thì thực hiện thao tác S (trả về kết quả) Bước 2 Ngược lại: Bước 2.1 thực hiện lệnh S* Bước 2.2 Gọi hàm đệ quy (cho đối tượng thường là nhỏ hơn) • S, S*: xử lý không đệ quy (Có thể gộp bước 2.1 và 2.2 lại) 14
15. Đệ quy tuyến tính Viết hàm tính giai thừa của số nguyên n bằng cách dùng vòng lặp int TinhGiaiThua(int n) { ??? } 15
16. Đệ quy tuyến tính Hàm tính giai thừa (TinhGiaiThuaDQ) bằng đệ quy Bước 1 Nếu n=0 hoặc n=1 thì trả về 1 Bước 2 Ngược lại: trả về n*TinhGiaiThuaDQ (n-1) 16
17. Đệ quy tuyến tính • Cài đặt: int TinhGiaiThuaDQ(int n) { if (n == 1 || n == 0) return 1; return n*TinhGiaiThuaDQ(n - 1); } 17
18. Hoạt động của đệ quy • Gồm 2 pha: • Pha tiến (forward): Tiến đến lời giải nhỏ nhất • Pha lùi (backward): Kết hợp các kết quả lại với nhau 18
19. Main( ) Gọi Giai thừa 5 n=5 kq=120 Giai Thừa ( 5 ) Gọi Giai thừa 4 n=4 kq=24 Giai Thừa ( 4 ) Gọi Giai thừa 3 n=3 kq=6 Giai Thừa ( 3 ) Gọi Giai thừa 2 n=2 kq=2 Giai Thừa ( 2 ) Gọi Giai thừa 1 n=1 kq=1 1! = 1
20. Đệ quy tuyến tính Viết hàm tìm ước số chung lớn nhất của 2 số nguyên dương m và n bằng cách sử dụng vòng lặp int USCLN (int m, int n) { ??? } 20
21. Đệ quy tuyến tính • Uớc số chung lớn nhất của 2 số dựa vào thuật toán Euclide: Bước 1: Nếu n=0 || m=0 thì trả về n+m Bước 2: Ngược lại: Nếu n>m thì n = n mod m Ngược lại thì m = m mod n trả về USCLN(n, m) 21
22. Đệ quy tuyến tính • Cài đặt: int USCLN(int m, int n) { if (n == 0|| m==0) return m+n; if(n>m) n%=m; else m%=n; return USCLN(n, m); } 22
23. Đệ quy tuyến tính Viết hàm xuất các phần tử lẻ trong mảng một chiều số nguyên bằng cách sử dụng vòng lặp void XuatLe (int []a, int n) { ??? } 23
24. Đệ quy tuyến tính • Xuất các giá trị lẻ của dãy số nguyên bằng đệ quy Bước 1: Nếu n=0 thì dừng Bước 2: Ngược lại: Bước 2.1 Nếu a[n-1] lẻ xuất a[n-1] Bước 2.2 gọi hàm LietKeLe(a, n-1) 24
25. Đệ quy tuyến tính • Cài đặt: void LietKeLe(int[] a, int n) { if (n == 0) return ; if (a[n - 1] % 2 != 0) printf(“%4d", a[n - 1]); LietKeLe(a, n - 1); } 25
26. Đệ quy tuyến tính • Kết quả xuất ra ngược với dãy ban đầu nhập vào • Xuất xuôi lại ta làm như sau: Bước 1: Nếu n=0 thì dừng Bước 2: Ngược lại: Bước 2.1 gọi hàm LietKeLe(a, n-1) Bước 2.2 Nếu a[n-1] lẻ xuất a[n-1] 26
27. Đệ quy tuyến tính • Cài đặt: void LietKeLe(int[] a, int n) { if (n == 0) return ; LietKeLe(a, n - 1); if (a[n - 1] % 2 != 0) printf(“%4d", a[n - 1]); } 27
28. Đệ quy tuyến tính • Đối với hàm đệ quy không có trị trả về (void), ta có thể viết theo dạng sau Bước 1: Nếu chưa dừng (n>0) thì: Bước 1.1 gọi hàm LietKeLe(a, n-1) Bước 1.2 Nếu a[n-1] lẻ xuất a[n-1] 28
29. Đệ quy tuyến tính • Cài đặt: void LietKeLe(int[] a, int n) { if (n > 0) { LietKeLe(a, n - 1); if (a[n - 1] % 2 != 0) printf(“%4d", a[n - 1]); } } 29
30. Đệ quy tuyến tính • Tính tổng giá trị của dãy số nguyên (TongDay) Bước 1: Nếu n=1 thì trả về a[0] Bước 2: Ngược lại: trả về a[n-1]+TongDay(a, n-1) 30
31. Đệ quy tuyến tính • Cài đặt: int TongDay(int []a, int n) { if (n == 1) return a[0]; return a[n-1] + TongDay(a, n-1); } 31
32. Bài tập Cho n là số nguyên dương, hãy viết hàm tính các tổng sau bằng phương pháp đệ quy: S(n) =12 + 22 + 32 ++ n2 1 1 1 S(n) = 1+ + ++ 2 3 n 32
33. Bài tập Cho mảng một chiều số nguyên a, kích thước n 1. Viết hàm tìm vị trí xuất hiện cuối cùng của phần tử có giá trị x (nếu có) bằng phương pháp đệ quy 2. Viết hàm tìm vị trí xuất hiện đầu tiên của phần tử có giá trị x (nếu có) bằng phương pháp đệ quy 33
34. ĐỆ QUY NHỊ PHÂN
35. Đệ quy nhị phân • Chương trình con gọi trực tiếp đến hàm đệ quy, thường sẽ có 2 lần gọi hàm đệ quy một cách tường minh với 2 nhánh rõ ràng 35
36. Đệ quy nhị phân Bước 1: Nếu thỏa điều kiện dừng thì thực hiện thao tác S (trả về kết quả) Bước 2: Ngược lại: Bước 2.1 thực hiện lệnh S* Bước 2.2 Gọi hàm đệ quy (đối tượng nhỏ hơn nhánh trái) lần thứ nhất Bước 2.3 Gọi hàm đệ quy (nhánh phải) lần thứ hai 36
37. Đệ quy nhị phân Viết hàm Fibonaci (n) để tính số hạng thứ n của dãy Fibonaci Bước 1 Nếu n<2 thì trả về 1 Bước 2 Ngược lại: trả về Fibonaci (n-1)+Fibonaci(n-2) 37
38. Đệ quy nhị phân • Cài đặt: int Fibonaci (int n) { if (n < 2) return 1; return Fibonaci(n - 1) + Fibonaci(n - 2); } 38
39. F4=F3+F2 F3=F2+F1 F2=F1+F0 F2=F1+F0 F1=1 F1=1 F0=1 F1=1 F0=1
40. kq=5 F4=F3+F2 kq=3 kq=2 F3=F2+F1 F2=F1+F0 kq=2 kq=1 kq=1 kq=1 F2=F1+F0 F1=1 F1=1 F0=1 kq=1 kq=1 F1=1 F0=1
41. Đệ quy nhị phân Tìm kiếm nhị phân trên dãy đã được sắp tăng Bước 1 Nếu left>right trả về -1 Bước 2 B2.1: Tính mid=(left+right)/2 B2.2: Nếu a[mid]=x thì trả về mid B2.3: Nếu a[mid]<x thì trả về TimNhiPhan(a,mid+1,right,x) B2.4: Ngược lại: trả về TimNhiPhan(a,left,mid-1,x) 41
42. Đệ quy nhị phân • Cài đặt: int TimNhiPhan(int []a,int left, int right,int x) { if (left > right) return -1; int mid = (left + right) / 2; if (a[mid] == x) return mid; if (a[mid] < x) return TimNhiPhan(a, mid + 1,right,x); return TimNhiPhan(a,left,mid-1,x); } 42
43. CÁC DẠNG ĐỆ QUY KHÁC
44. Đệ quy phi tuyến Đệ quy trực tiếp, gọi đệ quy trong vòng lặp Vòng lặp for từ giá trị đầu đến giá trị cuối B1.1: Thực hiện lệnh S B2.2: Nếu thỏa điều kiện dừng thì Thực hiện lệnh S* B2.3: Ngược lại: Gọi đệ quy 44
45. Đệ quy phi tuyến • Hoặc có dạng: B1: Nếu thỏa điều kiện dừng thì Thực hiện lệnh S B2: Ngược lại: B2.1 Thực hiện lệnh S* B2.2 Vòng lặp for từ giá trị đầu đến cuối Gọi đệ quy 45
46. Đệ quy phi tuyến • Ta có công thức truy hồi tính dãy {Xn} như sau: • X0 = 1. 2 2 2 2 • Xn = n X0 +(n-1) X1+ +2 Xn-2 +1 Xn-1 46
47. Đệ quy phi tuyến int TinhX(int n) { if (n == 0) return 1; else { int tong = 0; for (int i = 0; i < n; i++) tong += (n - i) * (n - i) * TinhX(i); return tong; } } 47
48. Đệ quy hỗ tương Trong thân hàm này có lời gọi hàm đến hàm kia và trong thân hàm kia có lời gọi hàm tới hàm này g() f() f() f() g() h() 48
49. Đệ quy hỗ tương Hàm thứ nhất Hàm thứ hai B1: Nếu thỏa đk dừng thì B1: Nếu thỏa đk dừng thì Thực hiện lệnh S* Thực hiện lệnh S* B2 Ngược lại: B2 Ngược lại: Thực hiện lệnh S Thực hiện lệnh S Gọi ĐQ hàm hai Gọi ĐQ hàm nhất 49
50. Đệ quy hỗ tương • Tính số hạng thứ n của hai dãy {Xn}, {Yn} được định nghĩa như sau: • X0 =Y0 =1 • Xn = Xn-1 + Yn-1 (n>0) 2 • Yn = n Xn-1 + Yn-1 (n>0) • Điều kiện dừng:X(0) = Y(0) = 1 50
51. Đệ quy hỗ tương long TinhXn(int n) { if (n == 0) return 1; return TinhXn(n - 1) + TinhYn(n - 1); } long TinhYn(int n) { if (n == 0) return 1; return n * n * TinhXn(n - 1) + TinhYn(n - 1); } 51
52. KHỬ ĐỆ QUY
53. Các giải pháp thay thế cho đệ quy • Đệ quy là phương pháp giúp ta tìm giải thuật cho các bài toán khó • Giải thuật đệ quy thường rất gọn gàng, dễ hiểu, dễ chuyển thành chương trình • Tuy nhiên các giải thuật đệ quy thường tốn không gian bộ nhớ và thời gian thực thi. Hơn nữa, có một số ít ngôn ngữ lập trình không cho phép đệ quy → Vì vậy, việc khử đệ quy là vấn đề cần quan tâm 53
54. Tìm công thức không đệ quy • Ví dụ: Tính tổng S(n)=1+2+ +n, với n>0 int TongDeQuy(int n) { if (n == 1) return 1; return n + tongDeQuy(n - 1); } int TongKhongDeQuy (int n) { return n * (n + 1) / 2; } 54
55. Dùng vòng lặp để khử đệ quy • Ví dụ: Tính tổng S(n)=1+2+ +n, với n>0. int TongVongLap(int n) { int S = 0; for (int i = 1; i <= n; i++) S += i; return S; } 55
56. Dùng mảng lưu trữ dữ liệu trung gian • Tính số hạng thứ n của dãy Fibonaci • Với n=7, ta có: 0 1 2 3 4 5 6 7 1 1 2 3 5 8 13 21 56
57. Dùng mảng lưu trữ dữ liệu trung gian int FibonaciArray(int n) { if (n == 0 || n == 1) return 1; int a[MAX]; a[0] = a[1] = 1; for (int i = 2; i <= n; i++) a[i] = a[i-1] + a[i-2]; return a[n]; } 57
58. Dùng stack để mô phỏng đệ quy Stack là kiểu dữ liệu đặc biệt do người dùng tự định nghĩa theo cơ chế LIFO (Last In First Out) với 2 thao tác chính: 1. Push (đưa dữ liệu vào đầu stack) 2. Pop (lấy dữ liệu từ đầu stack ra) 58
59. Q&A 59