Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC SƢ PHẠM
NGUYỄN THỊ HỒNG PHƢỢNG
THUẬT TOÁN FRAME – STEWART GIẢI BÀI TOÁN
THÁP HÀ NỘI TỔNG QUÁT
LUẬN VĂN THẠC SĨ TOÁN HỌC
THÁI NGUYÊN - 2010
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC SƢ PHẠM
NGUYỄN THỊ HỒNG PHƢỢNG
THUẬT TOÁN FRAME – STEWART GIẢI BÀI TOÁN
THÁP HÀ NỘI TỔNG QUÁT
LUẬN VĂN THẠC SĨ TOÁN HỌC
Chuyên ngành: Giải tích
Mã số: 60 46 01
Người hướng dẫn khoa học: PGS. TS. TẠ DUY PHƢỢNG
THÁI NGUYÊN - 2010
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
1
MỤC LỤC
Trang
MỤC LỤC
LỜI NÓI ĐẦU ............................................................................................... 2
Chƣơng 1 ....................................................................................................... 4
TỔNG QUAN VỀ TRÒ CHƠI THÁP HÀ NỘI .......................................... 4
§1. Lịch sử trò chơi Tháp Hà Nội ............................................................ 4
§2. Sơ lược về bài toán tháp Hà Nội tổng quát, các bài toán cải biên và
các vấn đề toán học liên quan ................................................................ 15
Chƣơng 2: TRÒ CHƠI THÁP HÀ NỘI..................................................... 21
§1 Trò chơi tháp Hà Nội và thuật giải đệ qui.......................................... 21
§2 Giải bài toán tháp Hà Nội bằng biểu diễn trong hệ đếm cơ số 2 ........ 26
§3 Đồ thị Hà Nội.................................................................................... 34
§4 Giải bài toán Tháp Hà Nội trên máy tính ........................................... 38
Chƣơng 3: BÀI TOÁN THÁP HÀ NỘI VỚI BỐN CỌC (Trò chơi
Reve-The Reve’s Puzzle) ............................................................................. 39
§1 Trò chơi Tháp Hà Nội với bốn cọc .................................................... 39
§2 Tính số bước chuyển tối ưu trong trò chơi Tháp Hà Nội với bốn cọc...... 43
Chƣơng 4: BÀI TOÁN THÁP HÀ NỘI TỔNG QUÁT............................. 52
§1 Tính số
()
p
Sn
trong thuật toán Frame-Stewart cho trò chơi Tháp
Hà Nội tổng quát ................................................................................... 52
§2 Đánh giá
()
p
Sn
............................................................................... 68
§3 Sự tương đương của một số thuật toán giải bài toán Tháp Hà Nội
tổng quát................................................................................................ 70
KẾT LUẬN .................................................................................................. 78
TÀI LIỆU THAM KHẢO ........................................................................... 79
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
2
LỜI NÓI ĐẦU
Trò chơi (Bài toán) Tháp Hà Nội được phổ biến rộng rãi ở Paris năm
1883 bởi nhà toán học Edouard Lucas, là một bài toán nổi tiếng thế giới, hiện
nay đang được nghiên cứu bởi rất nhiều nhà toán học và khoa học máy tính,
các chuyên gia giáo dục và y học, được đưa vào nhiều giáo trình tin học và
sách về trò chơi toán học như một ví dụ điển hình về thuật toán đệ qui và lập
trình căn bản, nhưng hình như chưa được chú ý nghiên cứu ở Việt Nam. Mặc
dù trò chơi Tháp Hà Nội có mặt trên khá nhiều trang WEB và giáo trình tiếng
Việt, số lượng bài viết tiếng Việt giới thiệu về trò chơi và bài toán Tháp Hà
Nội trên các tạp chí là rất ít và còn rất sơ lược (xem [1]-[6]), hình như chưa có
bài nghiên cứu tiếng Việt nào về bài toán Tháp Hà Nội, trong khi đó chỉ tính
riêng số bài báo nghiên cứu về bài toán Tháp Hà Nội trong lĩnh vực Toán-Tin
học đã có đến hơn 450 bài với khoảng 250 bài với đầu đề có cụm từ "The
Tower of Hanoi", đăng trên hơn 100 tạp chí khoa học uy tín (trong [5] thống
kê số lượng bài báo khoa học viết về Tháp Hà Nội là 464 bài). Đó là chưa kể
đến những bài viết về sử dụng bài toán Tháp Hà Nội trong khoa học giáo dục
và y học. Trò chơi Tháp Hà Nội thú vị đến mức nó đã được dùng làm đề tài
của một số luận án Tiến sĩ và luận văn cao học. Một hội thảo khoa học quốc
tế [21] với tên gọi Workshop on the Tower of Hanoi and Related Problems đã
được tổ chức năm 2005.
Bài toán Tháp Hà Nội không chỉ thú vị ở chỗ nó mang tên Hà Nội, thủ
đô của Việt nam, mà nó hấp dẫn các nhà Toán-Tin học bởi nó liên quan đến
nhiều vấn đề như giải thuật đệ qui, hệ đếm, tam giác Pascal, thảm Sierpinski,
lý thuyết đồ thị và chu trình Hamilton, ôtômát hữu hạn, độ phức tạp tính
toán,.... Bài toán Tháp Hà Nội gợi ý cho nhiều nghiên cứu trong khoa học
máy tính và toán học.
Luận văn Thuật toán Frame-Stewart giải bài toán Tháp Hà Nội tổng
quát có mục đích trình bày tổng quan về một thuật toán quan trọng giải bài
toán Tháp Hà Nội với số cọc bất kì.
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
3
Luận văn gồm phần mở đầu, bốn Chương và phần tài liệu tham khảo.
Chương 1. Tổng quan về trò chơi Tháp Hà Nội.
Chương 2. Bài toán Tháp Hà Nội cổ điển.
Chương 3. Bài toán Tháp Hà Nội với bốn cọc.
Chương 4. Bài toán Tháp Hà Nội tổng quát.
Chương 1 giới thiệu tổng quan về Trò chơi Tháp Hà Nội.
Lời giải Bài toán Tháp Hà Nội cho ba cọc được trình bày trong Chương 2.
Sau hơn 100 năm, trò chơi Tháp Hà Nội đã có những cải biên và tổng
quát hoá (trò chơi Tháp Hà Nội xoay vòng, trò chơi Tháp Hà Nội song song,
trò chơi Tháp Hà Nội với nhiều cọc,...). Những cải biên và tổng quát hóa này
dẫn đến những vấn đề toán học thú vị, thậm chí dẫn tới nhiều bài toán hiện
nay chưa có lời giải. Trong luận văn này, chúng tôi tập trung trình bày trong
Chương 3 và Chương 4 lời giải của bài toán Tháp Hà Nội, đó là Thuật toán đệ
qui dạng Frame-Stewart giải bài toán Tháp Hà Nội tổng quát.
Luận văn được hoàn thành dưới sự hướng dẫn tận tình của PGS.TS Tạ
Duy Phượng. Em xin bầy tỏ lòng biết ơn sâu sắc nhất đối với Thầy và xin
được cảm ơn Thầy đã cung cấp nhiều tài liệu đồng thời cho phép sử dụng Bản
thảo cuốn sách của Thầy về Tháp Hà Nội.
Em xin cảm ơn các Thầy Cô của Đại học Thái Nguyên và Viện Toán
học đã tận tình giảng dạy em trong suốt quá trình học cao học.
Tôi xin cảm ơn khoa Toán trường ĐHSP Thái Nguyên, khoa Sau Đại
học trường ĐHSP Thái Nguyên đã quan tâm giúp đỡ, tạo điều kiện thuận lợi
cho tôi thực hiện kế hoạch học tập của mình.
Xin cảm ơn người thân, đồng nghiệp, bạn bè đã cổ vũ động viên tôi trong
suốt quá trình làm luận văn.
Thái Nguyên, 19.8.2010
Nguyễn Thị Hồng Phượng