Bài giảng cơ sở lập trình nâng cao - Chương 3

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 đó
Nội dung trích xuất từ tài liệu:
Bài giảng cơ sở lập trình nâng cao - Chương 3 Chương 3 LẬP TRÌNH ĐỆ QUY 1 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 2 Đị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 3 Đị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:  1 Nếu n=0 n!=  n . (n − 1)! Nếu n>0 4 Định nghĩa theo cách đệ quy • Ví dụ 2:  1 Nếu n=0  f ( n) =  1 f (n − 1) + Nếu n>0   f (n − 1) • Ví dụ 3: Công thức tính số Fibonacci  1 Nếu n=1 hay n=2 f ( n) =   f (n − 1) + f (n − 2) Nếu n>2 5 Đị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 6 Đị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? 7 Đị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 quay về B1 chọn bài toán con khác, nếu thấy không khả quan thì chọn một số bài toán con • B5: Kết thúc 8 Định nghĩa theo cách đệ quy § Tìm định nghĩa đệ quy để tính tổng/tích của mảng số nguyên a có n phần tử (n≤100) 9 Định nghĩa theo cách đệ quy § Tìm định nghĩa đệ quy để kiểm tra số nguyên n là số chẵn hay số lẻ (không dùng phép toán % và &) 10 Định nghĩa theo cách đệ quy § Tìm định nghĩa đệ quy để tính độ dài của chuỗi s 11 Định nghĩa theo cách đệ quy § Tìm định nghĩa đệ quy để kiểm tra chuỗi s có chứa ký tự ch không 12 Định nghĩa theo cách đệ quy § Tìm định nghĩa đệ quy để đảo mảng số nguyên a có n phần tử (n≤100) 13 Định nghĩa theo cách đệ quy § Hạn chế của định nghĩa Đệ quy • Để tính f(n), chúng ta phải tính một vài hay tất cả các phần tử trước đó f(1), f(2), … • Để kiểm tra x có thuộc tập hợp đang định nghĩa hay không chúng ta cũng phải tính f(1), f(2), … Tìm định nghĩa không đệ quy tương đương 14 Định nghĩa theo cách đệ quy § Tìm định nghĩa không đệ quy của công thức đệ quy sau:  1 Nếu n=0 n!=  n . (n − 1)! Nếu n>0  1 Nếu n=0 f ( n) =  2 . f (n − 1) Nếu n>0 15 Cài đặt Hàm đệ quy § Hàm/thủ tục Đệ quy: Một hàm A được gọi là Hàm Đệ quy nếu trong định nghĩa hàm A có lời gọi đến chính hàm A KieuTraVe TenHam(Danh Sach Tham So) { … TenHam(); … } 16 Cài đặt Hàm đệ quy § Sơ đồ cài đặt • Sơ đồ 1: KieuTraVe TenHam(Kieu n) { if (dieukien dung) [return] kq; else [return] TenHam(n-1) … } 17 Cài đặt Hàm đệ quy § Sơ đồ cài đặt • Sơ đồ 2: KieuTraVe TenHam(Kieu n) { if (dieukien dequy) [return] TenHam(n-1)…; else [return] kq; } 18 Cài đặt Hàm đệ quy § Ví dụ: Cài đặt hàm đệ quy tính n! int Factorial(int n) { } 19 Hoạt động của Hàm đệ quy § Tìm hiểu hoạt động của hàm đệ quy tính an  1 Nếu n=0 ...