Bài giảng Kỹ thuật lập trình: Kỹ thuật lập trình đệ quy - ThS. Đặng Bình Phương
lượt xem 15
download
Chương trình trình bày về kỹ thuật lập trình đệ quy. Nội dung chính trong chương này gồm có: Tổng quan về đệ quy, các vấn đề đệ quy thông dụng, phân tích giải thuật & khử đệ quy, các bài toán kinh điển. Mời các bạn cùng tham khảo để nắm bắt các nội dung chi tiết.
Bình luận(0) Đăng nhập để gửi bình luận!
Nội dung Text: Bài giảng Kỹ thuật lập trình: Kỹ thuật lập trình đệ quy - ThS. Đặng Bình Phương
- Bộ môn Công nghệ phần mềm Khoa Công nghệ thông tin Trường Đại học Khoa học Tự nhiên KỸ THUẬT LẬP TRÌNH ThS. Đặng Bình Phương dbphuong@fit.hcmus.edu.vn KỸ THUẬT LẬP TRÌNH ĐỆ QUY 1
- && VC VC BB BB Nội dung 1 Tổng quan về đệ quy 2 Các vấn đề đệ quy thông dụng 3 Phân tích giải thuật & khử đệ quy 4 Các bài toán kinh điển Kỹ thuật lập trình đệ quy 2
- && VC VC BB BB Bài toán Cho S(n) = 1 + 2 + 3 + … + n =>S(10)? S(11)? S(10) = 11 + 22 + … + 10 10 = 55 55 S(11) = 11 + 22 + … + 10 10 + 11 11 = 66 66 = S(10) + 11 11 = 55 55 + 11 11 = 66 66 Kỹ thuật lập trình đệ quy 3
- && VC VC BB BB 2 bước giải bài toán Bước 2. Thế ngược ác định kết quả bài toán đồng S(n) = S(n1) + nn dạng từ đơn giản đến phức tạp Kết quả cuối cùng. S(n1) = S(n2) + n1 n1 … = … + … … Bước 1. Phân tích S(1) = S(0) + 11 hân tích thành bài toán đồng dạng nhưng đơn giản hơn. S(0) = 00 ừng lại ở bài toán đồng dạng đơn giản nhất có thể xác định ngay kết quả. Kỹ thuật lập trình đệ quy 4
- && VC VC BB BB Khái niệm đệ quy Khái niệm Vấn đề đệ quy là vấn đề được định nghĩa bằng chính nó. Ví dụ Tổng S(n) được tính thông qua tổng S(n1). 2 điều kiện quan trọng Tồn tại bước đệ quy. Điều kiện dừng. Kỹ thuật lập trình đệ quy 5
- && VC VC BB BB Hàm đệ quy trong NNLT C Khái niệm Một hàm được gọi là đệ quy nếu bên trong thân của hàm đó có lời gọi hàm lại chính nó một cách trực tiếp hay gián tiếp. … Hàm(…) … Hàm1(…) … Hàm2(…) { { { … … … … … … Lời gọi Hàm Lời gọi Hàm2 Lời gọi Hàmx … … … … … … … … … } } } ĐQ trực tiếp ĐQ gián tiếp Kỹ thuật lập trình đệ quy 6
- && VC VC BB BB Cấu trúc hàm đệ quy { (TS) Phần dừng if ()(Base step) { • Phần khởi tính toán hoặc điểm kết thúc của thuật toán … • Không chứa phần đang được return ; định nghĩa } Phần đệ quy … (Recursion step) … Lời gọi Hàm• Có sử dụng thuật toán đang được định nghĩa. … } Kỹ thuật lập trình đệ quy 7
- && VC VC BB BB Phân loại Trong thân hàm có duy nhất một TUYẾN TÍNH 1 lời gọi hàm gọi lại chính nó một cách tường minh. Trong thân hàm có hai lời gọi NHỊ PHÂN 2 hàm gọi lại chính nó một cách tường minh. HỖ TƯƠNG Trong thân hàm này có lời gọi hàm tới PHI TUYẾN 3 hàm kia và bên trong thân hàm kia có lời gọi hàm tới hàm này. 4 Trong thân hàm có lời gọi hàm lại chính nó được đặt bên trong thân vòng lặp. Kỹ thuật lập trình đệ quy 8
- && VC VC BB BB Đệ quy tuyến tính Ví dụ Tính S(n) = 1 + 2 + … + n S(n) = S(n – 1) + n ĐK dừng: S(0) = 0 Cấu trúc chương trình .: Chương trình :. long Tong(int n) { TênHàm() { if (n == 0) if () { return 0; … return Tong(n–1) + n; return ; } } … TênHàm(); … } Kỹ thuật lập trình đệ quy 9
- && VC VC BB BB Đệ quy nhị phân Ví dụ Tính số hạng thứ n của dãy Fibonacy: f(0) = f(1) = 1 f(n) = f(n – 1) + f(n – 2) n > 1 Cấu trúc chương trình ĐK dừng: f(0) = 1 và f(1) = 1 TênHàm() { if () { .: Chương trình :. … long Fibo(int n) return ; { } if (n == 0 || n == 1) … TênHàm(); return 1; … return Fibo(n–1)+Fibo(n–2); … TênHàm(); } … } Kỹ thuật lập trình đệ quy 10
- && VC VC BB BB Đệ quy hỗ tương Ví dụ Tính số hạng thứ n của dãy: x(0) = 1, y(0) = 0 x(n) = x(n – 1) + y(n – 1) y(n) = 3*x(n – 1) + 2*y(n – 1) Cấu trúc chương trình ĐK dừng: x(0) = 1, y(0) = 0 TênHàm1() { .: Chương trình :. if () long yn(int n); return ; long xn(int n) { … TênHàm2(); … if (n == 0) return 1; } return xn(n1)+yn(n1); TênHàm2() { } if () long yn(int n) { return ; if (n == 0) return 0; … TênHàm1(); … return 3*xn(n1)+2*yn(n1); } } Kỹ thuật lập trình đệ quy 11
- && VC VC BB BB Đệ quy phi tuyến Ví dụ Tính số hạng thứ n của dãy: x(0) = 1 x(n) = n2x(0) + (n1)2x(1) + … + 22x(n – 2) + 12x(n – 1) Cấu trúc chương trình ĐK dừng: x(0) = 1 TênHàm() { if () { .: Chương trình :. … long xn(int n) return ; { } if (n == 0) return 1; … Vòng lặp { long s = 0; … TênHàm(); … for (int i=1; i
- && VC VC BB BB Các bước xây dựng hàm đệ quy Tổng quát hóa bài toán cụ thể thành bài toán tổng quát. Thông số hóa Thông số hóa cho bài toán tổng quát bài toán VD: n trong hàm tính tổng S(n), … Chia bài toán tổng quát ra thành: Phần không đệ quy. Tìm thuật giải Phần như bài toán trên nhưng tổng quát kích thước nhỏ hơn. VD: S(n) = S(n – 1) + n, … Các trường hợp suy biến của bài toán. Kích thước bài toán trong trường hợp Tìm các trường này là nhỏ nhất. hợp suy biến (neo) VD: S(0) = 0 Kỹ thuật lập trình đệ quy 13
- && VC VC BB BB Cơ chế gọi hàm và STACK main() B() main { { …; …; A(); D(); …; …; D(); } A D …; } C() { A() …; { } B C …; B(); D D() STACK …; B B B C C(); { …; …; D A A A A A A A D } } M M M M M M M M M M M Thời gian Kỹ thuật lập trình đệ quy 14
- && VC VC BB BB Nhận xét Cơ chế gọi hàm dùng STACK trong C phù hợp cho giải thuật đệ quy vì: Lưu thông tin trạng thái còn dở dang mỗi khi gọi đệ quy. Thực hiện xong một lần gọi cần khôi phục thông tin trạng thái trước khi gọi. Lệnh gọi cuối cùng sẽ hoàn tất đầu tiên. Kỹ thuật lập trình đệ quy 15
- && VC VC BB BB Ví dụ gọi hàm đệ quy Tính số hạng thứ 4 của dãy Fibonacy F(4) 5 3 F(3) 5 + 2 F(2) 2 F(2) 3 + 1 F(1) 1 F(1) 2 + 1 F(0) 1 F(1) 2 + 1 F(0) Kỹ thuật lập trình đệ quy 16
- && VC VC BB BB Một số lỗi thường gặp Công thức đệ quy chưa đúng, không tìm được bài toán đồng dạng đơn giản hơn (không hội tụ) nên không giải quyết được vấn đề. Không xác định các trường hợp suy biến – neo (điều kiện dừng). Thông điệp thường gặp là StackOverflow do: Thuật giải đệ quy đúng nhưng số lần gọi đệ quy quá lớn làm tràn STACK. Thuật giải đệ quy sai do không hội tụ hoặc không có điều kiện dừng. Kỹ thuật lập trình đệ quy 17
- && VC VC BB BB Các vấn đề đệ quy thông dụng ĐĐệệ quy?? quy?? Kỹ thuật lập trình đệ quy 18
- && VC VC BB BB 1.Hệ thức truy hồi Khái niệm Hệ thức truy hồi của 1 dãy An là công thức biểu diễn phần tử An thông qua 1 hoặc nhiều số hạng trước của dãy. AA00 AA11 … … AAn2 n2 AAn1 n1 Hàm truy h AAnn Hàm truy h ồồii AA00 AA11 … … AAn2 n2 AAn1 n1 Hàm truy h AAnn Hàm truy h ồồii Kỹ thuật lập trình đệ quy 19
- && VC VC BB BB 1.Hệ thức truy hồi Ví dụ 1 Vi trùng cứ 1 giờ lại nhân đôi. Vậy sau 5 giờ sẽ có mấy con vi trùng nếu ban đầu có 2 con? Giải pháp Gọi Vh là số vi trùng tại thời điểm h. Ta có: • Vh = 2Vh1 • V0 = 2 Đệ quy tuyến tính với V(h)=2*V(h1) và điều 20 kiện dừng V(0) = 2 Kỹ thuật lập trình đệ quy
CÓ THỂ BẠN MUỐN DOWNLOAD
-
Bài giảng Kỹ thuật lập trình - Phạm Thế Bảo
0 p | 217 | 32
-
Bài giảng Kỹ thuật lập trình: Chương I - Lưu Hồng Việt
48 p | 194 | 23
-
Bài giảng Kỹ thuật lập trình: Chương II - Lưu Hồng Việt
74 p | 181 | 18
-
Bài giảng Kỹ thuật lập trình: Chương IV - Lưu Hồng Việt
32 p | 149 | 17
-
Bài giảng Kỹ thuật lập trình Programing technique - Vũ Đức Vượng
68 p | 219 | 16
-
Bài giảng Kỹ thuật lập trình: Chương V - Lưu Hồng Việt
19 p | 124 | 15
-
Bài giảng Kỹ thuật lập trình: Chương III - Lưu Hồng Việt
51 p | 146 | 15
-
Bài giảng Kỹ thuật lập trình: Chương VI - Lưu Hồng Việt
27 p | 132 | 11
-
Bài giảng Kỹ thuật lập trình: Phần 1 - ĐH CNTT&TT
37 p | 114 | 10
-
Bài giảng Kỹ thuật lập trình - Bài 1: Tổng quan về kỹ thuật lập trình
65 p | 163 | 8
-
Bài giảng Kỹ thuật lập trình: Bài 1 - Phạm Đình Sắc
9 p | 125 | 7
-
Bài giảng Kỹ thuật lập trình nâng cao: Chương 4 - ThS. Dương Thành Phết
26 p | 91 | 7
-
Bài giảng Kỹ thuật lập trình: Chương 1 - Trần Minh Thái, Phạm Đức Thành
50 p | 116 | 6
-
Bài giảng Kỹ thuật lập trình - TS. Vũ Hương Giang
8 p | 117 | 5
-
Bài giảng Kỹ thuật lập trình: Bài 2 - Phạm Đình Sắc
7 p | 116 | 5
-
Bài giảng Kỹ thuật lập trình - Chương 10: Tổng kết môn học (Trường Đại học Bách khoa Hà Nội)
67 p | 12 | 4
-
Bài giảng Kỹ thuật lập trình - Chương 1: Tổng quan về kỹ thuật lập trình
45 p | 52 | 3
-
Bài giảng Kỹ thuật lập trình - Chương 1: Tổng quan về kỹ thuật lập trình (Trường Đại học Bách khoa Hà Nội)
46 p | 12 | 3
Chịu trách nhiệm nội dung:
Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA
LIÊN HỆ
Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM
Hotline: 093 303 0098
Email: support@tailieu.vn