ĐẠI HỌC KINH TẾ ĐÀ NẴNG
KHOA THỐNG - KÊ TIN HỌC
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−− −−
Môn học: CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT
Tên Đề Tài: CƠ SỞ LÝ THUYẾT THUẬT TOÁN QUAY LUI,
TRÌNH BÀY THUẬT TOÁN VÀ CÀI ĐẶT TRÊN C
CHƯƠNG TRÌNH ỨNG DỤNG THUẬT TOÁN QUAY LUI
ĐỂ TÌM ĐƯỜNG ĐI TRONG MÊ CUNG
Nhóm 7: Nguyễn Thị Ngọc Sương – 37H11K14.1
Hồ Văn Trọng – 37H11K14.1
Phùng Quý Châu – 37H11K14.1
Phùng Thị Tuyết – 37H11K14.1
Đỗ Thị Hiền – 37H11K14.1
Lê Thị Ánh Tuyết – 37H11K14.1
Nguyễn Thị Thảo – 36H11K14.1
Trần Thị Ngân – 37H11K14.1
GVHD: Th.s Nguyễn Thành Thuỷ
Cấu trúc dữ liệu và giải thuật GVHD: Th.s Nguyễn Thành Thủy
Đà Nẵng , 03/2012
Nhóm 7 Trang 2
Cấu trúc dữ liệu và giải thuật GVHD: Th.s Nguyễn Thành Thủy
MỤC LỤC
Table of Contents
MỤC LỤC..................................................................................................................................3
Table of Contents.......................................................................................................................3
LỜI CẢM ƠN............................................................................................................................3
I. GIỚI THIỆU...........................................................................................................................4
1. Lời mở đầu.........................................................................................................................4
3. Tìm hiểu về mê cung..........................................................................................................5
4. Tìm hiểu về thuật toán quay lùi (Đệ quy).........................................................................6
4.1 Định nghĩa :..................................................................................................................6

1. Lời mở đầu
Trong cuộc sống có nhiều vấn đề buộc ta phải lựa chọn hoặc tìm ra
những phương án để giải quyết được vấn đề. Trong toán học cũng thế, để
giải một bài toán đòi hỏi ta phải chọn được phương án giải quyết bài toán
một cách tối ưu để thu được kết quả mong muốn. Trong lập trình cũng thế
ta phải tìm ra được giải thuật đúng để làm nền tảng xây dựng chương trình
Nhóm 7 Trang 4
Cấu trúc dữ liệu và giải thuật GVHD: Th.s Nguyễn Thành Thủy
chạy đúng kết quả bài toán hay đề tài của người yêu cầu đặt ra. Chẳng hạn
như bài toán mê cung, đòi hỏi ta phải xây dựng thuật toán tìm được lối đi
từ cửa vào để đến được lối ra. Trong khi đó, có thể đứng trước nhiều ngã
rẽ và phải tìm được lối đi cho đến khi thoát khỏi mê cung.
2. Đặc tả đề tài
• Yêu cầu
o Chương trình đọc mê cung từ tập tin văn bản(INPUT.TXT)
• Mục tiêu đạt được
o Tìm đường đi đến cửa ra. (OUTPUT.TXT)
• Môi trường làm việc.
o Ngôn ngữ lập trình C.
3. Tìm hiểu về mê cung.
a) Định nghĩa:
Mê cung là một hệ thống gồm nhiều hành lang nối với nhau. Bài
toán tìm đường đi trong mê cung là đứng từ vị trí s ( bên trong mê
cung hoặc cửa vào ) tìm đường đi đến vị trí e ( cửa ra hoặc bên trong
mê cung).
Nhóm 7 Trang 5