汉诺塔问题分析

汉诺塔问题分析

引用

CSDN

1.

https://blog.csdn.net/2401_83283514/article/details/137691031

汉诺塔问题是在递归学习中一个非常有意思的问题，是一道经典的智力游戏，也被称为河内塔或汉诺威塔。游戏的目的是通过一系列的移动，将一组大小不一的矩形条从一个柱子全部移动到另一个指定柱子上。我们来看一下汉诺塔游戏的规则：

1. 游戏开始时，所有的矩形条全部堆叠在最左侧柱子上，并且最大的矩形条在最底侧，最小的在最顶侧。
2. 玩家的目标是把这些矩形条全部移动到最右侧柱子上，同样最大的矩形条在最底侧，最小的矩形条在最顶侧。
3. 在移动过程中，玩家每次只能移动一个矩形条，并且只能在三个柱子间移动。
4. 移动过程中，小矩形条不能在大矩形条下面，即大矩形条必须在底部，小矩形条必须在顶部。
5. 玩家不能使用额外的空间或者临时的柱子来帮助移动矩形条

完成汉诺塔问题的步骤：

1. 将最顶层的矩形条从图一移动到柱子即图三上；
2. 然后把图一中介于两者大小之间的矩形条移动到柱子即图二上；
3. 把图三中的矩形条移动到图二上；
4. 把图三中最大的矩形条移动到图三上；
5. 把图二中较小的矩形条移动到图以上；
6. 再把图二上剩余的一个矩形条移动到图三上；
7. 最后再把图以上的矩形条移动到图三即可。

通过这个我们可以发现一个规律：有三个矩形条移动了7次即2^3-1；也就是说如果有n个矩形条的话移动了2^n-1次。

那么接下来我们就来看代码部分：

#include<stdio.h>
void move(char A,char B)
{
  printf("%c->%c\n",A,B);
}
//n:矩形条的个数
//pos1:即图一所在柱子
//pos2：图二所在柱子
//pos3：图三所在柱子
void Hanio(int n,char pos1,char pos2,char pos3)
{
  if(n==1)
  {
    move(pos1,pos3);
  }
  else
  {
    Hanio(n-1,pos1,pos3,pos2);//此时pos1是起始位置，pos3是辅助位置，pos2是目标位置
    move(pos1,pos3);//这个时候图一所在位置仅剩下一个矩形条，移动到目标柱子图三即可
    Hanio(n-1,pos2,pos1,pos3);//此时pos2是起始位置，pos1是辅助位置，pos3是目标位置
  }//用到了递归的思想
}
int main()
{
  int n=0;
  scanf("%d",&n);
  Hanio(n,'a','b','c');
  return 0;
}

汉诺塔游戏关键在于策略和逻辑思维，并把一个实际问题转化为代码的能力。这至关重要，对函数学习中递归的思想起到了很大的帮助，更加突出递归的魅力：把一个复杂的问题转化为一串逻辑简单的代码。通过解决汉诺塔问题，我们可以自己的问题解决能力和策略规划能力。

相信大家都一定会有所收获！