Cấu trúc dữ liệu & Giải thuật - Tháp Hà Nội

Tháp Hà Nội, là một câu đố toán học bao gồm ba tháp (chốt) và nhiều hơn một vòng được mô tả -

Những chiếc nhẫn này có kích thước khác nhau và xếp chồng lên nhau theo thứ tự tăng dần, tức là chiếc nhỏ hơn nằm trên chiếc lớn hơn. Có những biến thể khác của câu đố trong đó số lượng đĩa tăng lên, nhưng số tháp vẫn giữ nguyên.

Quy tắc

Nhiệm vụ là di chuyển tất cả các đĩa đến một số tháp khác mà không vi phạm trình tự sắp xếp. Một số quy tắc cần tuân thủ đối với Tháp Hà Nội là:

• Chỉ có thể di chuyển một đĩa giữa các tháp vào bất kỳ thời điểm nào.
• Chỉ đĩa "trên cùng" mới có thể được gỡ bỏ.
• Không có đĩa lớn nào có thể đè lên đĩa nhỏ.

Sau đây là mô tả hoạt hình giải câu đố Tháp Hà Nội bằng ba đĩa.

Câu đố Tháp Hà Nội với tối thiểu n đĩa có thể giải được 2ⁿ−1các bước. Phần trình bày này cho thấy rằng một câu đố có 3 đĩa đã được2³ - 1 = 7 các bước.

Thuật toán

Để viết một thuật toán cho Tower of Hanoi, trước tiên chúng ta cần học cách giải bài toán này với số lượng đĩa ít hơn, chẳng hạn → 1 hoặc 2. Chúng ta đánh dấu ba tháp bằng tên, source, destination và aux(chỉ để giúp di chuyển các đĩa). Nếu chúng ta chỉ có một đĩa, thì nó có thể dễ dàng được di chuyển từ nguồn đến chốt đích.

Nếu chúng ta có 2 đĩa -

• Đầu tiên, chúng ta di chuyển đĩa nhỏ hơn (trên cùng) sang aux peg.
• Sau đó, chúng tôi di chuyển đĩa lớn hơn (dưới cùng) đến chốt đích.
• Và cuối cùng, chúng tôi di chuyển đĩa nhỏ hơn từ aux đến chốt đích.

Vì vậy, bây giờ, chúng tôi đang ở vị trí để thiết kế một thuật toán cho Tower of Hanoi với hơn hai đĩa. Chúng tôi chia chồng đĩa thành hai phần. Đĩa lớn nhất (đĩa ^thứ n ) nằm trong một phần và tất cả các đĩa (n-1) khác nằm trong phần thứ hai.

Mục đích cuối cùng của chúng tôi là di chuyển đĩa ntừ nguồn đến đích và sau đó đặt tất cả (n1) đĩa khác vào đó. Chúng ta có thể tưởng tượng để áp dụng giống nhau theo cách đệ quy cho tất cả các bộ đĩa đã cho.

Các bước cần thực hiện là -

Step 1 − Move n-1 disks from source to aux
Step 2 − Move nth disk from source to dest
Step 3 − Move n-1 disks from aux to dest

Một thuật toán đệ quy cho Tower of Hanoi có thể được sử dụng như sau:

START
Procedure Hanoi(disk, source, dest, aux)

   IF disk == 1, THEN
      move disk from source to dest             
   ELSE
      Hanoi(disk - 1, source, aux, dest)     // Step 1
      move disk from source to dest          // Step 2
      Hanoi(disk - 1, aux, dest, source)     // Step 3
   END IF
   
END Procedure
STOP

Để kiểm tra việc thực hiện trong lập trình C, hãy nhấp vào đây .