汉诺塔问题（递归与非递归详解）--------------Five—菜鸟级
欢迎前往个人搭建博客 Five-great的博客
汉诺塔
时间限制: 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/
-
#include <stdio.h>
-
void han(int n, char A, char B, char C){
-
if(n == 1)printf("%d from %c to %c\n", n, A, C);
-
else{
-
//第一步 对于执行最大盘（n） 到C的操作之前
-
han(n-1, A, C, B);
-
//第二步 执行最大盘（n） 到C的操作
-
printf("%d from %c to %c\n", n, A, C);
-
//第三步 对于执行最大盘（n） 到C的操作之后
-
han(n-1, B, A, C);
-
}
-
}
-
int main()
-
{
-
int n;
-
scanf("%d", &n);
-
printf("%d\n", (1 << n) - 1);
-
han(n, 'A', 'B', 'C');
-
return 0;
-
}
非递归 思路：
我们先找找规律：
当3个盘的时候：
| 1 |
1:A-->C |
| 2 |
2:A-->B |
| 3 |
1:C-->B |
| 4 |
3:A-->C |
| 5 |
1:B-->A |
| 6 |
2:B-->C |
| 7 |
1:A-->C |
4个的时候：
| 1 |
1:A-->B |
| 2 |
2:A-->C |
| 3 |
1:B-->C |
| 4 |
3:A-->B |
| 5 |
1:C-->A |
| 6 |
2:C-->B |
| 7 |
1:A-->B |
| 8 |
4:A-->C |
| 9 |
1:B-->C |
| 10 |
2:B-->A |
| 11 |
1:C-->A |
| 12 |
3:B-->C |
| 13 |
1:A-->B |
| 14 |
2:A-->C |
| 15 |
1:B-->C |
仔细研究研究就能发现，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六种）
代码：
-
#include<stdio.h>
-
int main(){
-
long long i, res,t,k;int n,s;
-
scanf("%d", &n);
-
res=(1<<n)-1;
-
printf("%lld\n",res);
-
for( i=1; i <=res; i++ ){
-
for( t=2,s=1; s<= n; s++,t*=2)if( i%t == t/2 ) break;//i%t=t/2 找 第i步移动的S号盘
-
k = i/t;//获得第S盘 第几次移动
-
if( n%2 == s%2 ){// 逆时针
-
if( (k+1)%3 == 0 ) printf("%d from B to A\n",s);
-
if( (k+1)%3 == 1 ) printf("%d from A to C\n",s);
-
if( (k+1)%3 == 2 ) printf("%d from C to B\n",s);
-
}
-
else{// 逆时针
-
if( (k+1)%3 == 0 ) printf("%d from C to A\n",s);
-
if( (k+1)%3 == 1 ) printf("%d from A to B\n",s);
-
if( (k+1)%3 == 2 ) printf("%d from B to C\n",s);
-
}
-
}
-
return 0;
-
}
文章来源: fivecc.blog.csdn.net，作者：Five-菜鸟级，版权归原作者所有，如需转载，请联系作者。
原文链接：fivecc.blog.csdn.net/article/details/82829067
- 点赞
- 收藏
- 关注作者
评论（0）