Source tham khảo
| AutoIt | http://pastebin.com/Zkk6Xsx3 |
|---|---|
| C++ | http://pastebin.com/90hpgPV6 |
Giới thiệu
Tháp Hà Nội là một trò chơi toán học du nhập vào Việt Nam lần đầu năm 1883, nó nhanh chóng trở thành một trò chơi logic kinh điển thú vị, ngoài ra, tháp Hà Nội còn có ý nghĩa trong nhiều lĩnh vực khác, điển hình là Toán học và Tin học, tháp Hà Nội là một bài toán đệ quy siêu kinh điển.
Luật chơi tháp Hà Nội khá đơn giản, có ba cột A, B và C cùng n đĩa được đặt trên cột A xếp chồng lên nhau. Nhiệm vụ duy nhất của người chơi là di chuyển toàn bộ số đĩa từ cột A sang cột C, với điều kiện mỗi lần chỉ được di chuyển 1 đĩa ở trên cùng, và khi đặt đĩa vào cột khác phải đảm bảo sao cho đĩa nhỏ luôn nằm trên đĩa lớn hơn (không phân biệt thứ tự).
Mẹo chơi
Chính vì sự phổ biến và tính logic, nó nhanh chóng trở thành một bài toán và những quy luật.Có một mẹo chơi như sau, xét số n đĩa, nếu n là chỗ chẵn thì liên tục di chuyển lần lượt các đĩa 1 tới đĩa n sang cột bên phải (thuận chiều kim đồng hồ), ngược lại nếu n lẻ thì liên tục di chuyển sang cột bên trái cho đến khi hoàn tất (nghịch chiều kim đồng hồ).
Ví dụ quá trình di chuyển 2 đĩa (n = 2 là chẵn nên di chuyển từng đĩa liên tục sang cột bên phải thuận chiều kim đồng hồ)
Đối với trường hợp chuyển 3 đĩa (n = 3 là lẻ nên di chuyển từng đĩa liên tục sang cột bên trái nghịch chiều kim đồng hồ)
Thuật toán đệ quy
Để giải trên máy tính, người ta đưa nó thành một bài toán đệ quy. Và để có thể hiểu và đệ quy được bài toán này, ta cùng xét một số trường hợp sau, ta gọi n là số đĩa có trong bài toán và a, b, c là ba cột cho trước:1. Đối với trường hợp n = 1: ta di chuyển thẳng đĩa n từ cột nguồn sang cột đích
2. Đối với trường hợp n = 2: ta di chuyển
- Đĩa 1 từ cột nguồn (a) sang cột trung gian (b)
- Đĩa 2 từ cột nguồn (a) sang cột đích (c)
- Đĩa 1 từ cột trung gian (c) sang cột đích (c)
3. Đối với trường hợp n = 3: ta di chuyển
- Đĩa 1 và 2 từ cột nguồn (a) sang cột trung gian (b)
- Đĩa 3 sang cột đích (c)
- Đĩa 1 và 2 từ cột trung gian (b) sang cột đích (d)
Và ở trường hợp 3, ta xuất hiện một bài toán nhỏ hơn trong bài toán lớn 3 đĩa, đó là di chuyển 2 đĩa từ cột nguồn (a) sang cột trung gian (b).
Hệ quy chiếu lúc này thay đổi. Đối với đĩa 1 và 2 lúc này, cột nguồn là cột (a), cột đích là cột (b) và cột còn lại là cột trung gian. Lúc này ta chỉ việc ứng dụng là trường hợp 2 mà thôi.
Như vậy có thể thấy rõ mối quan hệ của bài toán, trong một bài toán lớn, có 1 bài toán nhỏ hơn và trong bài toán nhỏ hơn, có các bài toán nhỏ hơn nữa. Vì vậy chúng ta sử dụng đệ quy để giải quyết bài toán này như sau:
- Nếu n = 1 thì di chuyển đĩa n từ cột nguồn đến cột đích
- Nếu n > 1 thì:
+ Di chuyển n-1 đĩa từ cột nguồn sang cột trung gian
+ Di chuyển đĩa n từ cột nguồn sang cột đích
+ Di chuyển n-1 đĩa từ cột trung gian sang cột đích
2 nhận xét
nhận xétTìm mãi không thấy nút +1 đâu ạ :) hay lắm a
ReplyThế thì bạn share hộ mình cũng đc ạ
ReplyTks bạn ^^