TAILIEUCHUNG - Bài giảng Nhập môn lập trình - Chương 16: Kỹ thuật lập trình đệ quy

Chương 16 trang bị cho người học những hiểu biết về kỹ thuật lập trình đệ quy. Trong chương này chúng ta sẽ cùng tìm hiểu một số nội dung cơ bản sau: Tổng quan về đệ quy, các vấn đề đệ quy thông dụng, phân tích giải thuật và khử đệ quy, các bài toán kinh điển. . | Nội dung NMLT - Kỹ thuật lập trình đệ quy Tổng quan về đệ quy 1 Các vấn đề đệ quy thông dụng 2 Phân tích giải thuật & khử đệ quy 3 Các bài toán kinh điển 4 Bài toán Cho S(n) = 1 + 2 + 3 + + n =>S(10)? S(11)? NMLT - Kỹ thuật lập trình đệ quy 1 + 2 + + 10 1 + 2 + + 10 = 55 + 11 = 66 1 + 2 + + 10 = = S(10) S(11) 1 + 2 + + 10 S(10) = + 11 = + 11 55 = 66 S(10) + 11 55 + 11 2 bước giải bài toán NMLT - Kỹ thuật lập trình đệ quy = S(n) + n S(n-1) = S(n-1) + n-1 S(n-2) = + = S(1) + 1 S(0) = S(0) 0 Bước 1. Phân tích Phân tích thành bài toán đồng dạng nhưng đơn giản hơn. Dừng lại ở bài toán đồng dạng đơn giản nhất có thể xác định ngay kết quả. Bước 2. Thế ngược Xác định kết quả bài toán đồng dạng từ đơn giản đến phức tạp Kết quả cuối cùng. Khái niệm đệ quy NMLT - Kỹ thuật lập trình đệ 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(n-1). 2 điều kiện quan trọng Tồn tại bước đệ quy. Điều kiện dừng. 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. NMLT - Kỹ thuật lập trình đệ quy Hàm( ) { Lời gọi Hàm } ĐQ trực tiếp Hàm1( ) { Lời gọi Hàm2 } ĐQ gián tiếp Hàm2( ) { Lời gọi Hàmx } Cấu trúc hàm đệ quy NMLT - Kỹ thuật lập trình đệ quy { if () { return ; } Lời gọi Hàm } (TS) Phần dừng (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 định nghĩa Phần đệ quy (Recursion step) Có sử dụng thuật toán đang được định nghĩa. Phân loại NMLT - Kỹ thuật lập trình đệ quy 2 TUYẾN TÍNH NHỊ PHÂN HỖ TƯƠNG PHI TUYẾN 1 3 4 Trong thân hàm có duy nhất một 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 hàm gọi lại chính nó một cách tường minh. Trong thân hàm này có lời gọi hàm tới 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. Trong thân hàm có lời

• Kỹ thuật lập trình
• Nhập môn lập trình
• Bài giảng Nhập môn lập trình
• Ngôn ngữ lập trình
• Kỹ thuật lập trình đệ quy
• Phân tích giải thuật
• Khử đệ quy
• Kỹ thuật lập trình
• Ứng dụng lập trình
• Giáo trình nhập môn lập rình
• Bài tập nhập môn lập trình
• Viết chương trình lập trình
• Ngôn ngữ lập trình C
• Bộ từ vựng của C
• Cấu trúc chương trình C
• Kỹ thuật lập trình C
• Phương pháp lập trình
• Ngôn ngữ lập trình kỹ thuật
• Tài liệu nhập môn lập trình
• Ngôn ngữ C#
• Công cụ lập trình
• Chức năng lập trình
• Ebook Nhập môn lập trình không code
• Nhập môn lập trình không code
• Lập trình không code
• Lập trình viên
• Bài giảng Nhập môn về lập trình
• Tổ chức máy tính
• Ngôn ngữ lập trình
• Công cụ lập trình
• chương trình lập trình
• giáo trình lập trình
• lập trình máy tính
• kinh nghiệm lập trình
• thủ thuật lập trình
• nhập môn tin học
• Bài giảng Nhập môn lập trình C
• Nhập môn lập trình C
• Lập trình C
• Chương trình C
• Xây dựng chương trình
• Diễn biến thuật toán
• Chương trình máy tính
• Kiến thức lập trình
• Bài giảng Nhập môn lập trình Java
• Nhập môn lập trình Java
• Lập trình Java
• Lập trình giao diện
• Đối tượng khung chứa
• Bộ quản lý trình bày
• Giới thiệu ngôn ngữ lập trình C
• Các kiểu dữ liệu cơ sở
• Các lệnh nhập xuất
• Chuỗi ký tự
• Hệ thống nhập xuất trong lập trình
• Tập tin văn bản thô
• Xuất nhập Console
• Vấn đề xử lý files truy cập
• Xử lý file
• Hàm nhập xuất
• Kiểu dữ liệu
• Câu lệnh điều kiện
• Câu lệnh điều kiện if
• Câu lệnh rẽ nhánh switch
• Kiểu dữ liệu cơ sở
• Ngôn ngữ lập trình C C++