Lập trình C - Chương 5: Lập trình đệ quy

Lập trình CChương 5. Lập trình đệ quy(3 tiết)Trần Minh TháiEmail: minhthai@huflit.edu.vn Website: www.minhthai.edu.vn Cập nhật: 20/03/2017Nội dungGiới thiệu về lập trình đệ quyXây dựng giải thuật đệ quyPhân loại các dạng đệ quyHoạt động của đệ quyCác giải pháp thay thế cho đệ quyBài tậpGIỚI THIỆU VỀ LẬP TRÌNH ĐỆ QUYKhi 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 minhKỹ 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ĩaGiới thiệu về lập trình đệ quyVí 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)! * nTập số tự nhiênSố 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)Giới thiệu về lập trình đệ quyCấu trúc danh sách liên kết (linklist/xâu) kiểu TCấu trúc rỗng là danh sách liên kết kiểu TKế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 TGiới thiệu về lập trình đệ quy Để đị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 của thuật toán qua một điều kiện cụ thể (phần dừng của đệ quy)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 đệ quyGiới thiệu về lập trình đệ quyBước 1: Thông số hóa bài toánBướ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àyBước 3: Phân rã bài toán theo hướng đệ quyXây dựng giải thuật đệ quyTổ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ấtBước 1: Thông số hóa bài toánLà 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 đệ quyVí dụ: GiaiThua(1) = 1USCLN(a, 0) = a SUM(a[m:m]) = a[m]Bước 2: Phát hiện TH suy biến, tìm giải thuậtTì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ơnBước 3: Phân rã theo hướng đệ quyĐệ quy tuyến tínhĐệ quy nhị phânĐệ quy phi tuyếnĐệ quy hỗ tươngPhân loại đệ quyĐỆ QUY TUYẾN TÍNHS, S*: xử lý không đệ quy (Có thể gộp bước 2.1 và 2.2 lại)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Đệ quy tuyến tínhViết hàm tính giai thừa của số nguyên n bằng cách dùng vòng lặpint TinhGiaiThua(int n){ ???}Hàm tính giai thừa (TinhGiaiThuaDQ) bằng đệ quyBước 1Nếu n=0 hoặc n=1 thì trả về 1Bước 2Ngược lại: trả về n*TinhGiaiThuaDQ (n-1)Đệ quy tuyến tínhCài đặt:int TinhGiaiThuaDQ(int n){ if (n == 1 || n == 0) return 1; return n*TinhGiaiThuaDQ(n - 1);} Đệ quy tuyến tínhGồ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 nhauHoạt động của đệ quyMain( )Gọi Giai thừa5Giai Thừa ( 5 )Gọi Giai thừa4Giai Thừa ( 4 )Gọi Giai thừa3Giai Thừa ( 3 )Gọi Giai thừa2Giai Thừa ( 2 )Gọi Giai thừa11! = 1n=5n=4n=3n=2n=1kq=120kq=24kq=6kq=2kq=1Viế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ặpint USCLN (int m, int n){ ???} Đệ quy tuyến tínhUớ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+mBướ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)Đệ quy tuyến tínhCà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);}Đệ quy tuyến tínhĐệ quy tuyến tínhViế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ặpvoid XuatLe (int []a, int n){ ???}Xuất các giá trị lẻ của dãy số nguyên bằng đệ quyBước 1:Nếu n=0 thì dừngBước 2:Ngược lại:Bước 2.1Nếu a[n-1] lẻ xuất a[n-1]Bước 2.2gọi hàm LietKeLe(a, n-1)Đệ quy tuyến tínhCà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);}Đệ quy tuyến tínhKết quả xuất ra ngược với dãy ban đầu nhập vàoXuất xuôi lại ta làm như sau:Bước 1:Nếu n=0 thì dừngBước 2:Ngược lại:Bước 2.1gọi hàm LietKeLe(a, n-1)Bước 2.2Nếu a[n-1] lẻ xuất a[n-1]Đệ quy tuyến tínhCà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]);}Đệ 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 sauBước 1:Nếu chưa dừng (n>0) thì:Bước 1.1gọi hàm LietKeLe(a, n-1)Bước 1.2Nếu a[n-1] lẻ xuất a[n-1]Đệ quy tuyến tínhCà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]); }}Đệ quy tuyến tínhTí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)Đệ quy tuyến tínhCài đặt:int TongDay(int []a, int n){ if (n == 1) return a[0]; return a[n-1] + TongDay(a, n-1);}Đệ quy tuyến tínhBài tậpCho 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:Bài tậpCho mảng một chiều số nguyên a, kích thước nViế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 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ĐỆ QUY NHỊ PHÂNChươ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Đệ quy nhị phânBướ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.1thực hiện lệnh S*Bước 2.2Gọi hàm đệ quy (đối tượng nhỏ hơn nhánh trái) lần thứ nhấtBước 2.3Gọi hàm đệ quy (nhánh phải) lần thứ haiĐệ quy nhị phânViết hàm Fibonaci (n) để tính số hạng thứ n của dãy FibonaciBước 1Nếu nright trả về -1Bước 2B2.1:Tính mid=(left+right)/2B2.2:Nếu a[mid]=x thì trả về midB2.3:Nếu a[mid] right) return -1; int mid = (left + right) / 2; if (a[mid] == x) return mid; if (a[mid] 0) Yn = n2Xn-1 + Yn-1 (n>0) Điều kiện dừng:X(0) = Y(0) = 1Đệ quy hỗ tươnglong 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ươngKHỬ ĐỆ 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âmCác giải pháp thay thế cho đệ quyVí dụ: Tính tổng S(n)=1+2+..+n, với n>0int TongDeQuy(int n){ if (n == 1) return 1; return n + tongDeQuy(n - 1);}int TongKhongDeQuy (int n){ return n * (n + 1) / 2;}Tìm công thức không đệ quyVí 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ử đệ quyTính số hạng thứ n của dãy FibonaciVới n=7, ta có:012345671123581321Dùng mảng lưu trữ dữ liệu trung gianint 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];}Dùng mảng lưu trữ dữ liệu trung gianStack 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:Push (đưa dữ liệu vào đầu stack) Pop (lấy dữ liệu từ đầu stack ra)Dùng stack để mô phỏng đệ quyQ&A