Thạc Sĩ Bài toán tháp Hà Nội với chuyển động xoay vòng

2

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/



MỤC LỤC

Trang
Mục lục . 1
Lời nói đầu . 2
Chương 1 Một số cải biên của bài toán Tháp Hà Nội 4
1.1 Lịch sử bài toánTháp Hà Nội . 4
1.2 Một số phát triển và cải biên của bài toán Tháp Hà Nội .
1.3 Tài liệu về bài toán Tháp Hà Nội .
15
26
Chương 2 Bài toán Tháp Hà Nội với chuyển động xoay vòng . 28
2.1 Các tính chất cơ bản của bài toán Tháp Hà Nội xoay vòng 28
2.2 Thuật toán lặp cho bài toán Tháp Hà Nội xoay vòng . 45
2.3 Bài toán Tháp Hà Nội với hạn chế chuyển động các đĩa 52
Kết luận 64
Tài liệu tham khảo 65



3

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/



LỜI NÓI ĐẦU
Bài toánTháp Hà Nộiđược nhà toán họcPháp EdouardLucas nghĩ ra năm 1882
(xem [17]) và phổ biếnvào năm 1883dưới dạng một trò chơi, là một bài toán
thường được giới thiệu trong các sách về các trò chơi toán học và sử dụng
trong các giáo trình Tin học như một ví dụ điển hình về thuật giải đệ qui, lập
trình căn bản và độ phức tạp tính toán.
Trò chơi Tháp Hà Nộikhông chỉ thú vị ở chỗ nó mang tên Hà Nội, thủ đô của
Việt Nam mà nó còn hấp dẫn các nhà nghiên cứu Toán học và Công nghệ
thông tin bởi nó liên quan đến nhiều vấn đề của Toán – Tin học như giải thuật
đệ qui, hệ đếm, tam giác Pascal, thảm Sierpinski, Fractal, lý thuyết đồ thị và
chu trình Hamilton, ôtômát hữu hạn, độ phức tạp tính toán, . Các bài toán
Tháp Hà Nộimở rộng hoặc cải biên gợi ý cho nhiều nghiên cứu mới trong
toán học và khoa học máy tính.
Đã có hai cuốn sách chuyên khảo đầu tiênviết về Bài toán Tháp Hà Nội:The
Tower of Hanoi –Myths and Maths[16]của Andreas M. Hinz, Sandi Klavžar,
Uroš Milutinović, Ciril Petrxuất bản năm 2013 và cuốn sách hai tập Classical
Tower of Hanoi Problem and Its Generalizations[18] của A.A.K. Majumdar
xuất bản năm 2012 – 2013.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 học và Tin học đã có đến gần 500 bài với
khoảng 250 bài với đầu đề có cụm từ "The Tower of Hanoi", đăng trên gần
200 tạp chí khoa học có uy tín(xem thống kê Tài liệu trong [7], [16] và [22],
tiếc rằng hình như chưa có bài nghiên cứu nào của người Việt Nam về bài
toán Tháp Hà Nộ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,sinh – y học hoặc những cuốn sách về
tin học hay toán trò chơi, trong đó có trình bày về trò chơi Tháp Hà Nội. 4

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/


Sau hơn 100 năm, bài toánTháp Hà Nội đã có những cải biên và tổng quát hóa
(trò chơi Tháp Hà Nội với nhiều cọc, trò chơi Tháp Hà Nội với các đĩa màu,
trò chơi Tháp Hà Nội với hạn chế hướng chuyển đĩa, trò chơi Tháp Hà Nội
song song, .). 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.
Dựa trên các bài báo của các tác giả nước ngoài, Luận văn Bài toán Tháp Hà
Nội với chuyển động xoay vòngcó mục đích trình bày các tính chất cơ bản của
bài toán Tháp Hà Nộivới hạn chế đặt lên chuyển động – một biến thể của bài
toán Tháp Hà Nội,đặc biệt là mô tả giải thuật lặp để giải quyết bài toánTháp
Hà Nội xoay vòng.
Luận văn gồm Phần mở đầu, hai chương và Tài liệu tham khảo.
Chương 1Một số cải biên của bài toánTháp Hà Nội
Chương 1 giới thiệu tổng quan về lịch sử phát triển trò chơi Tháp Hà Nội và
một số biến thể của bài toán. Các tư liệu trong Chương này được bổ sung chi
tiết và thời sự hơn so với [3] và [5].
Chương 2Bài toán Tháp Hà Nội với chuyển động xoay vòng
Chương 2trình bày các tính chất,lời giải bài toán bằng giải thuật lặp của bài
toán Tháp Hà Nộivới chuyển động xoay vòng.
Luận văn được hoàn thành dưới sự hướng dẫn tận tìnhcủa PGS TS Tạ Duy
Phượng, Viện Toán học. Đặc biệt Thầy đã cung cấp nhiều tài liệu và biên tập
kĩ luận văn. Em xin bày tỏ lòng biết ơn sâu sắc nhất đối với Thầy.
Tôi xin được cảm ơn khoa Toán – Tin trường Đại học Khoa học – Đại học
Thái Nguyên và Trường Trung học Phổ thông Hòn Gai –Thành phốHạLong
đã 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.
Xin được 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 học cao học và làm luận văn.