前言

这里主要讲解汉诺塔问题的一些思路,自己之前了解过汉诺塔问题,虽然只是会做,但并没有整理出自己的思路,因此希望可以写下这篇博文来记录下自己学习汉诺塔问题求解的思路!

汉诺塔问题

假设有3根柱子,分别用A、B、C表示,柱子A上套着n个半径大小不同的盘子(盘子中央有小空),并且大盘子在下面,小盘子在上面。要求将柱子A上的盘子搬到柱子C上,在搬动过程中,可以使用柱子B暂时存放盘子,但无论何时都必须保证大盘子在下面,小盘子在上面,并且每次只能搬动一个盘子。

以4个盘子为例说明

解题思路:

  1. 首先找到目前4个最大的盘子也就是A柱子最下面的1号盘子,将1号盘子移动到C(这里只是讲解思路,中间的过程后面讲)
  2. 接着继续从现在3个盘子里面找到最大的移动到C
  3. 接着继续从现在2个盘子里面找到最大的移动到C
  4. 将剩下的最后一个直接移动到C

思路如此,不难发现,每次当我们找到目前还没有归位的盘子中最大的放到C中,下次要找的没有归位的盘子中便少了1个盘子,并且也要放到C中,逐层递归,直到最后只剩1个盘子,直接放到C中

具体步骤

  1. 我们要将目前没有归位的盘子中最大的盘子从A移动到C,但是B又是一个空柱子,可以作为一个中介,我们可以借助B(其他盘子放到B或C,最终除最大的以外其他的都在B),把最大的从A移动到C
  2. 再从剩下n-1个盘子中,借助A将最大的盘子从B移动到C,
  3. 逐层递归,直到最后只剩1个盘子,直接放到C中
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <stdio.h>


void hanoi(int n, char A, char B, char C); //n为盘子的个数,A为盘子的起点,B为中介,C为盘子放的重点
void move(char x, char y); //直接将盘子从x移动到y


void main()
{
int n;
printf("input the number of diskes: ");
scanf("%d", &n);

printf("the step to moving %d diskes:\n", n);
hanoi(n, 'A', 'B', 'C');

}

void hanoi(int n, char A, char B, char C)
{
if(n == 1)
move(A, C); //如果只有一个盘子,直接从A移动到C
else
{
hanoi(n-1, A, C, B); //要移动n个中最大的,需要将其他n-1个盘子移动到中介中
move(A, C); //最大的盘子从A移动到c
hanoi(n-1, B, A, C); //现在只剩下n-1个盘子没有归位了,因此重新开始,n-1个盘子因为都在B上,所以我们需要修改起点,因为要放到C,所以这次中介为A,也要进行修改
}
}


void move(char x, char y)
{
printf("%c---------------------> %c\n", x, y);
}

总结:汉诺塔问题可以理解为递归问题,每次我们只需要找到当前最大的移动到目的地中,逐渐递归,直到最后只剩1个