Bài giảng Nhập môn lập trình - Bài 14: Kỹ thuật lập trình đệ quy
lượt xem 7
download
Bài giảng cung cấp cho người học các kiến thức: Kỹ thuật lập trình đệ quy. Hi vọng đây sẽ là một tài liệu hữu ích dành cho các bạn sinh viên đang theo học môn dùng làm tài liệu học tập và nghiên cứu.
Bình luận(0) Đăng nhập để gửi bình luận!
Nội dung Text: Bài giảng Nhập môn lập trình - Bài 14: Kỹ thuật lập trình đệ quy
- Trường Đại học Khoa học Tự nhiên Khoa Công nghệ thông tin Bộ môn Tin học cơ sở NHẬP MÔN LẬP TRÌNH Đặ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 Nhập môn lập trình - Chương 1: Các khái niệm cơ bản về lập trình
20 p | 115 | 8
-
Bài giảng Nhập môn lập trình: Chương 2 - Trần Minh Thái
86 p | 109 | 8
-
Bài giảng Nhập môn lập trình: Chương 1 - Trần Minh Thái
58 p | 105 | 7
-
Bài giảng Nhập môn lập trình: Bài 1 - Trần Duy Thanh
70 p | 190 | 5
-
Bài giảng Nhập môn lập trình - Bài 2: Giới thiệu ngôn ngữ lập trình C
18 p | 111 | 5
-
Bài giảng Nhập môn lập trình: Bài 2 - TS. Ngô Hữu Dũng
53 p | 65 | 3
-
Bài giảng Nhập môn lập trình: Bài 1 - TS. Ngô Hữu Dũng
47 p | 81 | 3
-
Bài giảng Nhập môn lập trình: Tổng quan về lập trình - Nguyễn Đình Hưng
21 p | 80 | 3
-
Bài giảng Nhập môn lập trình: Chương giới thiệu - ThS. Nguyễn Đông Hà
9 p | 79 | 3
-
Bài giảng Nhập môn lập trình: Bài 3 - Trần Duy Thanh
16 p | 99 | 3
-
Bài giảng Nhập môn lập trình: Giới thiệu về các cấu trúc điều khiển - Trường ĐH Khoa học tự nhiên TP. HCM
58 p | 6 | 1
-
Bài giảng Nhập môn lập trình: Sử dụng những kiểu dữ liệu cơ sở trong chương trình - Trường ĐH Khoa học tự nhiên TP. HCM
53 p | 4 | 1
-
Bài giảng Nhập môn lập trình: Giới thiệu tổng quan về lập trình - Trường ĐH Khoa học tự nhiên TP. HCM
31 p | 2 | 0
-
Bài giảng Nhập môn lập trình: Hàm và kỹ thuật tổ chức chương trình - Trường ĐH Khoa học tự nhiên TP. HCM
86 p | 2 | 0
-
Bài giảng Nhập môn lập trình: Giới thiệu về thuật toán - Trường ĐH Khoa học tự nhiên TP. HCM
29 p | 0 | 0
-
Bài giảng Nhập môn lập trình: Kỹ thuật cài đặt các thuật toán cơ bản - Trường ĐH Khoa học tự nhiên TP. HCM
37 p | 4 | 0
-
Bài giảng Nhập môn lập trình: Dữ liệu mạng và dữ liệu có cấu trúc - Trường ĐH Khoa học tự nhiên TP. HCM
37 p | 1 | 0
-
Bài giảng Nhập môn lập trình: Lập trình với tập tin văn bản thô - Trường ĐH Khoa học tự nhiên TP. HCM
38 p | 8 | 0
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