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

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....
Nội dung trích xuất từ tài liệu:
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 ĐẠ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 - 2010Số 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 - 2010Số 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 TrangMỤC LỤCLỜI NÓI ĐẦU ............................................................................................... 2Chương 1 ....................................................................................................... 4TỔ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 ................................................................ 15Chươ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 ........................................... 38Chương 3: BÀI TOÁN THÁP HÀ NỘI VỚI BỐN CỌC (Trò chơiReve-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...... 43Chương 4: BÀI TOÁN THÁP HÀ NỘI TỔNG QUÁT............................. 52 §1 Tính số S p (n) trong thuật toán Frame-Stewart cho trò chơi Tháp Hà Nội tổng quát ................................................................................... 52 §2 Đánh giá S p (n) ............................................................................... 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................................................................................................ 70KẾT LUẬN .................................................................................................. 78TÀI LIỆU THAM KHẢO........................................................................... 79Số 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ăm1883 bởi nhà toán học Edouard Lucas, là một bài toán nổi tiếng thế giới, hiệnnay đ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ậptrình căn bản, nhưng hình như chưa được chú ý nghiên cứu ở Việt Nam. Mặcdù trò chơi Tháp Hà Nội có mặt trên khá nhiều trang WEB và giáo trình tiếngViệ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ínhriê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-Tinhọc đã có đến hơn 450 bài với khoảng 250 bài với đầu đề có cụm từ TheTower of Hanoi, đăng trên hơn 100 tạp chí khoa học uy tín (trong [5] thốngkê 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ụcvà y học. Trò chơi Tháp Hà Nội thú vị đến mức nó đã được dùng làm đề tàicủ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ốctế [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 đếnnhiề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ínhtoán,.... Bài toán Tháp Hà Nội gợi ý cho nhiều nghiên cứu trong khoa họcmá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ổngquá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àitoá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 q ...