Bài toán Tháp Hà Nội (Tower of Hanoi)
Tháp Hà Nội (Tower of Hanoi) là gì?
Bài toán Tháp Hà Nội (Tower of Hanoi) là một trò chơi toán học bao gồm 3 cột và với số đĩa nhiều hơn 1.
Dưới đây là hình minh họa bài toán Tháp Hà Nội (Tower of Hanoi) với trường hợp có 3 đĩa.
Các đĩa có kích cỡ khác nhau và xếp theo tự tự tăng dần về kích cỡ từ trên xuống: đĩa nhỏ hơn ở trên đĩa lớn hơn. Với số đĩa khác nhau thì ta có các bài toán Tháp Hà Nội (Tower of Hanoi) khác nhau, tuy nhiên lời giải cho các bài toán này là tương tự nhau. Lời giải tối ưu cho bài toán Tháp Hà Nội (Tower of Hanoi) là khi trò chơi chỉ có 3 cọc. Với số cọc lớn hơn thì lời giải bài toán vẫn chưa được khẳng định.
Qui tắc trò chơi toán học Tháp Hà Nội (Tower of Hanoi)
Nhiệm vụ của trò chơi là di chuyển các đĩa có kích cỡ khác nhau sang cột khác sao cho vẫn đảm bảo thứ tự ban đầu của các đĩa: đĩa nhỏ nằm trên đĩa lớn. Dưới đây là một số qui tắc cho trò chơi toán học Tháp Hà Nội (Tower of Hanoi):
Mỗi lần chỉ có thể di chuyển một đĩa từ cột này sang cột khác.
Chỉ được di chuyển đĩa nằm trên cùng (không được di chuyển các đĩa nằm giữa).
Đĩa có kích thước lớn hơn không thể được đặt trên đĩa có kích thước nhỏ hơn.
Dưới đây là hình minh họa cách giải bài toán Tháp Hà Nội (Tower of Hanoi) với trường hợp có 3 đĩa.
Bài toán Tháp Hà Nội (Tower of Hanoi) với số đĩa là n có thể được giải với số bước tối thiểu là 2n−1
. Do đó, với trường hợp 3 đĩa, bài toán Tháp Hà Nội (Tower of Hanoi) có thể được giải sau 23−1 = 7
bước.
Giải thuật cho bài toán Tháp Hà Nội (Tower of Hanoi)
Để viết giải thuật cho trò chơi toán học Tháp Hà Nội (Tower of Hanoi), đầu tiên chúng ta cần tìm hiểu cách giải bài toán với số đĩa là 1 và 2. Chúng ta gán 3 cột với các tên là:
cotNguon: cột ban đầu chứa các đĩa
cotDich: cột cần di chuyển các đĩa tới
cotTrungGian: cột trung gian có mục đích làm trung gian trong quá trình di chuyển đĩa
Nếu chỉ có 1 đĩa, chúng ta chỉ cần di chuyển từ cotNguon tới cotDich.
Nếu có 2 đĩa:
Đầu tiên chúng ta di chuyển đĩa trên cùng (đĩa nhỏ nhất) tới cotTrungGian.
Sau đó chúng ta di chuyển đĩa ở dưới cùng (đĩa to hơn) tới cotDich.
Và cuối cùng di chuyển đĩa nhỏ nhất từ cotTrungGian về cotDich.
Từ hai giải thuật phần giải thuật trên chúng ta sẽ có giải thuật cho bài toán Tháp Hà Nội (Tower of Hanoi) cho 3 đĩa trở lên. Chúng ta chia ngăn xếp các đĩa thành hai phần: đĩa thứ lớn nhất (đĩa thứ n) là phần thứ nhất và (n-1) đĩa còn lại là phần thứ hai.
Mục đích của chúng ta là di chuyển đĩa thứ n từ cotNguon tới cotDich và sau đó đặt tất cả (n-1) đĩa còn lại lên trên nó. Bây giờ chúng ta có thể tưởng tượng ra cách giải bài toán trên dựa vào đệ qui theo các bước sau:
Bước 1: Di chuyển n-1 đĩa từ cotNguon tới cotTrungGian Bước 2: Di chuyển đĩa thứ n từ cotNguon tới cotDich Bước 3: Di chuyển n-1 đĩa từ cotTrungGian về cotDich
Giải thuật đệ qui cho bài toán Tháp Hà Nội (Tower of Hanoi) là:
Bắt đầu giải thuật Tháp Hà nội Hanoi(disk, cotNguon, cotDich, cotTrungGian) IF disk == 0, thì di chuyển đĩa từ cotNguon tới cotDich ELSE Hanoi(disk - 1, cotNguon, cotTrungGian, cotDich) // Bước 1 di chuyển đĩa từ cotNguon tới cotDich // Bước 2 Hanoi(disk - 1, cotTrungGian, cotDich, cotNguon) // Bước 3 Kết thúc IF Kết thúc giải thuật
Theo Tutorialspoint
Bài trước: Khái niệm cơ bản về đệ qui (Recursion)
Bài tiếp: Dãy Fibonacci trong Cấu trúc dữ liệu và giải thuật
Bạn nên đọc
Theo Nghị định 147/2024/ND-CP, bạn cần xác thực tài khoản trước khi sử dụng tính năng này. Chúng tôi sẽ gửi mã xác thực qua SMS hoặc Zalo tới số điện thoại mà bạn nhập dưới đây:

- Code NgầuThích · Phản hồi · 6 · 17/08/20

Cũ vẫn chất
-
20+ cách giải phóng RAM trên máy tính Windows 10, reset RAM Win 10 đơn giản nhất
Hôm qua -
Cách tải toàn bộ Playlist Video trên Youtube
Hôm qua -
Số thập phân là gì? Các phép tính với số thập phân
Hôm qua -
Hàng ngày hay hằng ngày? Khi nào dùng 'hàng ngày', khi nào dùng 'hằng ngày'
Hôm qua -
Trực tâm là gì? Xác định trực tâm trong tam giác
Hôm qua 1 -
Cách cài đặt Python trên Windows, macOS, Linux
Hôm qua -
Cách đánh số trang bỏ trang đầu, đánh số từ trang bất kỳ trong Word chi tiết nhất
Hôm qua -
Cách xóa tài khoản Facebook vĩnh viễn trên điện thoại, máy tính
Hôm qua -
Những câu nói cà khịa người yêu cũ, stt cà khịa người yêu cũ bá đạo
Hôm qua 2 -
Cách giả lập CASIO FX-580VN X trên máy tính, điện thoại
Hôm qua 1