数据结构与算法 - 河内塔

河内塔是一个数学难题，由三座塔（钉子）和多个环组成，如图所示 -

河内塔

这些环大小不同，并按升序堆叠，即较小的环位于较大的环之上。该谜题还有其他变体，其中圆盘数量增加，但塔数保持不变。

规则

任务是将所有圆盘移动到另一个塔而不违反排列顺序。河内塔需要遵循的一些规则是 -

  • 在任何给定时间，只能在塔之间移动一个圆盘。
  • 只能移除“顶部”磁盘。
  • 没有大磁盘可以位于小磁盘之上。

以下是用三个圆盘解决河内塔谜题的动画演示。

河内塔

具有 n 个圆盘的汉诺塔谜题可以通过最少2 n −1步来解决。该演示显示，一个包含 3 个圆盘的拼图需要2 3 - 1 = 7 个步骤。

算法

要为河内塔编写算法，首先我们需要学习如何用更少的磁盘来解决这个问题，比如 → 1 或 2。我们用 name、 source、destination和aux标记三个塔（只是为了帮助移动磁盘）。如果我们只有一个磁盘，那么可以轻松地将其从源桩移动到目标桩。

如果我们有 2 个磁盘 -

  • 首先，我们将较小的（顶部）磁盘移动到辅助挂钩。
  • 然后，我们将较大（底部）的磁盘移动到目标挂钩。
  • 最后，我们将较小的磁盘从 aux 移动到目标挂钩。
有两个圆盘的河内塔

现在，我们可以为具有两个以上磁盘的汉诺塔设计算法。我们将磁盘堆栈分为两部分。最大的圆盘（第 n个圆盘）位于一部分中，所有其他 (n-1) 个圆盘位于第二部分中。

我们的最终目标是将磁盘n从源移动到目标，然后将所有其他 (n1) 磁盘放入其中。我们可以想象以递归方式对所有给定的磁盘集应用相同的方法。

要遵循的步骤是 -

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

河内塔的递归算法可以按如下方式驱动 -

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++ Java Python 
#include <stdio.h>
#include <stdbool.h>
#define MAX 10
int list[MAX] = {1,8,4,6,0,3,5,2,7,9};
void display(){
   int i;
   printf("[");
   // navigate through all items 
   for(i = 0; i < MAX; i++) {
      printf("%d ",list[i]);
   }
   printf("]\n");
}
void bubbleSort() {
   int temp;
   int i,j;
   bool swapped = false;       
   // loop through all numbers 
   for(i = 0; i < MAX-1; i++) { 
      swapped = false;	
      // loop through numbers falling ahead 
      for(j = 0; j < MAX-1-i; j++) {
         printf("Items compared: [ %d, %d ] ", list[j],list[j+1]);
         // check if next number is lesser than current no
         //   swap the numbers. 
         //  (Bubble up the highest number) 		
         if(list[j] > list[j+1]) {
            temp = list[j];
            list[j] = list[j+1];
            list[j+1] = temp;
            swapped = true;
            printf(" => swapped [%d, %d]\n",list[j],list[j+1]);
         } else {
            printf(" => not swapped\n");
         }
      }
      // if no number was swapped that means 
      //   array is sorted now, break the loop. 
      if(!swapped) {
         break;
      }
      printf("Iteration %d#: ",(i+1)); 
      display();                     
   }    
}
int main() {
   printf("Input Array: ");
   display();
   printf("\n");
   bubbleSort();
   printf("\nOutput Array: ");
   display();
}

输出

Input Array: [1 8 4 6 0 3 5 2 7 9 ]

Items compared: [ 1, 8 ]  => not swapped
Items compared: [ 8, 4 ]  => swapped [4, 8]
Items compared: [ 8, 6 ]  => swapped [6, 8]
Items compared: [ 8, 0 ]  => swapped [0, 8]
Items compared: [ 8, 3 ]  => swapped [3, 8]
Items compared: [ 8, 5 ]  => swapped [5, 8]
Items compared: [ 8, 2 ]  => swapped [2, 8]
Items compared: [ 8, 7 ]  => swapped [7, 8]
Items compared: [ 8, 9 ]  => not swapped
Iteration 1#: [1 4 6 0 3 5 2 7 8 9 ]
Items compared: [ 1, 4 ]  => not swapped
Items compared: [ 4, 6 ]  => not swapped
Items compared: [ 6, 0 ]  => swapped [0, 6]
Items compared: [ 6, 3 ]  => swapped [3, 6]
Items compared: [ 6, 5 ]  => swapped [5, 6]
Items compared: [ 6, 2 ]  => swapped [2, 6]
Items compared: [ 6, 7 ]  => not swapped
Items compared: [ 7, 8 ]  => not swapped
Iteration 2#: [1 4 0 3 5 2 6 7 8 9 ]
Items compared: [ 1, 4 ]  => not swapped
Items compared: [ 4, 0 ]  => swapped [0, 4]
Items compared: [ 4, 3 ]  => swapped [3, 4]
Items compared: [ 4, 5 ]  => not swapped
Items compared: [ 5, 2 ]  => swapped [2, 5]
Items compared: [ 5, 6 ]  => not swapped
Items compared: [ 6, 7 ]  => not swapped
Iteration 3#: [1 0 3 4 2 5 6 7 8 9 ]
Items compared: [ 1, 0 ]  => swapped [0, 1]
Items compared: [ 1, 3 ]  => not swapped
Items compared: [ 3, 4 ]  => not swapped
Items compared: [ 4, 2 ]  => swapped [2, 4]
Items compared: [ 4, 5 ]  => not swapped
Items compared: [ 5, 6 ]  => not swapped
Iteration 4#: [0 1 3 2 4 5 6 7 8 9 ]
Items compared: [ 0, 1 ]  => not swapped
Items compared: [ 1, 3 ]  => not swapped
Items compared: [ 3, 2 ]  => swapped [2, 3]
Items compared: [ 3, 4 ]  => not swapped
Items compared: [ 4, 5 ]  => not swapped
Iteration 5#: [0 1 2 3 4 5 6 7 8 9 ]
Items compared: [ 0, 1 ]  => not swapped
Items compared: [ 1, 2 ]  => not swapped
Items compared: [ 2, 3 ]  => not swapped
Items compared: [ 3, 4 ]  => not swapped

Output Array: [0 1 2 3 4 5 6 7 8 9 ]

// C++ Code for Tower of Hanoi
#include <iostream>
#include <array>
#include <algorithm>
const int MAX = 10;
std::array<int, MAX> list = {1, 8, 4, 6, 0, 3, 5, 2, 7, 9};
void display() {
   std::cout << "[";
   // navigate through all items 
   for (int i = 0; i < MAX; i++) {
      std::cout << list[i] << " ";
   }	
   std::cout << "]\n";
}
void bubbleSort() {
   int temp;
   bool swapped = false;       
   // loop through all numbers 
   for (int i = 0; i < MAX - 1; i++) { 
      swapped = false;		
      // loop through numbers falling ahead 
      for (int j = 0; j < MAX - 1 - i; j++) {
         std::cout << "Items compared: [" << list[j] << ", " << list[j+1] << "] ";
         // check if next number is lesser than current no
         // swap the numbers. 
         // (Bubble up the highest number) 		
         if (list[j] > list[j+1]) {
            std::swap(list[j], list[j+1]);
            swapped = true;
            std::cout << "=> swapped [" << list[j] << ", " << list[j+1] << "]\n";
         } else {
            std::cout << "=> not swapped\n";
         }
      }
      // if no number was swapped that means 
      // array is sorted now, break the loop. 
      if (!swapped) {
         break;
      }  
      std::cout << "Iteration " << (i+1) << "#: "; 
      display();                     
   }    
}
int main() {
   std::cout << "Input Array: ";
   display();
   std::cout << "\n";
   bubbleSort();
   std::cout << "\nOutput Array: ";
   display();
   return 0;
}

输出

Input Array: [1 8 4 6 0 3 5 2 7 9 ]

Items compared: [1, 8] => not swapped
Items compared: [8, 4] => swapped [4, 8]
Items compared: [8, 6] => swapped [6, 8]
Items compared: [8, 0] => swapped [0, 8]
Items compared: [8, 3] => swapped [3, 8]
Items compared: [8, 5] => swapped [5, 8]
Items compared: [8, 2] => swapped [2, 8]
Items compared: [8, 7] => swapped [7, 8]
Items compared: [8, 9] => not swapped
Iteration 1#: [1 4 6 0 3 5 2 7 8 9 ]
Items compared: [1, 4] => not swapped
Items compared: [4, 6] => not swapped
Items compared: [6, 0] => swapped [0, 6]
Items compared: [6, 3] => swapped [3, 6]
Items compared: [6, 5] => swapped [5, 6]
Items compared: [6, 2] => swapped [2, 6]
Items compared: [6, 7] => not swapped
Items compared: [7, 8] => not swapped
Iteration 2#: [1 4 0 3 5 2 6 7 8 9 ]
Items compared: [1, 4] => not swapped
Items compared: [4, 0] => swapped [0, 4]
Items compared: [4, 3] => swapped [3, 4]
Items compared: [4, 5] => not swapped
Items compared: [5, 2] => swapped [2, 5]
Items compared: [5, 6] => not swapped
Items compared: [6, 7] => not swapped
Iteration 3#: [1 0 3 4 2 5 6 7 8 9 ]
Items compared: [1, 0] => swapped [0, 1]
Items compared: [1, 3] => not swapped
Items compared: [3, 4] => not swapped
Items compared: [4, 2] => swapped [2, 4]
Items compared: [4, 5] => not swapped
Items compared: [5, 6] => not swapped
Iteration 4#: [0 1 3 2 4 5 6 7 8 9 ]
Items compared: [0, 1] => not swapped
Items compared: [1, 3] => not swapped
Items compared: [3, 2] => swapped [2, 3]
Items compared: [3, 4] => not swapped
Items compared: [4, 5] => not swapped
Iteration 5#: [0 1 2 3 4 5 6 7 8 9 ]
Items compared: [0, 1] => not swapped
Items compared: [1, 2] => not swapped
Items compared: [2, 3] => not swapped
Items compared: [3, 4] => not swapped

Output Array: [0 1 2 3 4 5 6 7 8 9 ]

//Java Code for Tower of Hanoi
import java.util.Arrays;
public class BubbleSort {
    public static final int MAX = 10;
    public static int[] list = {1, 8, 4, 6, 0, 3, 5, 2, 7, 9};
    public static void display() {
        System.out.print("[");
        // navigate through all items
        for (int i = 0; i < MAX; i++) {
            System.out.print(list[i] + " ");
        }
        System.out.println("]");
    }
    public static void bubbleSort() {
        boolean swapped;
        // loop through all numbers
        for (int i = 0; i < MAX - 1; i++) {
            swapped = false;
            // loop through numbers falling ahead
            for (int j = 0; j < MAX - 1 - i; j++) {
                System.out.print("Items compared: [" + list[j] + ", " + list[j + 1] + "] ");
                // check if next number is lesser than current no
                // swap the numbers.
                // (Bubble up the highest number)
                if (list[j] > list[j + 1]) {
                    int temp = list[j];
                    list[j] = list[j + 1];
                    list[j + 1] = temp;
                    swapped = true;
                    System.out.println("=> swapped [" + list[j] + ", " + list[j + 1] + "]");
                } else {
                    System.out.println("=> not swapped");
                }
            }
            // if no number was swapped that means
            // array is sorted now, break the loop.
            if (!swapped) {
                break;
            }
            System.out.print("Iteration " + (i + 1) + "#: ");
            display();
        }
    }
    public static void main(String[] args) {
        System.out.print("Input Array: ");
        display();
        System.out.println();
        bubbleSort();
        System.out.print("\nOutput Array: ");
        display();
    }
}

输出

Input Array: [1 8 4 6 0 3 5 2 7 9 ]
Items compared: [1, 8] => not swapped
Items compared: [8, 4] => swapped [4, 8]
Items compared: [8, 6] => swapped [6, 8]
Items compared: [8, 0] => swapped [0, 8]
Items compared: [8, 3] => swapped [3, 8]
Items compared: [8, 5] => swapped [5, 8]
Items compared: [8, 2] => swapped [2, 8]
Items compared: [8, 7] => swapped [7, 8]
Items compared: [8, 9] => not swapped
Iteration 1#: [1 4 6 0 3 5 2 7 8 9 ]
Items compared: [1, 4] => not swapped
Items compared: [4, 6] => not swapped
Items compared: [6, 0] => swapped [0, 6]
Items compared: [6, 3] => swapped [3, 6]
Items compared: [6, 5] => swapped [5, 6]
Items compared: [6, 2] => swapped [2, 6]
Items compared: [6, 7] => not swapped
Items compared: [7, 8] => not swapped
Iteration 2#: [1 4 0 3 5 2 6 7 8 9 ]
Items compared: [1, 4] => not swapped
Items compared: [4, 0] => swapped [0, 4]
Items compared: [4, 3] => swapped [3, 4]
Items compared: [4, 5] => not swapped
Items compared: [5, 2] => swapped [2, 5]
Items compared: [5, 6] => not swapped
Items compared: [6, 7] => not swapped
Iteration 3#: [1 0 3 4 2 5 6 7 8 9 ]
Items compared: [1, 0] => swapped [0, 1]
Items compared: [1, 3] => not swapped
Items compared: [3, 4] => not swapped
Items compared: [4, 2] => swapped [2, 4]
Items compared: [4, 5] => not swapped
Items compared: [5, 6] => not swapped
Iteration 4#: [0 1 3 2 4 5 6 7 8 9 ]
Items compared: [0, 1] => not swapped
Items compared: [1, 3] => not swapped
Items compared: [3, 2] => swapped [2, 3]
Items compared: [3, 4] => not swapped
Items compared: [4, 5] => not swapped
Iteration 5#: [0 1 2 3 4 5 6 7 8 9 ]
Items compared: [0, 1] => not swapped
Items compared: [1, 2] => not swapped
Items compared: [2, 3] => not swapped
Items compared: [3, 4] => not swapped
Output Array: [0 1 2 3 4 5 6 7 8 9 ]

#Python Code for Tower of Hanoi
MAX = 10
list = [1, 8, 4, 6, 0, 3, 5, 2, 7, 9]
def display():
    print("[", end="")
    # navigate through all items
    for i in range(MAX):
        print(list[i], end=" ")
    print("]")
def bubbleSort():
    swapped = False
    # loop through all numbers
    for i in range(MAX - 1):
        swapped = False
        # loop through numbers falling ahead
        for j in range(MAX - 1 - i):
            print("Items compared: [",
                  list[j],
                  ", ",
                  list[j + 1],
                  "] ",
                  end="")
            # check if next number is lesser than the current number
            # swap the numbers.
            # (Bubble up the highest number)
            if list[j] > list[j + 1]:
                temp = list[j]
                list[j] = list[j + 1]
                list[j + 1] = temp
                swapped = True
                print("=> swapped [", list[j], ", ", list[j + 1], "]")
            else:
                print("=> not swapped")
        # if no number was swapped, the array is sorted now, break the loop
        if not swapped:
            break
        print("Iteration", (i + 1), "#: ", end="")
        display()
print("Input Array: ", end="")
display()
print()
bubbleSort()
print("\nOutput Array: ", end="")
display()

输出

Input Array: [1 8 4 6 0 3 5 2 7 9 ]
Items compared: [ 1 ,  8 ] => not swapped
Items compared: [ 8 ,  4 ] => swapped [ 4 ,  8 ]
Items compared: [ 8 ,  6 ] => swapped [ 6 ,  8 ]
Items compared: [ 8 ,  0 ] => swapped [ 0 ,  8 ]
Items compared: [ 8 ,  3 ] => swapped [ 3 ,  8 ]
Items compared: [ 8 ,  5 ] => swapped [ 5 ,  8 ]
Items compared: [ 8 ,  2 ] => swapped [ 2 ,  8 ]
Items compared: [ 8 ,  7 ] => swapped [ 7 ,  8 ]
Items compared: [ 8 ,  9 ] => not swapped
Iteration 1 #: [1 4 6 0 3 5 2 7 8 9 ]
Items compared: [ 1 ,  4 ] => not swapped
Items compared: [ 4 ,  6 ] => not swapped
Items compared: [ 6 ,  0 ] => swapped [ 0 ,  6 ]
Items compared: [ 6 ,  3 ] => swapped [ 3 ,  6 ]
Items compared: [ 6 ,  5 ] => swapped [ 5 ,  6 ]
Items compared: [ 6 ,  2 ] => swapped [ 2 ,  6 ]
Items compared: [ 6 ,  7 ] => not swapped
Items compared: [ 7 ,  8 ] => not swapped
Iteration 2 #: [1 4 0 3 5 2 6 7 8 9 ]
Items compared: [ 1 ,  4 ] => not swapped
Items compared: [ 4 ,  0 ] => swapped [ 0 ,  4 ]
Items compared: [ 4 ,  3 ] => swapped [ 3 ,  4 ]
Items compared: [ 4 ,  5 ] => not swapped
Items compared: [ 5 ,  2 ] => swapped [ 2 ,  5 ]
Items compared: [ 5 ,  6 ] => not swapped
Items compared: [ 6 ,  7 ] => not swapped
Iteration 3 #: [1 0 3 4 2 5 6 7 8 9 ]
Items compared: [ 1 ,  0 ] => swapped [ 0 ,  1 ]
Items compared: [ 1 ,  3 ] => not swapped
Items compared: [ 3 ,  4 ] => not swapped
Items compared: [ 4 ,  2 ] => swapped [ 2 ,  4 ]
Items compared: [ 4 ,  5 ] => not swapped
Items compared: [ 5 ,  6 ] => not swapped
Iteration 4 #: [0 1 3 2 4 5 6 7 8 9 ]
Items compared: [ 0 ,  1 ] => not swapped
Items compared: [ 1 ,  3 ] => not swapped
Items compared: [ 3 ,  2 ] => swapped [ 2 ,  3 ]
Items compared: [ 3 ,  4 ] => not swapped
Items compared: [ 4 ,  5 ] => not swapped
Iteration 5 #: [0 1 2 3 4 5 6 7 8 9 ]
Items compared: [ 0 ,  1 ] => not swapped
Items compared: [ 1 ,  2 ] => not swapped
Items compared: [ 2 ,  3 ] => not swapped
Items compared: [ 3 ,  4 ] => not swapped

Output Array: [0 1 2 3 4 5 6 7 8 9 ]