Đồ Án ĐACS-Giải Thuật Đệ Quy-BT Tháp HN

LỜI MỞ ĐẦU Sự ra đời của máy tính là một trong những phát minh vĩ đại của loài người, nó có ảnh hưởng lớn đến sự phát triển của xã hội và hầu hết tất cả các ngành trong xã hội đều cần đến máy tính như: y học, giáo dục, khoa học .Và máy tính cũng là thiết bị có khả năng làm thuận lợi cho những bài toán phức tạp và tốn nhiều thời gian, để giải quyết những tính toán này, thì máy tính phải dùng một trong những phương pháp đó là giải thuật, từ phương pháp này đã cho ra đời giải thuật theo kiểu đệ quy.
Trong phạm vi đề tài cho phép, em xin trình bày những hiểu biết của em về giải thuật đệ quy, và bài toán điển hình của giải thuật đệ quy là bài toán tháp Hà Nội. Dưới đây là nội dung đồ án gồm các chương:
Chương I: TÌM HIỂU VỀ GIẢI THUẬT ĐỆ QUY.
Trong chương này gồm các nội dung: Tìm hiểu về đệ quy, phân loại đệ quy, và tìm hiểu về giải thuật
Chương II: ỨNG DỤNG GIẢI THUẬT ĐỆ QUY TRÊN THÁP HÀ NỘI.
Để hoàn thành đồ án này, với sự giúp đỡ của thầy hướng dẫn: Lê Văn Long, và những tài liệu tham khảo trong của giáo viên trong viên trong và ngoài trường thuộc khoa công nghệ thông tin. Em xin chân thành cảm ơn thầy Lê Văn Long và các giáo viên trong khoa đã tận tình giúp em hoàn thành đồ án này.






MỤC LỤC
LỜI MỞ ĐẦU 1
MỤC LỤC 2
Chương I. 3
TÌM HIỂU VỀ GIẢI THUẬT ĐỆ QUY 3
1.1 Tìm hiểu về đệ quy. 3
1.1.1 Khái niệm về giải thuật đệ quy. 3
1.1.2 Cấu trúc của hàm đệ quy. 4
1.1.3 Phân loại đệ quy. 4
1.1.3.1 Đệ quy nhị phân. 4
1.1.3.2 Đệ quy tuyến tính. 5
1.1.3.3 Đệ quy phi tuyến. 6
1.1.3.4 Đệ quy tương hỗ. 7
1.2 Giải thuật đệ quy. 8
1.2.1 Tìm hiểu về giải thuật. 8
1.2.1.2 Các vấn đề liên quan đến giải thuật. 9
1.2.1.2.1 Đặc trưng của giải thuật. 9
1.2.1.2.2 Thiết kế giải thuật. 9
1.2.1.2.3 Tính đúng đắn của giải thuật. 10
1.2.1.2.4 Độ phức tạp của giải thuật. 10
1.2.1.3 Cấu trúc giải thuật đệ quy. 11
1.2.1.4 Cài đặt giải thuật đệ quy. 12
1.2.1.5 Cơ chế giải thuật khi gọi hàm đệ quy. 13
1.2.1.6 Nhận xét về giải thuật đệ quy. 14
Chương II. 16
ỨNG DỤNG GIẢI THUẬT ĐỆ QUY TRÊN BÀI TOÁN THÁP HÀ NỘI (Tower of HaNoi) 16
2.1 Sơ lược về lịch sử bài toán tháp Hà Nội 16
2.3 Cài đặt thuật toán trên ngôn ngữ C. 20
2.4 Kết luận. 21
Tài liỆu tham khẢo: 22
LỜI NHẬN XÉT CỦA GIÁO VIÊN HƯỚNG DẪN 23
LỜI NHẬN XÉT CỦA GIÁO VIÊN PHẢN BIỆN 24