tailieunhanh - Bài giảng Kỹ thuật lập trình: Chương 3 - Trần Minh Thái, Phạm Đức Thành

Bài giảng "Kỹ thuật lập trình - Chương 3: Kỹ thuật lập trình đệ quy" trình bày các nội dung: 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. . | KỸ THUẬT LẬP TRÌNH Chương 3 Kỹ thuật lập trình đệ quy TRẦN MINH THÁI – minhthai@, PHẠM ĐỨC THÀNH – phamducthanh@, 28/04/2016 1 Trần Minh Thái - Phạm Đức Thành . 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 28/04/2016 2 Trần Minh Thái - Phạm Đức Thành 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 28/04/2016 3 Trần Minh Thái - Phạm Đức Thành [] 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 28/04/2016 4 Trần Minh Thái - Phạm Đức Thành [] 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). 28/04/2016 5 Trần Minh Thái - Phạm Đức Thành [] 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. 28/04/2016 6 Trần Minh Thái - Phạm . | KỸ THUẬT LẬP TRÌNH Chương 3 Kỹ thuật lập trình đệ quy TRẦN MINH THÁI – minhthai@, PHẠM ĐỨC THÀNH – phamducthanh@, 28/04/2016 1 Trần Minh Thái - Phạm Đức Thành . 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 28/04/2016 2 Trần Minh Thái - Phạm Đức Thành 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 28/04/2016 3 Trần Minh Thái - Phạm Đức Thành [] Giới thiệu về lập