Bài giảng Kỹ thuật lập trình: Chương 5 - Trần Minh Thái

Bài giảng "Kỹ thuật lập trình - Chương 5: Lập trình đệ quy" cung cấp cho người học các kiến thức: 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. Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Kỹ thuật lập trình: Chương 5 - Trần Minh Thái Lập trình C Chương 5. Lập trình đệ quy (3 tiết)Trần Minh TháiEmail: minhthai@huflit.edu.vnWebsite: www.minhthai.edu.vnCập nhật: 20/03/2017Nộ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 2GIỚI THIỆU VỀ LẬP TRÌNH ĐỆ QUYGiớ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 4Giớ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)! * 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 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 6Giớ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 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 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 Bước 2: Phát hiện TH suy biến, tìm giải thuậtLà 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ôngcần đệ quy• Ví dụ: • GiaiThua(1) = 1 • USCLN(a, 0) = a • SUM(a[m:m]) = a[m] 10 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 11Phân loại đệ quy1. Đệ quy tuyến tính2. Đệ quy nhị phân3. Đệ quy phi tuyến4. Đệ quy hỗ tương 12ĐỆ QUY TUYẾN TÍNHĐệ quy tuyến tínhBước1 Nếuthỏađiềukiệndừngthì thựchiệnthaotácS(trảvềkếtquả)Bước2 Ngượclại: Bước2.1 thựchiệnlệnhS* Bước2.2 Gọihàmđệquy (chođốitượngthườnglànhỏhơn)• S, S*: xử lý không đệ quy (Có thể gộp bước 2.1 và 2.2 lại) 14Đệ 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){ ???} 15Đệ quy tuyến tínhHàm tính giai thừa (TinhGiaiThuaDQ) bằng đệ quy Bước1 Nếun=0hoặcn=1thì trảvề1 Bước2 Ngượclại: trảvền*TinhGiaiThuaDQ(n1) 16Đệ 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 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 Main( ) Gọi Giai thừa 5 n=5kq=120 Giai Thừa ( 5 ) Gọi Giai thừa 4 ...