C语言每日一练——第88天：汉诺塔问题（河内塔）
? 前言
大家好，我是Edison?
今天是C语言每日一练，第88天！
Let’s get it！
1. 题目描述
汉诺塔问题
解题之前，我们先来了解一下 汉诺塔 到底是什么？
传说，在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。
印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。
不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。
僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。
我也从网上找了张图片，大致是下面这样的?
2. 解题思路
思路很简单：有三根相邻的柱子，从左到右分别为：托盘A、托盘B、托盘C；
托盘A按照“从下到上、从大到小”叠放着3个不同大小的盘子；?
第一步：将盘子1从托盘A移动至托盘C?
第二步：将盘子2从托盘A移动至托盘B?
第三步：将盘子1从托盘C移动至托盘B?
第四步：将盘子3从托盘A移动至托盘C?
第五步：将盘子1从托盘B移动至托盘A?
第六步：将盘子2从托盘B移动至托盘C?
第七步：将盘子1从托盘A移动至托盘C?
（注：此过程图是我从网上找的，实在是难得画啦?）
3. 动图演示
是不是很简单？
我们从上面移动的过程中，可以看到，托盘B始终作为一个过渡的存在，并且可以把它想象成中转柱；
那么我们就可以这样理解：
托盘A：起始柱A；
托盘B：中转柱B；
托盘C：目标柱C
4. 代码实现
那么我们怎么用代码来实现呢？
这是一个非常经典的递归问题。
假设有n个盘子，需要把这些盘子从第一根起始柱A移动到第三根目标柱C中。
1、首先需要把n-1个盘子移动到第二根中转柱B上；
2、再把最后一个也就是最大的那一个盘子移动到第三根目标柱C上；
3、最后再把剩下的n-1个盘子移动到第三根目标柱C上。
我们定义f
(
n
)
f(n)
f(n)是需要移动的次数；
f
(
1
)
=
1
，
f
(
2
)
=
3
，
f
(
3
)
=
7
f(1) = 1，f(2) = 3，f(3) = 7
f(1)=1，f(2)=3，f(3)=7
…
f
(
n
)
=
2
f
(
n
−
1
)
+
1
f(n) = 2f(n-1)+1
f(n)=2f(n−1)+1
?代码示例
这里拿3个盘子为例
#include <stdio.h>
void move(int n, char pos1, char pos3)
{
//打印移动的过程
// 1代表上面最小的盘子
// 2代表中间位置的盘子
// 3代表下面最大的盘子
printf("盘子%d: 从 %c柱 移动到 %c柱n", n, pos1, pos3);
}
void Hanoi(int n, char pos1, char pos2, char pos3)
{
//如果是1个盘子，直接从起始柱A移动到目标柱C
if (n == 1)
{
move(n, pos1, pos3);
}
else
{
//如果盘子大于1个，需要把n-1个盘子，从起始柱pos1，通过目标柱pos3，移动到中转柱pos2
Hanoi(n-1, pos1, pos3, pos2);
//此时pos1上的n-1个盘子全部移动pos2上去了，那么可以直接把pos1上剩下的1个盘子，直接移动到pos3上
move(n, pos1, pos3);
//把pos2剩下的n-1个盘子，通过中转位置pos1，移动到目标位置pos3
Hanoi(n-1, pos2, pos1, pos3);
}
}
int main()
{
//盘子个数
int n = 3;
//起始柱A
char pos1 = 'A';
//中转柱B
char pos2 = 'B';
//目标柱C
char pos3 = 'C';
printf("移动%d个盘子的步骤如下↓n", n);
//汉诺塔函数
Hanoi(n, pos1, pos2, pos3);
return 0;
}
运行结果?
完整代码贴图?
5. 特性总结
回到我们这个题的本身，僧侣要移动64个金片，到底需要多久？
对于汉诺塔问题，f
(
n
)
=
2
64
−
1
f(n) = 2^{64}-1
f(n)=264−1 这是一个什么概念？
即使是每微秒移动一次， 也需要5000世纪的时间， 可能到那个时候，世界也许真的将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽?
不信的话，大家可以去试一试?
（以上内容如有转载或引用请私聊说明并标明出处?）