【C语言】汉罗塔

article/2025/6/16 8:26:13

前言
🎈大家好，我是何小侠🎈
🌀大家可以叫我**小何或者小侠🌀**
🔴我是一名普通的博客写作者🔴
💐希望能通过写博客加深自己对于学习内容的理解💐
🌸也能帮助更多人理解和学习🌸
🍃我的主页: 何小侠的主页🍃

在这里插入图片描述

                        今天是高考，高考加油！

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

引子🍊

在印度，有这么一个古老的传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的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个柱子。三个柱子中必定是有一个辅助移动柱的，在函数参数中把放在中间的当作辅助柱才行。这个代码如果你仔细去写出过程其实是比较麻烦的，因为我最近也没有太多时间所以我就不在这里实现了，我之前有看到有个同学写出来过，还是比较麻烦的。