TAILIEUCHUNG - Bài giảng Cơ sở lập trình nâng cao - Chương 3: Lập trình đệ quy

Bài giảng cung cấp cho người học các kiến thức: Lập trình đệ quy, cài đặt hàm đệ quy, phân loại đệ quy, phương pháp khử đệ 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. chi tiết nội dung bài giảng. | CƠ SỞ LẬP TRÌNH NÂNG CAO Biên soạn: Quang Toại TonQuangToai@ TPHCM, NĂM 2013 TRƯỜNG ĐẠI HỌC NGOẠI NGỮ - TIN HỌC KHOA CÔNG NGHỆ THÔNG TIN 1 45T/4 = 11 buoi LẬP TRÌNH ĐỆ QUY Chương 3 2 Nội dung Định nghĩa theo cách đệ quy Cài đặt Hàm đệ quy Hoạt động của Hàm đệ quy Phân loại đệ quy Ứng dụng của đệ quy Ưu điểm và khuyết điểm của đệ quy Một số phương pháp khử đệ quy Bài tập áp dụng 3 Định nghĩa theo cách đệ quy Định nghĩa theo cách đệ quy: Định nghĩa theo cách đệ 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ụ: Định nghĩa tập số tự nhiên N 0 N Nếu n N thì n+1 N 4 Định nghĩa theo cách đệ quy Mục đích của đệ quy: Tạo ra các phần tử mới Kiểm tra một phần tử có thuộc tập đã cho hay không Dùng định nghĩa theo cách đệ quy để định nghĩa các hàm hay chuỗi số (Hàm đệ quy, công thức đệ quy) Ví dụ 1: Nếu n=0 Nếu n>0 5 Định nghĩa theo cách đệ quy Ví dụ 2: Nếu n=0 Nếu n>0 Ví dụ 3: Công thức tính số Fibonacci Nếu n>2 Nếu n=1 hay n=2 6 Định nghĩa theo cách đệ quy Các thành phần của 1 định nghĩa theo cách đệ quy Thành phần 1: Thành phần không đệ quy (trường hợp cơ bản, trường hợp cơ sở, trường hợp suy biến, điều kiện dừng) Chứa những trường hợp đơn giản nhất để xây dựng nên tập hợp Thành phần 2: Thành phần đệ quy (trường hợp đệ quy) Chứa những quy tắc, công thức để tạo đối tượng mới từ những đối tượng trước đó Nhận xét: Thành phần đệ quy phải tiến về thành phần không đệ quy 7 Định nghĩa theo cách đệ quy Làm thế nào để tìm công thức đệ quy? Chia bài toán f(n) thành các bài toán con f(1), f(2), , f(n-1) có dạng giống bài toán f(n) Tìm mối quan hệ giữa bài toán lớn với bài toán con Vấn đề khó khăn Bao nhiêu bài toán con? Chọn bài toán con nào? 8 Định nghĩa theo cách đệ quy Các bước gợi ý tìm công thức đệ quy f(n) B1: Chọn một bài toán con f(k) (thường là f(n-1), f(n-2)) B2: Tìm mối quan hệ giữa f(n) với f(k) B3: Nếu tìm được mối quan hệ thì Tìm trường hợp cơ sở Nhảy đến B5 B4: Ngược lại .

• Kỹ thuật lập trình
• Bài giảng Cơ sở lập trình nâng cao
• Cơ sở lập trình nâng cao
• Lập trình đệ quy
• Cài đặt hàm đệ quy
• Phân loại đệ quy
• Phương pháp khử đệ quy
• Nội dung cơ sở lập trình nâng cao
• Cơ sở lập trình
• Phương pháp quay lui
• Cơ sở dữ liệu nâng cao
• Bài giảng Cơ sở dữ liệu nâng cao
• Giao diện lập trình
• Giao diện lập trình C
• Giao diện lập trình JAVA
• Giao diện lập trình PHP
• Tối ưu hóa chương trình
• Loại tối ưu
• Quy tắc vòng lặp
• Quy tắc hàm
• Quy tắc biểu thức
• Ôn tập kỹ thuật xử lý file
• Xử lý mảng
• Xử lý xâu ký tự
• Thuật toán cơ bản
• Phương pháp thiết kế thuật toán
• Toán hình học
• Cấu trúc dữ liệu cơ bản
• Điểm và đa giác
• Cơ sở dữ liệu
• Cơ sở dữ liệu phân tán
• Cơ sở dữ liệu hướng đối tượng
• Lập trình PL/SQL
• Quy hoạch động
• Bài toán tối ưu
• Sơ đồ cài đặt
• Độ phức tạp của thuật toán
• Ước lượng độ phức tạp
• Phân tích thuật toán
• Thời gian thực hiện thuật toán
• Phương pháp thiết kế thuật toán quay lui
• Thiết kế thuật toán
• Sơ đồ cài đặt
• Phương pháp thiết kế thuật toán nhánh cận
• Chia để trị
• Sơ đồ cài đặt
• Tìm kiếm nhị phân
• Phương pháp thiết kế thuật toán tham lam
• Giáo trình cơ sở lập trình
• Tài liệu cơ sở lập trình
• Kỹ thuật lập trình
• Bài toán con trùng lắp
• Phương pháp quy lui
• Bài giảng Lập trình hướng đối tượng nâng cao
• Lập trình hướng đối tượng nâng cao
• Lập trình hướng đối tượng
• Mô hình đa lớp
• Lập trình windows form
• Độ phức tạp thuật toán
• Kỹ thuật xử lý mảng
• Kỹ thuật xử lý file văn bản
• Hàm đệ quy
• Phương pháp Đệ qui
• Thuật toán Insertion sort
• Phương pháp Tham lam
• Thuật toán Merge sort
• Thuật toán Dijkstra
• Cấu trúc dữ liệu
• Thuật toán Viterbi
• Kết nối cơ sở dữ liệu