汉诺塔游戏
时间限制: 1 s|空间限制: 32000 KB
题目描述 Description
汉诺塔问题(又称为河内塔问题),是一个大家熟知的问题。在A,B,C三根柱子上,
有n个不同大小的圆盘(假设半径分别为1-n吧),一开始他们都叠在我A上(如图所示),
你的目标是在最少的合法移动步数内将所有盘子从A塔移动到C塔。
游戏中的每一步规则如下:
每一步只允许移动一个盘子(从一根柱子最上方到另一个柱子的最上方)
移动的过程中,你必须保证大的盘子不能在小的盘子上方
(小的可以放在大的上面,最大盘子下面不能有任何其他大小的盘子)
如对于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.)
如此执行,通过递归方式。代码思路如下:
- 对于执行最大盘(n) 到C的操作之前,肯定是?把次大盘(n-1)从A移动到 B
2. 执行最大盘(n) 到C的操作 3.对于执行最大盘(n) 到C的操作之后,肯定是?把次大盘(n-1)从B移动到C
每次只关心上一层,上上层是到了上一层才考虑的事——递归
题目链接:http://codevs.cn/problem/3145/
Javascript
#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;
}
Java
#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;
}
C语言
#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;
}