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ỘI21

§1 Trò chơi tháp Hà Nội và thuật giải đệ qui21

§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ội34

§4 Giải bài toán Tháp Hà Nội trên máy tính38

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ọc39

§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[/B52

§1 Tính số Sp (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á Sp (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át70

KẾT LUẬN78

TÀI LIỆU THAM KHẢO79