前言

🎈大家好，我是何小侠🎈

🌀大家可以叫我**小何或者小侠🌀**

🔴我是一名普通的博客写作者🔴

💐希望能通过写博客加深自己对于学习内容的理解💐

🌸也能帮助更多人理解和学习🌸

🍃我的主页:何小侠的主页🍃

这篇博客我们一起来学习汉罗塔，或者说学习递归。希望这篇博客能帮助大家理解和学习

引子🍊

在印度，有这么一个古老的传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片，一次只移动一片，不管在哪根针上，小片必在大片上面。当所有的金片都从梵天穿好的那根针上移到另外一概针上时，世界就将在一声霹雳中消灭，梵塔、庙宇和众生都将同归于尽

汉罗塔解析🍊

我们先来看一个gif

这里有三个柱子，我们从左至右称为A柱，B柱，C柱。

我们先从一个圆盘开始分析

ru

如果只有一个柱子我们就只需要把柱子从A——>C就行了。

然后我们再来看看有两个圆盘呢？

我们看到我们先讲小圆盘移动到B柱，再把大圆盘移动到C柱，然后再将小圆盘移动到C柱。

再加一个圆盘会是什么样？我们已经快接近规律了。

这个过程就逐渐变复杂起来了，由于我们已经试出了三种情况，我们可以大胆猜测汉罗塔的规律。

• 当只有一个盘移动1次。
• 有两个盘移动3次
• 当有三个盘就移动7次
  (2 ^ n)-1
  如果我回顾到引子部分，n = 64 ，假设每个盘子的移动需要1秒那么就需要2^64 -1秒，假设一个人能活到80岁那么也只能活2522880000（25亿秒）秒，愚公移山可能都没这和尚这么绝望吧。

递归思路🍊

我们从上面其实还可以发现一个规律，如果有n个圆盘，我们其实只需要

• 将n-1个柱子借助C柱移动到B柱，
• 然后将最后一个盘子（也就是n盘）移动到C柱，
• 最后再将n-1个圆盘借助A柱从B柱移动到C柱就行了。

这个过程分析是很简单的，但是要接受递归的这种思维是很难的，我最开始也不是很相信递归，但是递归见的多了后就更相信了。

代码🍊

#include<stdio.h>
int count = 0;
void HannoTower(char A, char B, char C, int n)
{
  count++;
  if (1 == n)
  {
    printf("把第%d个盘子从%c柱---->%c柱\n",n,A,C);
  }
  else
  {
    HannoTower(A, C, B, n - 1);
    //借助C柱从A柱将n-1个盘子移动到B柱
    printf("把第%d个盘子从%c柱---->%c柱\n",n, A, C);
    //将最后一个盘子移动到C柱
    HannoTower(B, A, C, n-1);
    //借助A柱从B柱将n-1个盘子移动到C柱
  }
}
int main()
{
  int n = 0;
  printf("请输入你想要和尚搬多少个盘子\n");
  scanf("%d", &n);
  HannoTower('A', 'B', 'C', n);
  printf("和尚搬了%d次", count);
  return 0;
}

我记得我刚遇到这个题目时也没有任何思路，一直在想用什么来表示柱子，后来看到别人的代码也还是不能算很懂为什么字符A,B,C就能直接表示柱子。

但是实际上我们也只需要操作一些数字和字符就够了。

A、B、C，3个字符为抽象成的3个柱子。三个柱子中必定是有一个辅助移动柱的，在函数参数中把放在中间的当作辅助柱才行。这个代码如果你仔细去写出过程其实是比较麻烦的，因为我最近也没有太多时间所以我就不在这里实现了，我之前有看到有个同学写出来过，还是比较麻烦的。

总结🍊

这篇博客我们系统的介绍了汉诺塔的实现，有没有对递归有感觉了呢？如果没有再多练习就行了！。

最后如果这篇博客有帮助到你,欢迎点赞关注加收藏

如果本文有任何错误或者有疑点欢迎在评论区评论