Xem mẫu
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
...
- tailieumienphi.vn
nguon tai.lieu . vn