汉诺塔（递归 + 非递归版）
汉诺塔
时间限制: 1 s｜空间限制: 32000 KB
题目描述 Description
汉诺塔问题（又称为河内塔问题），是一个大家熟知的问题。在 A，B，C 三根柱子上，
有 n 个不同大小的圆盘（假设半径分别为 1-n 吧），一开始他们都叠在我 A 上（如图所示），
你的目标是在最少的合法移动步数内将所有盘子从 A 塔移动到 C 塔。
游戏中的每一步规则如下：
1. 每一步只允许移动一个盘子（从一根柱子最上方到另一个柱子的最上方）
2. 移动的过程中，你必须保证大的盘子不能在小的盘子上方
（小的可以放在大的上面，最大盘子下面不能有任何其他大小的盘子）
如对于 n=3 的情况，一个合法的移动序列式：
1 from A to C
2 from A to B
1 from C to B
3 from A to C
1 from B to A
2 from B to C
1 from A to C
给出一个数 n，求出最少步数的移动序列
输入描述 Input Description
一个整数 n
输出描述 Output Description
第一行一个整数 k，代表是最少的移动步数。
接下来 k 行，每行一句话，N from X to Y，表示把 N 号盘从 X 柱移动到 Y 柱。X,Y 属于{A,B,C}
样例输入 Sample Input
3
样例输出 Sample Output
7
1 from A to C
2 from A to B
1 from C to B
3 from A to C
1 from B to A
2 from B to C
1 from A to C
数据范围及提示 Data Size & Hint
n<=10
💡递归思路
我们设定三个柱子 A,B,C。我们的目的是将环从 A–>C。（A 为起始位置，C 为目标位置）
当 N=1 即一阶时它的路径很简单只需要从 A->C 进行移动。
当 N=2 时我们需要进行三步：
1.小盘 A->B
(假想没有大盘只有小盘，与 N=1 的步骤一样，只是目标位置变为了 B)
2.大盘 A->C
(大盘上面的小盘到 B 去了，与 N=1 的步骤一样直接到 C )
3.小盘 B->C
(大盘到了 C,对于小盘而言,C 可以看作无盘，与 N=1 的步骤一样，只是起始位置变为 B )
(分解一下，小盘从 A 通过 B 作为中间目标再到 C。可以这样想
小盘下面的大盘目标是 C 所以小盘第一次目标则变成 B,
等到大盘到了目标 C ,小盘再到 C。
则完成将大小盘按小盘在上大盘在下的要求移到 C。）
当 N=3 时我们需要进行七步：
1. 小盘 A->C 2.中盘 A->B 3.小盘 C->B
(假想没有大盘只有小盘和中盘，与 N=2 的步骤一样，只是目标位置变为了 B)
4. 大盘 A->C
(大盘上面的小盘和中盘都到 B 去了，与 N=1 的步骤一样直接到 C )
5. 小盘 B->A 6.中盘 B->C 7.小盘 A->C
(大盘到了 C,对于小盘和中盘而言,C 可以看作无盘，与 N=2 的步骤一样，只是起始位置变为了 B )
(分解一下，大盘想从 A 去 C。但上面压着小盘与中盘 ，
所以得先把他们移开 并且上面两盘不能移动到 C,得移动到 B 去
就相当于 N=2 时，起始位置 A 到目标位置 B。待大盘移动到 C。
当前在 B 的小盘和中盘，完全就是执行 N=2 的步骤。从当前起始位置 B 到目标位置 C.)
如此执行，通过递归方式。代码思路如下：
1. 对于执行最大盘（n） 到 C 的操作之前，肯定是把次大盘（n-1）从 A 移动到 B
2. 执行最大盘（n） 到 C 的操作
3.对于执行最大盘（n） 到 C 的操作之后，肯定是把次大盘（n-1）从 B 移动到 C
每次只关心上一层，上上层是到了上一层才考虑的事------递归
题目链接：http://codevs.cn/problem/3145/
💡非递归思路
我们先找找规律：
当 3 个盘的时候：
4 个的时候：
仔细研究研究就能发现，1 号出现在·1，3，5，7，9 步
2 号出现在 2，6，10，14 步
3 号出现在 4，12 步
4 号在 8，步
规律与 2^n 有关。
我们在研究研究，三个时：
一号盘的行动方式是：
A-->C
C-->B
B-->A
A-->C
二号盘的行动方式是：
A-->B
B-->C
三号盘的行动方式是：
A-->C
四个时：
一号盘的行动方式是：
A-->B
B-->C
C-->A
A-->B
B-->C
C-->A
A-->B
B-->C
（成一定的周期 T=3,当 l 号盘同最大盘 n 奇偶性相同，则 执行周期为顺时针，A-->B，B-->C，C-->A
否者则 执行周期为逆时针，A-->C，C-->B，B-->A ）
二号盘的行动方式是：
A-->C
C-->B
B-->A
A-->C
三号盘的行动方式是：
A-->B
B-->C
四号盘的行动方式是：
A-->C 总结下：A 号柱有 n 个盘子,叫做源柱.移往 C 号柱,叫做目的柱.B 号柱叫做中间柱.全部移往 C 号柱要 f(n) =（2^n）- 1 次.最大盘 n 号盘在整个移动过程中只移动一次,n-1 号移动 2 次,i 号盘移动 2^(n-i)次.1 号盘移动次数最多,每 2 次移动一次.第 2k+1 次移动的是 1 号盘,且是第 k+1 次移动 1 号盘.第 4k+2 次移动的是 2 号盘,且是第 k+1 次移动 2 号盘.第(2^s)k+2^(s-1)次移动的是 s 号盘,这时 s 号盘已被移动了 k+1 次.每 2^s 次就有一次是移动 s 号盘.第一次移动 s 号盘是在第 2^(s-1)次.第二次移动 s 号盘是在第 2^s+2^(s-1)次.第 k+1 次移动 s 号盘是在第 k*2^s+2^(s-1)次.
A-->B，B-->C，C-->A 叫做顺时针方向,A-->C，C-->B，B-->A 叫做逆时针方向.最大盘 n 号盘只移动一次:A-->C 它是逆时针移动.n-1 移动 2 次:A-->B，B-->C,是顺时针移动.
代码实现：
枚举 1, 2, 3, 4·····i, i+1, i+2, ·····步。
先 获取 第 i 步移动的几号盘，根据 (2^s)k+2^(s-1)=i,转化一下，满足 i%(2^s) =2^(s-1) ，令 t=2^s;则有 i%t=t/2
再 获得第 S 盘 第几次移动 ，根据 (2^s)k+2^(s-1)=i, k=i/(2^s) ,即 k=i/t;
最后 根据周期 T 与奇偶性 确定具体移动的步骤（共 6 六种）
代码：
版权声明: 本文为 InfoQ 作者【Five】的原创文章。
原文链接:【http://xie.infoq.cn/article/631ba26c1a3e7a2ed287054c5】。
本文遵守【CC-BY 4.0】协议，转载请保留原文出处及本版权声明。
有事多研究，没事瞎琢磨 2022.08.02 加入
🏆第三季签约作者🏆,CSDN 前端领域优质创作者 , 博客专家认证, 华为云云享专家。 退役ACMer, IT技术狂热爱好者 擅长领域，web前端，算法, 业务架构，可视化，富文本编辑器等。
评论