Kĩ thuật lập trình đệ qui

5/4/2016 1 Giới thiệu về lập trình đệ quy Phân loại các dạng đệ quy Hoạt động của đệ quy Xây dựng giải thuật đệ quy Các giải thuật đệ quy tiêu biểu Các giải pháp thay thế cho đệ quy Tóm tắt chương 5/4/2016 2 Nội dung 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). Ví dụ: 2 chiếc gương đối diện nhau. Chiếc thứ nhất chứa hình chiếc thứ hai và ngược lại. Ta hình dung ra dãy các ảnh vô hạn của hai chiếc gương. Ví dụ: trên truyền hình, biên tập viên ngồi kế bên màn hình của chương trình đang phát, có dãy hình ảnh lập đi lập lại nhưng nhỏ dần.. 5/4/2016 3 [3.1] Giới thiệu về lập trình đệ quy Đệ quy được sử dụng rộng rãi trong khoa học máy tính và lý thuyết tính toán. Đị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. Ví dụ: về các định nghĩa đệ quy như sau: 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 5/4/2016 4 [3.1] Giới thiệu về lập trình đệ quy Ký hiệu số phần tử của một hữu hạn S là |S|: Nếu S= thì |S| = 0. Nếu S≠ thì chắc chắn có một phần tử xS, khi đó |S|=|S\{x}|+1. Đây là phương pháp định nghĩa tập hợp. 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/4/2016 5 [3.1] 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. 5/4/2016 6 [3.1] Giới thiệu về lập trình đệ quy Ví dụ trên, để định nghĩa đệ quy gồm 2 phần: Phần cố định (cơ sở - neo – anchor): các trường hợp suy biến (trường hợp đặc biệt) của thuật toán qua một điều kiện cụ thể (phần dừng của đệ quy – chương trình phải có tính dừng). 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. Lưu ý: phần đệ quy phải tiến về phần không đệ quy. 5/4/2016 7 [3.1] Giới thiệu về lập trình đệ quy Đệ quy tuyến tính. Đệ quy nhị phân. Đệ quy phi tuyến. Đệ quy hỗ tương. 5/4/2016 8 [3.2] Phân loại đệ quy S, S*: xử lý không đệ quy. Có thể gộp bước 2.1 và 2.2 lại. 5/4/2016 9 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) Đệ quy tuyến tính Hàm tính giai thừa (n!) 5/4/2016 10 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*Giai_thừa(n-1) Đệ quy tuyến tính Cài đặt: int giaiThua(int n) { if (n == 1 || n == 0) return 1; return giaiThua(n - 1) * n; } 5/4/2016 11 Đệ quy tuyến tính Uớc chung lớn nhất của 2 số dựa vào thuật toán Euclide: 5/4/2016 12 Bước 1: Nếu n=0 thì trả về m Bước 2: Ngược lại: trả về USCLN(n, m mod n) Đệ quy tuyến tính Cài đặt: int UCLN(int m, int n) { if (n == 0) return m; return uCLN(n, m% n); } 5/4/2016 13 Đệ quy tuyến tính Tính tổng giá trị của dãy số nguyên 5/4/2016 14 Bước 1: Nếu n=1 thì trả về a[n-1] Bước 2: Ngược lại: trả về a[n-1]+tongDay(a,n-1) Đệ quy tuyến tính Cài đặt: int tongDay(int []a, int n) { if (n == 1) return a[n-1]; return a[n-1]+tongDay(a, n-1); } 5/4/2016 15 Đệ quy tuyến tính Liệt kê các giá trị lẻ của dãy số nguyên 5/4/2016 16 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) Đệ 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(“%d\t”,a[n - 1]); lietKeLe(a, n - 1); } 5/4/2016 17 Đệ 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: 5/4/2016 18 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] Đệ 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(“%d\t", a[n - 1]); } 5/4/2016 19 Đệ 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 5/4/2016 20 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] Đệ 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(“%d\t", a[n - 1]); } } 5/4/2016 21 Đệ quy tuyến tính 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. 5/4/2016 22 Đệ 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 5/4/2016 23 Đệ quy nhị phân 5/4/2016 24 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ề fiBo(n-1)+fiBo(n-2) Đệ quy nhị phân 5/4/2016 25 Cài đặt: int fiBoNaCi(int n) { if (n < 2) return 1; return fiBoNaCi(n - 1) + fiBoNaCi(n - 2); } Đệ quy nhị phân 5/4/2016 26 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) Đệ quy nhị phân 5/4/2016 27 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); } Đệ quy nhị phân 5/4/2016 28 Đệ 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 Đệ quy phi tuyến 5/4/2016 29 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 Đệ quy phi tuyến 5/4/2016 30 Ta có công thức truy hồi tính dãy {Xn} như sau: X0 = 1. Xn = n 2X0 +(n-1) 2X1+..+2 2Xn-2 = 1 2Xn-1 Đệ quy phi tuyến 5/4/2016 31 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; } } Đệ quy phi tuyến 5/4/2016 32 Trong thân hàm này có lời gọi hàm đến hàm kia va ̀ trong thân hàm kia có lời gọi hàm tới hàm này. g() f() h() f() f() g() Đệ quy hỗ tương 5/4/2016 33 Hàm thứ nhất B1: Nếu thỏa đk dừng thì Thực hiện lệnh S* B2 Ngược lại: Thực hiện lệnh S Gọi ĐQ hàm hai Hàm thứ hai B1: Nếu thỏa đk dừng thì Thực hiện lệnh S* B2 Ngược lại: Thực hiện lệnh S Gọi ĐQ hàm nhất Đệ quy hỗ tương 5/4/2016 34 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) Yn = n 2Xn-1 + Yn-1; (n>0) - Điều kiện dừng:X(0) = Y(0) = 1. Đệ quy hỗ tương 5/4/2016 35 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); } Đệ quy hỗ tương 5/4/2016 36 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 . [3.3] Hoạt động của đệ quy 5/4/2016 37 Main( ) Gọi Giai thừa 5 Giai Thừa ( 5 ) Gọi Giai thừa 4 Giai Thừa ( 4 ) Gọi Giai thừa 3 Giai Thừa ( 3 ) Gọi Giai thừa 2 Giai Thừa ( 2 ) Gọi Giai thừa 1 1! = 1 n=5 n=4 n=3 n=2 n=1 kq=120 kq=24 kq=6 kq=2 kq=1 5/4/2016 38 F4=F3+F2 F0=1F1=1 F0=1F1=1F1=1F2=F1+F0 F2=F1+F0F3=F2+F1 5/4/2016 39 F4=F3+F2 F0=1F1=1 F0=1F1=1F1=1F2=F1+F0 F2=F1+F0F3=F2+F1 kq=1 kq=1 kq=1kq=2 kq=1kq=1 kq=2kq=3 kq=5 5/4/2016 40 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 (đặc biệt, dừng, neo) 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. [3.4] Xây dựng giải thuật đệ quy 5/4/2016 41 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... Bước 1: Thông số hóa bài toán 5/4/2016 42 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à giải thuật không đệ quy giải rất đơ giản. Ví dụ: GiaiThua(1)=1. USCLN(a,0)=0. TSUM(a[m:m])=a[m]. B2: Phát hiện TH suy biến, tìm giải thuật 5/4/2016 43 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. Bước 3: Phân rã theo hướng đệ quy 5/4/2016 44 B1: Thông hóa hóa bài toán: Xét ở mức tổng quát: chuyển n (n>0) đĩa từ cột A sang cột C với cột B làm trung gian. Ta gọi hàm có tên thapHaNoi(n,A,B,C) với bốn tham số, trong đó thông số n là thông số thay đổi, ta gọi n là thông số điều khiển. Bài toán tháp hà nội 5/4/2016 45 B2: Trường hợp suy biến và giải thuật: Với n=1 bài toán tổng quát suy biến thành bài toán đơn giản thapHaNoi(1,A,B,C), lúc này chỉ cần chuyển 1 đĩa từ cột A sang cột C là xong (trong đó B là cột trung gian), ta có thao tác chuyenDia(A,C). Bài toán tháp hà nội 5/4/2016 46 B3: Phân rã bài toán: Muốn n đĩa từ cột A sang cột C, với cột B là cột trung gian thapHaNoi, ta thực hiện 3 công việc sau: Chuyển (n-1) đĩa từ cột A sang cột B, lấy C làm trung gian: thapHaNoi(n-1,A,C,B) Chuyển 1 đĩa từ cột A sang cột C: chuyenDia(A,C) thao tác không đệ quy. Chuyển (n-1) đĩa từ cột B sang cột C, lấy A làm trung gian: thapHaNoi(n-1,B,A,C) Bài toán tháp hà nội 5/4/2016 47 Ta có giải thuật sau: thapHaNoi(n,A,B,C). Bước 1: Nếu chưa dừng (n>1) thì Bước 1.1 thapHaNoi(n-1,A,C,B) Bước 1.2 chuyenDia(A,C) Bước 1.3 thapHaNoi(n-1,B,A,C) Bài toán tháp hà nội 5/4/2016 48 void chuyenDia(char A, char C) { printf("Chuyen tu dia %c sang dia %c\n", A, C); } void thapHaNoi(int n, char A, char B, char C) { if(n>0) { thapHaNoi(n - 1, A, C, B); chuyenDia(A, C); thapHaNoi(n - 1, B, A, C); } } int main() { thapHaNoi(3, 'A', 'B', 'C'); return 0; } 5/4/2016 49 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 tongS(int n) { return n * (n + 1) / 2; } Tìm công thức không đệ quy 5/4/2016 50 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; } Dùng vòng lặp để khử đệ quy 5/4/2016 51 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 Dùng mảng lưu trữ dữ liệu trung gian 5/4/2016 52 Một hàm được gọi có tính đệ qui nếu trong thân của hàm đó có lệnh gọi lại chính nó một cách tường minh hay tiềm ẩn. Phân loại đệ qui Đệ qui tuyến tính. Đệ qui nhi ̣ phân. Đệ qui phi tuyến. Đệ qui hô ̃ tương. Tóm tắt chương 5/4/2016 53 Hoạt động đệ quy gồm 2 pha: pha tiến và pha lùi. Ta có ba bước để xây dựng giải thuật đệ quy: Thông số hóa. Tính trường hợp đặc biệt, dừng (suy biến – neo – cố định) Tính trường hợp tổng quát (câu lệnh và gọi đệ quy). Tóm tắt chương 5/4/2016 54 Có một số giải thuật đệ quy tiêu biểu như: quay lui, nhánh cận và chia để trị. Ta có thể dùng các giải pháp thay thế cho đệ quy như: Dùng công thức tường minh, vòng lặp. Dùng mảng 1 chiều, 2 chiều. Dùng Stack. Tóm tắt chương 5/4/2016 55 Tính n! In ra các ước số của số nguyên dương Đếm số lượng ước số của số nguyên dương Tìm ước số chung lớn nhất của 2 số nguyên dương Kiểm tra số nguyên dương n có phải là số nguyên tố? Nhập vào mảng 1 chiều số nguyên a, kích thước n Xuất mảng 1 chiều số nguyên a, kích thước n Bài tập 5/4/2016 56 Tìm phần tử có giá trị x trong mảng số nguyên a, kích thước n Viết hàm đệ quy tính tổ hợp chập k của n. Viết hàm đệ quy In mảng a gồm n phần tử (n≤100) lên màn hình Viết hàm đệ quy In ra các chữ số của số nguyên n theo thứ tự đảo ngược Viết hàm đệ quy Tìm số lớn nhất /nhỏ nhất của mảng số nguyên a có n phần tử (n≤100). Bài tập 5/4/2016 57 Viết hàm đệ quy Đếm số lần xuất hiện của ký tự ch trong chuỗi s Viết hàm đệ quy Kiểm tra n có phải là số nguyên tố không Viết hàm đệ quy Giải bài toán tháp Hanoi Viết hàm đệ quy liệt kê các phân số tối giản không giảm nằm trong [0, 1] và có mẫu số nhỏ hơn hay bằng n Viết hàm đệ quy Tính giá trị của một số viết dưới dạng chữ LA MÃ. Viết hàm đệ quy cho bài toán mã đi tuần. Bài tập