递归 - 河内塔

递归 - 河内塔 首页 / 结构和算法入门教程 / 递归 - 河内塔

河内塔,是一个数学难题,由三个塔(钉)和多个环组成,如图所示-

Tower Of Hanoi

这些环的尺寸不同,并且以升序堆叠,即较小的环位于较大的环上,难题的其他变体是磁盘数量增加,但是塔数保持不变。

规则

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

链接:https://www.learnfk.comhttps://www.learnfk.com/data-structures-algorithms/tower-of-hanoi.html

来源:LearnFk无涯教程网

  • 在任何给定时间,只能在塔之间移动一个磁盘。
  • 只能删除"顶部"磁盘。
  • 大磁盘不能放在小磁盘上。

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

无涯教程网

Tower Of Hanoi

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

算法

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

如果我们有2个磁盘-

  • 首先,我们将较小的(顶部)磁盘移到辅助钉上。
  • 然后,我们将较大的(底部)磁盘移到目标钉上。
  • 最后,我们将较小的磁盘从aux移到目标钉。
Tower Of Hanoi with Two Disks

因此,现在我们可以为带有两个以上磁盘的河内塔设计一种算法,我们将磁盘堆栈分为两部分。最大的磁盘(第n个 磁盘)在一部分中,所有其他(n-1)个磁盘在第二部分中。

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

河内塔的递归算法可以如下代码-

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编程的实现

#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 ]

祝学习愉快!(内容编辑有误?请选中要编辑内容 -> 右键 -> 修改 -> 提交!)

技术教程推荐

赵成的运维体系管理课 -〔赵成〕

MySQL实战45讲 -〔林晓斌〕

透视HTTP协议 -〔罗剑锋(Chrono)〕

Node.js开发实战 -〔杨浩〕

说透中台 -〔王健〕

架构实战案例解析 -〔王庆友〕

MySQL 必知必会 -〔朱晓峰〕

说透芯片 -〔邵巍〕

超级访谈:对话玉伯 -〔玉伯〕

好记忆不如烂笔头。留下您的足迹吧 :)