Bài giảng Phân tích và thiết kế thuật giải: Bài 3 - TS. Ngô Quốc Việt

Chia sẻ: You Can | Ngày: | Loại File: PDF | Số trang:50

Thêm vào BST

Báo xấu

102
lượt xem 19
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Phân tích và thiết kế thuật giải - Bài 3 trình bày kiến thức về giải thuật đệ quy. Bài này gồm có một số nội dung sau: Thiết kế giải thuật đệ quy, tại sao dùng đệ quy, khi nào dùng đệ quy, đệ quy tuyến tính, đệ quy nhị phân,...và một số nội dung khác.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Phân tích và thiết kế thuật giải: Bài 3 - TS. Ngô Quốc Việt

PHÂN TÍCH THIẾT KẾ GIẢI THUẬT GIẢI THUẬT ĐỆ QUY TS. NGÔ QUỐC VIỆT 2015
Nội dung 1. Giới thiệu 2. Các giải thuật đệ quy 3. Bài tập 4. Hỏi đáp. 2 Ngô Quốc Việt
Giới thiệu  Chương trình đệ quy là chương trình gọi đến chính nó.  Cần phải có điểm dừng chương trình/hàm (trường hợp suy biến)  Đệ quy tuyến tính  Đệ quy nhị phân  Đệ quy phi tuyến, đệ quy lồng  Đệ quy hỗ tương 3 Ngô Quốc Việt
Thiết kế giải thuật đệ quy  Tham số hoá bài toán.  Phân tích trường hợp chung (biểu diễn bài toán đồng dạng nhưng khác phạm vi hay kích thước giải quyết).  Xác định trường hợp dừng (suy biến) 4 Ngô Quốc Việt
Tại sao dùng đệ quy  Ưu điểm: giải thuật đệ quy đơn giản hơn không đệ quy khi giải quyết cùng một vấn đề => dễ thiết kế, hiểu, cài đặt và thay đổi.  Nhược điểm : gọi hàm liên tục (tốn nhiều thời gian và không gian bộ nhớ trong) Trong đó, vấn đề chủ yếu phát sinh do số lần gọi hàm có tham số, dẫn đến cần không gian lưu trữ trong stack. 5 Ngô Quốc Việt
Khi nào dùng đệ quy  Dùng đệ quy để thiết kế giải thuật khi muốn đơn giản về hình thức so với cách viết thông thường.  Thường được áp dụng cho các hàm có yếu tố lặp lại với ngữ cảnh thay đổi.  Kiểm tra nếu nó không sử dụng quá nhiều bộ nhớ trong. Một số ngôn ngữ (LISP, Scheme) sử dụng đệ quy để tạo vòng lặp, nhưng tiến hành theo cách hiệu quả (dạng tail recursion) 6 Ngô Quốc Việt
Đệ quy tuyến tính  Lời gọi đệ quy chỉ được gọi một lần trong hàm. 𝐴 𝑛=0 𝑛  Ví dụ tính: 𝑎𝑛 = 𝑎𝑛/2 𝑛 > 0, 𝑛 𝑐ℎẵ𝑛 2 3𝑛 + 1 𝑎𝑛−1 𝑛 > 0, 𝑛 𝑙ẻ int CalAn(int A, int n) { if(n==0) return A; else if(n > 0 && (n %2) ==0) return (n/2)*CalAn(A, n/2); else return (3*n+1)*CalAn(A, n-1); } 7 Ngô Quốc Việt
Đệ quy nhị phân  Lời gọi đệ quy chỉ được gọi hai lần trong hàm. int fiBo(int n) { long res, fn_1, fn_2; if(n
Đệ quy lồng  Lời gọi hàm đệ quy được gọi trong vòng lặp 1 𝑛=0  Tính: 𝑥𝑛 = 2 𝑛 𝑥0 + 𝑛 − 1 2 𝑥1 + ⋯ + 12 𝑥𝑛−1 𝑛>0 long calXn(int n) { long res, i; if(n == 0) res = 1; else { res = 0; for(i = 0; i < n; i ++ ) { res += (n-i)*(n-i)*calXn(i); } } } 9 Ngô Quốc Việt
Đệ quy hỗ tương  Gọi lại hàm thông qua hàm khác (hai hàm gọi qua lại lẫn nhau) 0 𝑛=0 0 𝑛=0  𝑥𝑛 = ;𝑦 = 2 𝑥𝑛−1 + 𝑦𝑛−1 𝑛 > 0 𝑛 𝑛 ∗ 𝑥𝑛−1 + 𝑦𝑛−1 𝑛>0 long calXn(int n); long calYn(int n); long calXn(int n) { long calYn(int n) { long res, i; long res, i; if(n == 0) res = 1; if(n == 0) res = 1; else { else { res = calXn(n-1)+calYn(n-1); res = n*n*calXn(n-1)+calYn(n-1); } } return res return res } } 10 Ngô Quốc Việt
Tail Recursion = Iteration  Khi đệ quy chứa lệnh gọi chính nó ở cuối cùng, phía sau không còn lệnh nào nữa  Được gọi là tail recursion và hiệu quả như giải pháp lặp: 11 Ngô Quốc Việt
Ví dụ tính giai thừa • Iterative solution 1: 0! = 1 int iterFact (int n) { n! = n*(n-1)!, n>0 int result = 1; for (int k = 1; k
Ví dụ tính dãy Fibonacci int fib (int n) { if (n
Ví dụ tính dãy Fibonacci Hỏi: độ phức tạp bằng bao nhiêu? 14 Ngô Quốc Việt
Ví dụ tính dãy Fibonacci  Cách làm hiệu quả hơn: giữ lại số hiện hành, kết quả trước đó int fibonacci_start (int n) { return fibo(1, 0, n); } int fibo ( int curr, int prev, int n) { if (n
Tìm tuyến tính  Giải thuật  Mỗi lần kiểm tra một phần tử.  Tìm từ đầu đến cuối.  Cơ sở để làm đệ quy: mảng rỗng  Trả về kết quả -1 ( not found).  Yếu tố khác: phần tử hiện hành trùng giá trị tìm.  Trả về chỉ mục của phần tử đang xét.  Cơ sở đệ quy: tìm phần còn lại, không bao gồm phần tử đang xét. 16 Ngô Quốc Việt
Tìm tuyến tính 1. if the array is empty 2. return -1 3. else if first element matches target 4. return index of first element 5. else 6. return result of searching rest of the array, excluding the first element 17 Ngô Quốc Việt
Tìm nhị phân 1. if array is empty 2. return -1 as result 3. else if middle element matches 4. return index of middle element as result 5. else if target < middle element 6. return result of searching lower portion of array 7. else 8. return result of searching upper portion of array 18 Ngô Quốc Việt
Tìm nhị phân 19 Ngô Quốc Việt
Tháp Hà Nội • Có ba cột tháp kim cương đặt ở cửa đền Brahma ở Hà Nội • Cột bên trái có 64 đĩa, mỗi đĩa kích thước khác nhau, được chồng lên nhau: 20 Ngô Quốc Việt