河内塔,是一个数学难题,由三个塔(钉)和多个环组成,如图所示-
这些环的尺寸不同,并且以升序堆叠,即较小的环位于较大的环上,难题的其他变体是磁盘数量增加,但是塔数保持不变。
任务是将所有磁盘移动到另一个塔中,而不会违反排列顺序。河内塔需要遵循的一些规则是-
链接:https://www.learnfk.comhttps://www.learnfk.com/data-structures-algorithms/tower-of-hanoi.html
来源:LearnFk无涯教程网
以下是用三个磁盘解决"河内之塔"难题的动画表示。
可以用最少 2 n -1 个步骤解决带有n个磁盘的河内之谜塔。此演示文稿显示具有3个磁盘的拼图已采取 2 3 -1=7 的步骤。
要为河内塔写算法,首先我们需要学习如何用更少的磁盘(如→1或2)来解决此问题。我们用名称 source 源,标签了三个塔destination 和 aux (仅用于帮助移动磁盘)。如果我们只有一个磁盘,则可以轻松地将其从源钉移到目标钉。
如果我们有2个磁盘-
因此,现在我们可以为带有两个以上磁盘的河内塔设计一种算法,我们将磁盘堆栈分为两部分。最大的磁盘(第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
#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 ]
祝学习愉快!(内容编辑有误?请选中要编辑内容 -> 右键 -> 修改 -> 提交!)