Thuật toán Tháp Hà Nội: Python, C++ Code

Tháp Hà Nội là gì?

Tháp Hà Nội là một trò chơi giải đố toán học gồm ba thanh và một chồng đĩa có kích thước giảm dần được đặt chồng lên nhau. Nó còn được biết đến với tên gọi Tháp Brahma hoặc Tháp Lucas, vì nhà toán học người Pháp Edouard Lucas đã giới thiệu nó vào năm 1883. Trò chơi giải đố này dựa trên những truyền thuyết về việc di chuyển những chiếc đĩa vàng giữa ba thanh.

Câu đố này có ba thanh và một số lượng đĩa xếp chồng lên nhau có thể thay đổi. Các thanh được sắp xếp thành các tháp tuần hoàn, do đó các đĩa lớn hơn được xếp ở dưới cùng và các đĩa nhỏ hơn được xếp ở trên cùng.

Ban đầu, chúng ta được cho ba cái chốt hoặc thanh. Một trong số đó (chốt A trong ví dụ) có tất cả các đĩa được xếp chồng lên nhau. Mục tiêu là di chuyển toàn bộ chồng đĩa từ thanh này (A) sang thanh khác (C) trong khi tuân theo một vài quy tắc cụ thể.

Đây là cách thiết lập ban đầu của câu đố:

Bài toán Tháp Hà Nội

Và đây là mục tiêu cuối cùng:

Quy định của Tháp Hà Nội

Dưới đây là những quy tắc cơ bản của trò chơi Tháp Hà Nội:

• Ở trạng thái ban đầu của câu đố, tất cả các đĩa đều được xếp chồng lên thanh thứ nhất.
• Ở trạng thái cuối cùng, tất cả các đĩa từ thanh thứ nhất được xếp chồng lên thanh thứ hai hoặc thanh thứ ba.
• Tại một thời điểm, chỉ có một đĩa có thể di chuyển từ thanh này sang thanh khác.
• Chỉ có đĩa trên cùng trên thanh mới có thể di chuyển được.
• Không thể đặt một đĩa lên trên một đĩa nhỏ hơn.

Truyền thuyết gốc kể về việc di chuyển 64 quân cờ. Các thầy tu chỉ được phép di chuyển từng quân cờ một theo luật chơi. Theo truyền thuyết, có một lời tiên tri rằng thế giới sẽ diệt vong nếu họ hoàn thành được việc này. Trong phần độ phức tạp về thời gian, chúng ta sẽ chứng minh rằng một tháp Hà Nội với n quân cờ cần 2^n – 1 nước đi.

Vì vậy, nếu các thầy tế cần 1 giây để di chuyển một chiếc đĩa, tổng thời gian để giải câu đố sẽ là 2^64 – 1 giây, hay xấp xỉ 584,942,417,356 năm, 26 ngày, 7 giờ và 15 giây.

Thuật toán Tháp Hà Nội

Cách phổ biến nhất để giải Tháp Hà Nội là sử dụng thuật toán đệ quy. Đầu tiên, ta chọn hai thanh làm điểm xuất phát và điểm đích; thanh còn lại đóng vai trò là thanh phụ trợ.

Dưới đây là các bước giải câu đố Tháp Hà Nội:

• Di chuyển n-1 đĩa trên cùng từ chốt nguồn sang chốt trợ giúp.
• Di chuyển đĩa thứ n từ vị trí nguồn đến vị trí đích.
• Di chuyển n-1 đĩa còn lại từ vị trí hỗ trợ đến vị trí đích.

Lưu ý: Nếu chỉ có một ổ đĩa duy nhất, chúng ta có thể di chuyển nó trực tiếp từ nguồn đến đích.

Cách giải câu đố Tháp Hà Nội

Chúng ta hãy minh họa thuật toán cho ba đĩa. Coi chốt A là nguồn, chốt B là bộ hỗ trợ và chốt C là đích đến.

Bước 1) Ban đầu, tất cả các đĩa được xếp chồng lên nhau trên cọc A.

Ở giai đoạn này: Nguồn = Cọc A, Đích = Cọc C, Cọc hỗ trợ = Cọc B.

Bây giờ, chúng ta cần di chuyển n-1 đĩa hàng đầu từ nguồn sang trợ giúp.

Lưu ý: Mặc dù chúng ta chỉ có thể di chuyển một đĩa tại một thời điểm, bước này giúp giảm bài toán 3 đĩa xuống còn bài toán 2 đĩa, được xử lý bằng một lời gọi đệ quy.

Bước 2) Khi thực hiện cuộc gọi đệ quy từ chốt A với chốt B là đích đến, ta sử dụng chốt C làm công cụ hỗ trợ.

Hãy lưu ý rằng chúng ta quay lại giai đoạn một của bài toán Tháp Hà Nội, nhưng lần này là với hai đĩa. Chúng ta di chuyển n-1 (tức là một) đĩa từ nguồn đến đĩa hỗ trợ, đĩa hỗ trợ này sẽ di chuyển đĩa nhỏ nhất từ ​​cọc A đến cọc C.

Ở giai đoạn này: Nguồn = cọc A, Đích = cọc B, Cọc hỗ trợ = cọc C.

Bước 3) Theo thuật toán, đĩa thứ n (thứ 2) hiện được chuyển đến đích, cọc B.

Ở giai đoạn này: Nguồn = cọc A, Đích = cọc B, Cọc hỗ trợ = cọc C.

Bước 4) Bây giờ, chúng ta di chuyển đĩa n-1 (đĩa thứ nhất) từ chốt hỗ trợ C đến chốt đích B, theo giai đoạn thứ ba của thuật toán.

Ở giai đoạn này: Nguồn = cọc A, Đích = cọc B, Cọc hỗ trợ = cọc C.

Bước 5) Sau khi hoàn thành lời gọi đệ quy, chúng ta quay trở lại thiết lập trước đó ở giai đoạn đầu tiên của thuật toán.

Bước 6) Ở giai đoạn thứ hai, chúng ta di chuyển đĩa 3 từ điểm neo nguồn A đến điểm neo đích C.

Ở giai đoạn này: Nguồn = cọc A, Đích = cọc C, Cọc hỗ trợ = cọc B.

Bước 7) Nhiệm vụ tiếp theo là di chuyển các đĩa còn lại từ vị trí hỗ trợ (cọc B) đến vị trí đích (cọc C). Lần này, chúng ta sẽ sử dụng vị trí nguồn ban đầu (cọc A) làm vị trí hỗ trợ.

Bước 8) Vì chúng ta không thể di chuyển hai đĩa cùng một lúc, nên chúng ta thực hiện một lời gọi đệ quy cho đĩa 1. Theo như chúng ta... thuật toánĐiểm đến trong bước này là cọc A.

Ở giai đoạn này: Nguồn = cọc B, Đích = cọc A, Cọc hỗ trợ = cọc C.

Bước 9) Lời gọi đệ quy của chúng ta đã hoàn tất. Bây giờ chúng ta di chuyển đĩa 2 từ vị trí nguồn đến vị trí đích.

Ở giai đoạn này: Nguồn = cọc B, Đích = cọc C, Cọc hỗ trợ = cọc A.

Bước 10) Chúng ta hoàn tất bằng cách di chuyển đĩa n-1 còn lại (đĩa 1) từ máy hỗ trợ sang máy đích.

Ở giai đoạn này: Nguồn = cọc A, Đích = cọc C, Cọc hỗ trợ = cọc B.

Biệt danh Code cho Tháp Hà Nội

START
Procedure Tower_Of_Hanoi(disk, source, dest, helper)
    IF disk == 1 THEN
        move disk from source to dest
    ELSE
        Tower_Of_Hanoi(disk - 1, source, helper, dest)
        move disk from source to dest
        Tower_Of_Hanoi(disk - 1, helper, dest, source)
    END IF
END Procedure

Mã chương trình trong C++

#include <bits/stdc++.h>
using namespace std;
void tower_of_hanoi(int num, string source, string dest, string helper) {
    if (num == 1) {
        cout << " Move disk 1 from tower " << source << " to tower " << dest << endl;
        return;
    }
    tower_of_hanoi(num - 1, source, helper, dest);
    cout << " Move disk " << num << " from tower " << source << " to tower " << dest << endl;
    tower_of_hanoi(num - 1, helper, dest, source);
}
int main() {
    int num;
    cin >> num;
    printf("The sequence of moves :\n");
    tower_of_hanoi(num, "I", "III", "II");
    return 0;
}

Đầu ra:

3
The sequence of moves :
Move disk 1 from tower I to tower III
Move disk 2 from tower I to tower II
Move disk 1 from tower III to tower II
Move disk 3 from tower I to tower III
Move disk 1 from tower II to tower I
Move disk 2 from tower II to tower III
Move disk 1 from tower I to tower III

Mã chương trình trong Python

def tower_of_hanoi(n, source, destination, helper):
    if n == 1:
        print("Move disk 1 from peg", source, "to peg", destination)
        return
    tower_of_hanoi(n - 1, source, helper, destination)
    print("Move disk", n, "from peg", source, "to peg", destination)
    tower_of_hanoi(n - 1, helper, destination, source)
# n = number of disks
n = 3
tower_of_hanoi(n, 'A', 'B', 'C')

Đầu ra:

Move disk 1 from peg A to peg B
Move disk 2 from peg A to peg C
Move disk 1 from peg B to peg C
Move disk 3 from peg A to peg B
Move disk 1 from peg C to peg A
Move disk 2 from peg C to peg B
Move disk 1 from peg A to peg B

Sự phức tạp của Tháp Hà Nội

Dưới đây là độ phức tạp về thời gian và không gian của Tháp Hà Nội:

1) Độ phức tạp về thời gian:

Nhìn lại thuật toán, chúng ta thực hiện một lời gọi đệ quy cho (n-1) đĩa hai lần mỗi lần gọi. Mỗi (n-1) lời gọi đệ quy được chia thành ((n-1)-1) lời gọi đệ quy, và cứ thế tiếp tục cho đến khi chúng ta đạt đến trường hợp cơ sở một đĩa.

Dành cho ba đĩa:

• Đĩa 3 gọi hàm đệ quy của đĩa 2 hai lần.
• Đĩa 2 gọi hàm đệ quy của đĩa 1 hai lần.
• Đĩa 1 di chuyển với thời gian không đổi, cho phép có đủ thời gian để giải bài toán cho ba đĩa.

Được biểu diễn dưới dạng công thức lặp lại:

= 2 × (Thời gian giải cho hai đĩa) + thời gian không đổi để di chuyển đĩa 3

= 2 × (2 × thời gian giải cho một đĩa + thời gian không đổi để di chuyển đĩa 2) + thời gian không đổi để di chuyển đĩa 3

= (2 × 2) × thời gian không đổi để di chuyển đĩa 1 + 2 × thời gian không đổi để di chuyển đĩa 2 + thời gian không đổi để di chuyển đĩa 3

Với n đĩa, điều này trở thành:

2^n-1 × thời gian không đổi để di chuyển đĩa 1 + 2^n-2 × thời gian không đổi để di chuyển đĩa 2 + ….

Cấp số nhân này có tổng là O(2)ⁿ – 1), được đơn giản hóa thành O(2ⁿ), độ phức tạp thời gian theo cấp số mũ.

2) Độ phức tạp về không gian:

Độ phức tạp không gian của Tháp Hà Nội là O(n). Đệ quy sử dụng ngăn xếp gọi hàm, và độ sâu tối đa của ngăn xếp bằng n, số đĩa. Đó là lý do tại sao độ phức tạp không gian là O(n).

Câu Hỏi Thường Gặp