UOJ Logo

NOI.AC

1S 512MB

#1138. 汉诺塔

Statistics

用递归算法模拟汉诺塔。 有三根杆子$X,Y,Z$。$X$杆上有$N$个($N \geq 1$)穿孔圆盘,盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至$Y$杆:

  • 每次只能移动一个圆盘
  • 大盘不能叠在小盘上面

递归思想(为降低题目难度,公开递归思想):

将$X$杆上的$n-1$个圆盘都移到空闲的$Z$杆上,并且满足上面的所有条件 将$X$杆上的第$n$个圆盘移到$Y$上 剩下问题就是将Z杆上的$n-1$个圆盘移动到Y上了

【输入说明】

一行,盘子数量

【输出说明】

移动方案,见输出样例

【输入样例】

3

【输出样例】

第1步,将1从X杆移动到Y杆
第2步,将2从X杆移动到Z杆
第3步,将1从Y杆移动到Z杆
第4步,将3从X杆移动到Y杆
第5步,将1从Z杆移动到X杆
第6步,将2从Z杆移动到Y杆
第7步,将1从X杆移动到Y杆