Cấu trúc dữ liệu & thuật toán - 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ả -

Các vòng này có kích thước khác nhau và được xếp chồng lên nhau theo thứ tự tăng dần, tức là vòng nhỏ hơn so với vòng 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ố lượng tháp vẫn giữ nguyên.

Quy tắc

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

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

Sau đây là một đại diện hoạt hình giải một câu đố Tháp Hà Nội với ba đĩa.

Câu đố của tháp Hà Nội với n đĩa có thể được giải trong tối thiểu 2 ⁿ −1 bước. Bài thuyết trình này cho thấy một câu đố với 3 đĩa đã thực hiện 2 ³ - 1 = 7 bước.

Thuật toán

Để viết một thuật toán cho Tháp Hà Nội, trước hết chúng ta cần phải học cách để giải quyết vấn đề này với số tiền ít hơn đĩa ghi tiếng, nói → 1 hoặc 2. Chúng tôi đánh dấu ba tháp với tên, nguồn , đích đến và aux (chỉ để giúp đỡ di chuyển đĩa ). Nếu chúng ta chỉ có một đĩa, thì nó có thể dễ dàng được chuyển từ nguồn sang chốt đích.

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

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

Vì vậy, bây giờ, chúng tôi đang ở một vị trí để thiết kế một thuật toán cho Tháp Hà Nội 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 khác (n-1) 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 n từ nguồn đến đích và sau đó đặt tất cả các đĩa (n1) khác vào đó. Chúng ta có thể tưởng tượng để áp dụng tương tự theo cách đệ quy cho tất cả các bộ đĩa đã cho.

Các bước để làm theo 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 Tháp Hà Nội có thể được điều khiển 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

Được cập nhật: hôm kia lúc 2:26:15 | Lượt xem: 555