数据结构&算法河内塔

河内塔

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

这些环的尺寸不同，并按升序堆叠，即较小的环位于较大的环上。这种模型其他变体是磁盘数量增加，但是塔数保持不变。

规则

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

任何给定时间只能在塔之间移动一个磁盘。
只能移动“顶部”磁盘。
大磁盘不能放在小磁盘上。

以下是用三个磁盘解决“河内塔”难题的动画表示。

具有n个磁盘的河内之谜塔至少可以解决2^{n -1}个步骤。此演示文稿显示具有3个磁盘的拼图已采取2 ^3-1 = 7步。

算法

要为河内塔写算法，首先我们需要学习如何用更少的磁盘来解决此问题，例如→1或2。我们用名称，源，目标和辅助标记三个塔（仅用于帮助移动磁盘））。如果我们只有一个磁盘，则可以轻松地将其从源钉移到目标钉。

如果我们有2个磁盘-

首先，我们将较小的（顶部）磁盘移至辅助钉。
然后，我们将较大的（底部）磁盘移动到目标挂钉。
最后，我们将较小的磁盘从辅助钉移到目标钉。

因此，现在我们可以为带有两个以上磁盘的河内塔设计一种算法。我们将磁盘堆栈分为两部分。最大的磁盘（第 n 个磁盘）在一部分中，所有其他磁盘（n-1）在第二部分中。我们的最终目标是将磁盘n从源移动到目标，然后将所有其他（n1）磁盘放入磁盘。我们可以想像以递归方式对所有给定的磁盘集应用相同的内容。

遵循的步骤是-


步骤1 -将n-1磁盘从源移动到aux
步骤2 -将第n个磁盘从源移动到dest
步骤3 -将n-1个磁盘从aux移动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

示例


#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();
}

尝试一下

数据结构&算法 河内塔

河内塔

规则

算法

示例

数据结构&算法河内塔