Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Bài giảng Cấu trúc dữ liệu và giải thuật - Thuật toán đệ quy gồm có những nội dung chính sau đây: Định nghĩa đệ quy, thuật toán đệ quy, phân tích thuật toán đệ quy, đệ quy có nhớ, thuật toán quay lui (backtracking algorithm). . | REVIEW Xác định mối quan hệ giữa các cặp hàm f ĩì và g ĩì sau đây a n n2 5 3 n 1 g n 6n b f ji n2 3-ựn 1 g n n3 c n 2n2 5 n g n Nội dung Định nghĩa đệ quy Thuật toán đệ quy Phân tích thuật toán đệ quy Đệ quy có nhớ Thuật toán quay lui backtracking algorithm 1 10 2011 THUẬTTOÁN ĐÊ QUY Định nghĩa đệ quy Đôi tượng bao gồm chính nó hoặc được định nghĩa dưới dạng chính nó. VD. Định nghĩa một công thức hợp lệ của các biến số và các phép toán A X là công thức hợp lệ nếu X là biến hoặc số Nếu f g là công thức hợp lệ thì Ư 3 Ư-3 Ư 3 ừ 3 cũng là công thức hợp lệ Elena Filippova. Recursion. 2003 Acrylic on Canvas 160 cm X 160 cm 63 X 63 1 Hàm được định nghĩa đệ quy . 1 nếu n 0 n 1 f . X. Z n X n 1 nếu n 0 _ 1 nếu n 1 2 1 w pib n 1 Fib n 2 nếu n 2 Ío nếu n 0 1 nếu n 1 2P n 1 p n 2 nếu n 1 Thuật toán đệ quy Thuật toán có chứa lời gọi đệ quy đến chính nó với đầu vào kích thước nhỏ hơn. VD. Sắp xếp trộn - MergeSort_________________ MergeSort int A int start int end if start end int mid start end 2 MergeSort A start mid MergeSort A mid 1 end Merge A start mid end 1 10 2011 Định nghĩa đệ quy Mọi định nghĩa đệ quy đều gồm 2 phần Một trường hợp cơ sở nhỏ nhất có thể xử lý trực tiếp mà không cần đệ quy và Một phương thức tổng quát mà biến đổi một trường hợp cụ thể về các trường hợp nhỏ hơn. Do đó biến đổi các trường hợp cho đến khi về trường hợp cơ sở. 2 Thuật toán đệ quy Mô tả thời gian thực hiện của thuật toán đệ quy bằng công thức đệ quy VD. MergeSort có í 0 1 nếun l 2T 0 n nếu n 1 Bỏ qua Tin với các giá trị n nhỏ coi là hằng . Ta có thể viết lại T n là T ịì 2T 0 n 1 10 2011 Phân tích thuật toán đệ quy Giải công thức đệ quy để tìm 0 hoặc 0 bằng Phương pháp thay thế Phương pháp cây đệ quy Dùng định lý thợ Phương pháp thay thế Gồm 2 bước Đoán dạng của lời giải Sử dụng quy nạp toán học để tìm ra các hằng và chứng minh lời giải Xác định cận trên của công thức đệ quy T n 2T P 2J n Đoán T n O nlogn Cần chứng minh Tin cnìogn với hằng sốn 0 được chọn phù hợp
