Cấu trúc dữ liệu và giải thuật - chương 5

Chương 5 bài giảng cấu trúc dữ liệu và giải thuật của trường ĐHBK TP.HCM. Trình bày ngắn gọn dễ hiểu với những hiệu ứng minh họa sinh động. Để các bạn hiểu rõ hơn về đệ qui là gì? Khái niệm đệ qui có dùng lại chính nó.
Nội dung trích xuất từ tài liệu:
Cấu trúc dữ liệu và giải thuật - chương 5 A CCẤU TRÚC DỮ LIỆU VÀ B F GIẢI THUẬT (501040) D E G Chương 5: Đệ qui K H Khái niệm đệ qui Khái niệm (định nghĩa) đệ qui có dùng lại chính nó. Ví dụ: giai thừa của n là 1 nếu n là 0 hoặc là n nhân cho giai thừa của n-1 nếu n > 0 Quá trình đệ qui gồm 2 phần: Trường hợp cơ sở (base case) Trường hợp đệ qui: cố gắng tiến về trường hợp cơ sở Ví dụ trên: Giai thừa của n là 1 nếu n là 0 Giai thừa của n là n * (giai thừa của n-1) nếu n>0 2 Chương 5: Đệ qui Khoa Công nghệ Thông tinĐH Bách Khoa Tp.HCM Tính giai thừa Định nghĩa không đệ qui: n! = n * (n-1) * … * 1 Định nghĩa đệ qui: nếu n=0 n! = 1 nếu n>0 n * (n-1)! Mã C++: int factorial(int n) { if (n==0) return 1; else return (n * factorial(n - 1)); } 3 Chương 5: Đệ qui Khoa Công nghệ Thông tinĐH Bách Khoa Tp.HCM Thi hành hàm tính giai thừa factorial (3) n=3 factorial (2) … n=2 3*factorial(2) … factorial (1) 6 n=1 2*factorial(1) … 2 factorial (0) n=0 1*factorial(0) … 1 return 1; 1 4 Chương 5: Đệ qui Khoa Công nghệ Thông tinĐH Bách Khoa Tp.HCM Trạng thái hệ thống khi thi hành hàm tính giai thừa Stack hệ thống factorial(0) factorial(1) factorial(1) factorial(1) factorial(2) factorial(2) factorial(2) factorial(2) factorial(2) factorial(3) factorial(3) factorial(3) factorial(3) factorial(3) factorial(3) factorial(3) t Thời gian hệ thống Trả về từ Trả về từ Trả về từ Trả về từ Gọi hàm Gọi hàm Gọi hàm Gọi hàm hàm hàm hàm hàm factorial(3) factorial(2) factorial(1) factorial(0) factorial(0 factorial(1 factorial(2 factorial(3 ) ) ) ) t 5 Chương 5: Đệ qui Khoa Công nghệ Thông tinĐH Bách Khoa Tp.HCM Bài toán Tháp Hà nội Luật: Di chuyển mỗi lần một đĩa Không được đặt đĩa lớn lên trên đĩa nh ỏ 6 Chương 5: Đệ qui Khoa Công nghệ Thông tinĐH Bách Khoa Tp.HCM Bài toán Tháp Hà nội – Thiết kế hàm Hàm đệ qui: Chuyển (count-1) đĩa trên đỉnh của cột start sang c ột temp Chuyển 1 đĩa (cuối cùng) của cột start sang cột finish Chuyển count-1 đĩa từ cột temp sang cột finish magic 7 Chương 5: Đệ qui Khoa Công nghệ Thông tinĐH Bách Khoa Tp.HCM Bài toán Tháp Hà nội – Mã C++ void move(int count, int start, int finish, int temp) { if (count > 0) { move(count − 1, start, temp, finish); cout Bài toán Tháp Hà nội – Thi hành ...