Bài giảng Cấu trúc dữ liệu và giải thuật: Đệ qui - TS. Đào Nam Anh

Chia sẻ: Bình Yên | Ngày: | Loại File: PDF | Số trang:50

0
18
lượt xem
1
download

Bài giảng Cấu trúc dữ liệu và giải thuật: Đệ qui - TS. Đào Nam Anh

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

Bài giảng "Cấu trúc dữ liệu và giải thuật: Đệ qui" trình bày các khái niệm đệ quy, ước số chung nhỏ nhất, tính giai thừa đệ qui, cây đệ qui chữ H, giải pháp đệ quy, chia để trị,... Mời các bạn cùng tham khảo nội dung chi tiết.

Chủ đề:
Lưu

Nội dung Text: Bài giảng Cấu trúc dữ liệu và giải thuật: Đệ qui - TS. Đào Nam Anh

DATA STRUCTURE AND ALGORITHM<br /> Recursion<br /> CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT<br /> Đệ qui<br /> Dr. Dao Nam Anh<br /> <br /> Data Structure and Algorithm<br /> <br /> 1<br /> <br /> Resource - Reference<br /> Slides adapted from Robert Sedgewick, and Kevin<br /> Wayne, edit by Dao Nam Anh.<br /> Major Reference:<br /> <br /> •<br /> <br /> Robert Sedgewick, and Kevin Wayne, “Algorithms”<br /> Princeton University, 2011, Addison Wesley<br /> <br /> •<br /> <br /> Algorithm in C (Parts 1-5 Bundle)- Third Edition by<br /> Robert Sedgewick, Addison-Wesley<br /> <br /> •<br /> <br /> Cấu trúc dữ liệu và giải thuật, Đinh Mạnh Tường.<br /> <br /> •<br /> <br /> Giải thuật và lập trình, Lê Minh Hoàng, Đại Học<br /> Sư Phạm, 2002<br /> Data Structure and Algorithm<br /> <br /> 2<br /> <br /> Khái niệm<br /> <br /> •<br /> <br /> Là một phương pháp lập trình cho phép một hàm có thể<br /> gọi lại chính nó trực tiếp hoặc gián tiếp.<br /> Ví dụ: void Test()<br /> {<br /> Test();<br /> }<br /> Reproductive Parts<br /> M. C. Escher, 1948<br /> <br /> •<br /> <br /> Một chương trình đệ quy hoặc một định nghĩa đệ quy thì<br /> không thể gọi đến chính nó mãi mãi mà phải có một<br /> điểm dừng đến một trường hợp đặc biệt nào đó, mà ta<br /> gọi là trường hợp suy biến (degenerate case).<br /> Data Structure and Algorithm<br /> <br /> 3<br /> <br /> Khái niệm<br /> Phương pháp thiết kế một giải thuật đệ quy:<br /> <br /> •<br /> •<br /> <br /> Tham số hoá bài toán<br /> <br /> •<br /> <br /> Tìm trường hợp suy biến<br /> <br /> Phân tích trường hợp chung : đưa bài toán dưới dạng bài<br /> toán cùng loại nhưng có phạm vi giải quyết nhỏ hơn<br /> theo nghiã dần dần sẽ tiến đến trường hợp suy biến<br /> <br /> Data Structure and Algorithm<br /> <br /> 4<br /> <br /> Khái niệm<br /> Chương trình đệ quy gồm hai phần chính:<br /> <br /> 1.<br /> 2.<br /> <br /> Phần cơ sở: Điều kiện thoát khỏi đệ quy (điểm dừng)<br /> Phần đệ quy: Trong phần thân chương trình có lời gọi<br /> đến chính bản thân chương trình với giá trị mới của<br /> tham số nhỏ hơn giá trị ban đầu<br /> <br /> Data Structure and Algorithm<br /> <br /> 5<br /> <br />

CÓ THỂ BẠN MUỐN DOWNLOAD

Đồng bộ tài khoản