Tháp Hà Nội (tiếng Pháp là Tuerme Von Hanoi, hay Hanoi Towers,
Tower Of Hanoi theo tiếng Anh) là một trò chơi giải đố toán học gồm một
bộ các đĩa kích thước khác nhau, có lỗ ở giữa, nằm xuyên trên ba cái
cọc.
Dạng thường gặp nhất của trò chơi này gồm một bộ các đĩa kích thước khác nhau, có lỗ ở giữa, nằm xuyên trên ba cái cọc. Bài toán đố bắt đầu bằng cách sắp xếp các đĩa theo trật tự kích thước vào một cọc sao cho đĩa nhỏ nhất nằm trên cùng, tức là tạo ra một dạng hình nón. Yêu cầu của trò chơi là di chuyển toàn bộ số đĩa sang một cọc khác, tuân theo các quy tắc sau:
Tháp Hà Nội có độ khó tăng theo số đĩa. Với hai đĩa, chỉ cần ba lần di chuyển để hoàn thành trò chơi. Con số tương ứng là 3 đĩa – 7 lần (hình trên), 4 đĩa – 15 lần, 5 đĩa – 31 lần, 5 đĩa – 63 lần, 7 đĩa – 127 lần, 8 đĩa – 255 lần… Nếu số đĩa là 64 thì số lần di chuyển là 18.446.744.073.709.551.615 lần. Nếu mỗi lần di chuyển mất một giây thì việc hoàn thành trò chơi mất tới... 5 tỷ thế kỷ.
Trong thế kỷ 20, quy luật của trò chơi Tháp Hà Nội đã được các nhà toán học nghiên cứu, và trở thành cơ sở về phương pháp giải đệ quy kinh điển. Trong tin học, Tháp Hà Nội là một bài toán thường được dùng để dạy về lập trình cơ bản. Nó xuất hiện trong nhiều ngôn ngữ lập trình khác nhau như Emacs, Prolog.
Bài toán Tháp Hà Nội còn được dùng trong nghiên cứu tâm lý về cách giải quyết vấn đề, cũng như trong chuẩn đoán và điều trị thần kinh tâm lý đối với các chức năng thực hành.
Phía dưới là phiên bản trò chơi Tháp Hà Nội trên máy tính, bạn có thể tùy chọn số đĩa lên nhiều nhất là 8 đĩa.
Dạng thường gặp nhất của trò chơi này gồm một bộ các đĩa kích thước khác nhau, có lỗ ở giữa, nằm xuyên trên ba cái cọc. Bài toán đố bắt đầu bằng cách sắp xếp các đĩa theo trật tự kích thước vào một cọc sao cho đĩa nhỏ nhất nằm trên cùng, tức là tạo ra một dạng hình nón. Yêu cầu của trò chơi là di chuyển toàn bộ số đĩa sang một cọc khác, tuân theo các quy tắc sau:
- Chỉ có 3 cột để di chuyển.
- Một lần chỉ được di chuyển một đĩa (không được di chuyển đĩa nằm giữa).
- Một đĩa chỉ có thể được đặt lên một đĩa lớn hơn (không nhất thiết hai đĩa này phải có kích thước liền kề, tức là đĩa nhỏ nhất có thể nằm trên đĩa lớn nhất).
Tháp Hà Nội có độ khó tăng theo số đĩa. Với hai đĩa, chỉ cần ba lần di chuyển để hoàn thành trò chơi. Con số tương ứng là 3 đĩa – 7 lần (hình trên), 4 đĩa – 15 lần, 5 đĩa – 31 lần, 5 đĩa – 63 lần, 7 đĩa – 127 lần, 8 đĩa – 255 lần… Nếu số đĩa là 64 thì số lần di chuyển là 18.446.744.073.709.551.615 lần. Nếu mỗi lần di chuyển mất một giây thì việc hoàn thành trò chơi mất tới... 5 tỷ thế kỷ.
Trong thế kỷ 20, quy luật của trò chơi Tháp Hà Nội đã được các nhà toán học nghiên cứu, và trở thành cơ sở về phương pháp giải đệ quy kinh điển. Trong tin học, Tháp Hà Nội là một bài toán thường được dùng để dạy về lập trình cơ bản. Nó xuất hiện trong nhiều ngôn ngữ lập trình khác nhau như Emacs, Prolog.
Bài toán Tháp Hà Nội còn được dùng trong nghiên cứu tâm lý về cách giải quyết vấn đề, cũng như trong chuẩn đoán và điều trị thần kinh tâm lý đối với các chức năng thực hành.
Phía dưới là phiên bản trò chơi Tháp Hà Nội trên máy tính, bạn có thể tùy chọn số đĩa lên nhiều nhất là 8 đĩa.
0 nhận xét:
Đăng nhận xét