设计与分析 - 河内塔

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

河内塔

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

河内塔规则

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

  • 在任何给定时间，只能在塔之间移动一个圆盘。

  • 只能移除“顶部”磁盘。

  • 没有大磁盘可以位于小磁盘之上。

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

河内塔step0 河内塔 步骤1 河内塔 步骤2 河内塔 步骤3 河内塔 步骤4 河内塔 步骤5 河内塔 步骤6 河内塔 Step7 最后的河内塔

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

河内塔算法

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

如果我们有 2 个磁盘 -

  • 首先，我们将较小的（顶部）磁盘移动到辅助挂钩。

  • 然后，我们将较大（底部）的磁盘移动到目标挂钩。

  • 最后，我们将较小的磁盘从 aux 移动到目标挂钩。

步骤0 步骤1 第2步 步骤3 完毕

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

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

要遵循的步骤是 -

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 == 0, 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 <math.h>
#include <stdlib.h>
#include <limits.h>
// structure to store data of a stack
struct Stack {
   unsigned size;
   int top;
   int *arr;
};
// function to create a stack of given size.
struct Stack* stack_creation(unsigned size){
   struct Stack* stack = (struct Stack*) malloc(sizeof(struct Stack));
   stack -> size = size;
   stack -> top = -1;
   stack -> arr = (int*) malloc(stack -> size * sizeof(int));
   return stack;
}
// to check if stack is full
int isFull(struct Stack* stack){
   return (stack->top == stack->size - 1);
}
// to check if stack is empty
int isEmpty(struct Stack* stack){
   return (stack->top == -1);
}
// insertion in stack
void push(struct Stack *stack, int item){
   if (isFull(stack))
      return;
   stack -> arr[++stack -> top] = item;
}
// deletion in stack
int pop(struct Stack* stack){
   if (isEmpty(stack))
      return INT_MIN;
   return stack -> arr[stack -> top--];
}
//printing the movement of disks
void movement(char src, char dest, int disk){
   printf("Move the disk %d from \'%c\' to \'%c\'\n",disk, src, dest);
}
//Moving disks between two poles
void DiskMovement(struct Stack *src,
              struct Stack *dest, char s, char d){
   int pole1Disk1 = pop(src);
   int pole2Disk1 = pop(dest);
   if (pole1Disk1 == INT_MIN) {
      push(src, pole2Disk1);
      movement(d, s, pole2Disk1);
   } else if (pole2Disk1 == INT_MIN) {
      push(dest, pole1Disk1);
      movement(s, d, pole1Disk1);
   } else if (pole1Disk1 > pole2Disk1) {
      push(src, pole1Disk1);
      push(src, pole2Disk1);
      movement(d, s, pole2Disk1);
   } else {
      push(dest, pole2Disk1);
      push(dest, pole1Disk1);
      movement(s, d, pole1Disk1);
   }
}
//Towers of Hanoi implementation
void Iterative_TOH(int disk_count, struct Stack *src, struct Stack *aux, struct Stack *dest){
   int i, total_moves;
   char s = 'S', d = 'D', a = 'A';
   if (disk_count % 2 == 0) {
      char temp = d;
      d = a;
      a = temp;
   }
   total_moves = pow(2, disk_count) - 1;
   for (i = disk_count; i >= 1; i--)
      push(src, i);
   for (i = 1; i <= total_moves; i++) {
      if (i % 3 == 1)
         DiskMovement(src, dest, s, d);
      else if (i % 3 == 2)
         DiskMovement(src, aux, s, a);
      else if (i % 3 == 0)
         DiskMovement(aux, dest, a, d);
   }
}
int main(){
   unsigned disk_count = 3;
   struct Stack *src, *dest, *aux;

   // Three stacks are created with number of buckets equal to number of disks
   src = stack_creation(disk_count);
   aux = stack_creation(disk_count);
   dest = stack_creation(disk_count);
   Iterative_TOH(disk_count, src, aux, dest);
   return 0;
}

输出

Move the disk 1 from 'S' to 'D'
Move the disk 2 from 'S' to 'A'
Move the disk 1 from 'D' to 'A'
Move the disk 3 from 'S' to 'D'
Move the disk 1 from 'A' to 'S'
Move the disk 2 from 'A' to 'D'
Move the disk 1 from 'S' to 'D'

#include <iostream>
#include <cmath>
#include <climits>
using namespace std;
// structure to store data of a stack
struct Stack {
   unsigned size;
   int top;
   int *arr;
};
// function to create a stack of given size.
struct Stack* stack_creation(unsigned size){
   struct Stack* stack = (struct Stack*) malloc(sizeof(struct Stack));
   stack -> size = size;
   stack -> top = -1;
   stack -> arr = (int*) malloc(stack -> size * sizeof(int));
   return stack;
}
// to check if stack is full
int isFull(struct Stack* stack){
   return (stack->top == stack->size - 1);
}
// to check if stack is empty
int isEmpty(struct Stack* stack){
   return (stack->top == -1);
}
// insertion in stack
void push(struct Stack *stack, int item){
   if (isFull(stack))
      return;
   stack -> arr[++stack -> top] = item;
}
// deletion in stack
int pop(struct Stack* stack){
   if (isEmpty(stack))
      return INT_MIN;
   return stack -> arr[stack -> top--];
}
//printing the movement of disks
void movement(char src, char dest, int disk){
   cout << "Move the disk " << disk << " from " << src << " to " << dest <<endl;
}
//Moving disks between two poles
void DiskMovement(struct Stack *src,
              struct Stack *dest, char s, char d){
   int pole1Disk1 = pop(src);
   int pole2Disk1 = pop(dest);
   if (pole1Disk1 == INT_MIN) {
      push(src, pole2Disk1);
      movement(d, s, pole2Disk1);
   } else if (pole2Disk1 == INT_MIN) {
      push(dest, pole1Disk1);
      movement(s, d, pole1Disk1);
   } else if (pole1Disk1 > pole2Disk1) {
      push(src, pole1Disk1);
      push(src, pole2Disk1);
      movement(d, s, pole2Disk1);
   } else {
      push(dest, pole2Disk1);
      push(dest, pole1Disk1);
      movement(s, d, pole1Disk1);
   }
}
//Towers of Hanoi implementation
void Iterative_TOH(int disk_count, struct Stack *src, struct Stack *aux, struct Stack *dest){
   int i, total_moves;
   char s = 'S', d = 'D', a = 'A';
   if (disk_count % 2 == 0) {
      char temp = d;
      d = a;
      a = temp;
   }
   total_moves = pow(2, disk_count) - 1;
   for (i = disk_count; i >= 1; i--)
      push(src, i);
   for (i = 1; i <= total_moves; i++) {
      if (i % 3 == 1)
         DiskMovement(src, dest, s, d);
      else if (i % 3 == 2)
         DiskMovement(src, aux, s, a);
      else if (i % 3 == 0)
         DiskMovement(aux, dest, a, d);
   }
}
int main(){
   unsigned disk_count = 3;
   struct Stack *src, *dest, *aux;
// Three stacks are created with number of buckets equal to number of disks
   src = stack_creation(disk_count);
   aux = stack_creation(disk_count);
   dest = stack_creation(disk_count);
   Iterative_TOH(disk_count, src, aux, dest);
   return 0;
}

输出

Move the disk 1 from S to D
Move the disk 2 from S to A
Move the disk 1 from D to A
Move the disk 3 from S to D
Move the disk 1 from A to S
Move the disk 2 from A to D
Move the disk 1 from S to D

import java.util.*;
import java.lang.*;
import java.io.*;
// Tower of Hanoi
public class Iterative_TOH {
   //Stack
   class Stack {
      int size;
      int top;
      int arr[];
   }
   // Creating Stack
   Stack stack_creation(int size) {
      Stack stack = new Stack();
      stack.size = size;
      stack.top = -1;
      stack.arr = new int[size];
      return stack;
   }
   //to check if stack is full
   boolean isFull(Stack stack) {
      return (stack.top == stack.size - 1);
   }
   //to check if stack is empty
   boolean isEmpty(Stack stack) {
      return (stack.top == -1);
   }
   //Insertion in Stack
   void push(Stack stack, int item) {
      if (isFull(stack))
         return;
      stack.arr[++stack.top] = item;
   }
   //Deletion from Stack
   int pop(Stack stack) {
      if (isEmpty(stack))
         return Integer.MIN_VALUE;
      return stack.arr[stack.top--];
   }
   // Function to movement disks between the poles
   void Diskmovement(Stack src, Stack dest, char s, char d) {
      int pole1 = pop(src);
      int pole2 = pop(dest);
      // When pole 1 is empty
      if (pole1 == Integer.MIN_VALUE) {
         push(src, pole2);
         movement(d, s, pole2);
      }
      // When pole2 pole is empty
      else if (pole2 == Integer.MIN_VALUE) {
         push(dest, pole1);
         movement(s, d, pole1);
      }
      // When top disk of pole1 > top disk of pole2
      else if (pole1 > pole2) {
         push(src, pole1);
         push(src, pole2);
         movement(d, s, pole2);
      }
      // When top disk of pole1 < top disk of pole2
      else {
         push(dest, pole2);
         push(dest, pole1);
         movement(s, d, pole1);
      }
   }
   //Function to show the movementment of disks
   void movement(char source, char destination, int disk) {
      System.out.println("Move the disk " + disk + " from " + source + " to " + destination);
   }
   // Implementation
   void Iterative(int num, Stack src, Stack aux, Stack dest) {
      int i, total_count;
      char s = 'S', d = 'D', a = 'A';
      // Rules in algorithm will be followed
      if (num % 2 == 0) {
         char temp = d;
         d = a;
         a = temp;
      }
      total_count = (int)(Math.pow(2, num) - 1);
      // disks with large diameter are pushed first
      for (i = num; i >= 1; i--)
         push(src, i);
      for (i = 1; i <= total_count; i++) {
         if (i % 3 == 1)
            Diskmovement(src, dest, s, d);
         else if (i % 3 == 2)
            Diskmovement(src, aux, s, a);
         else if (i % 3 == 0)
            Diskmovement(aux, dest, a, d);
      }
   }
   // Main Function
   public static void main(String[] args) {
      // number of disks
      int num = 3;
      Iterative_TOH ob = new Iterative_TOH();
      Stack src, dest, aux;
      src = ob.stack_creation(num);
      dest = ob.stack_creation(num);
      aux = ob.stack_creation(num);
      ob.Iterative(num, src, aux, dest);
   }
}

输出

Move the disk 1 from S to D
Move the disk 2 from S to A
Move the disk 1 from D to A
Move the disk 3 from S to D
Move the disk 1 from A to S
Move the disk 2 from A to D
Move the disk 1 from S to D

#Iterative Towers of Hanoi
INT_MIN = -723489710
class Stack:
   def __init__(self, size):
      self.size = size
      self.top = -1
      self.arr = []
   # to check if the stack is full
   def isFull(self, stack):
      return stack.top == stack.size - 1
   # to check if the stack is empty
   def isEmpty(self, stack):
      return stack.top == -1
   # Insertion in Stack
   def push(self, stack, item):
      if self.isFull(stack):
         return
      stack.top+=1
      stack.arr.append(item)
   # Deletion from Stack
   def pop(self, stack):
      if self.isEmpty(stack):
         return INT_MIN
      stack.top-=1
      return stack.arr.pop()
   def DiskMovement(self, src, dest, s, d):
      pole1 = self.pop(src);
      pole2 = self.pop(dest);
      # When pole 1 is empty
      if(pole1 == INT_MIN):
         self.push(src, pole2)
         self.Movement(d, s, pole2)
      # When pole2 pole is empty
      elif (pole2 == INT_MIN):
         self.push(dest, pole1)
         self.Movement(s, d, pole1)
      # When top disk of pole1 > top disk of pole2
      elif (pole1 > pole2):
         self.push(src, pole1)
         self.push(src, pole2)
         self.Movement(d, s, pole2)
      # When top disk of pole1 < top disk of pole2
      else:
         self.push(dest, pole2)
         self.push(dest, pole1)
         self.Movement(s, d, pole1)
   # Function to show the Movementment of disks
   def Movement(self, source, destination, disk):
      print("Move the disk "+str(disk)+" from "+source+" to " + destination)
   # Implementation
   def Iterative(self, num, src, aux, dest):
      s, d, a = 'S', 'D', 'A'
      # Rules in algorithm will be followed
      if num % 2 == 0:
         temp = d
         d = a
         a = temp
      total_count = int(pow(2, num) - 1)
      # disks with large diameter are pushed first
      i = num
      while(i>=1):
         self.push(src, i)
         i-=1
      i = 1
      while(i <= total_count):
         if (i % 3 == 1):
            self.DiskMovement(src, dest, s, d)
         elif (i % 3 == 2):
            self.DiskMovement(src, aux, s, a)
         elif (i % 3 == 0):
            self.DiskMovement(aux, dest, a, d)
         i+=1

# number of disks
num = 3
# stacks created for src , dest, aux
src = Stack(num)
dest = Stack(num)
aux = Stack(num)
# solution for 3 disks
sol = Stack(0)
sol.Iterative(num, src, aux, dest)

输出

Move the disk 1 from S to D
Move the disk 2 from S to A
Move the disk 1 from D to A
Move the disk 3 from S to D
Move the disk 1 from A to S
Move the disk 2 from A to D
Move the disk 1 from S to D