Java递归求解汉诺塔问题

ゝ一世哀愁。 2022-07-12 10:52 197阅读 0赞

**汉诺塔问题**

![Center][]

**规则：**

1.每次只能移动一个圆盘。

2.圆盘可以插在X,Y,Z中的任一塔座上。

3.任何时刻都不能让一个大的圆盘落在小的圆盘上面。

**算法：**

1.当X塔只有1个盘子时，将编号为1的圆盘从X移到Z处。（编号自上而下，由小到大）

2.当X塔有2个盘子时，将编号为1的圆盘从X移动到Y处，接着将编号为2的圆盘从X移动到Z处，最后将编号为1的圆盘从Y移到Z处。

3.当X塔有3个盘子时，将X塔上编号1至2的盘子（共2个）移动到Y塔上（需借助Z塔），接着将X塔上的3号最大的盘子移动到Z塔，最后将Y塔上的两个盘子借助X塔移动到Z塔上。

4.当X塔有n个盘子时，需要借助Y塔作为辅助塔，将X塔上编号1到n-1的盘子从X塔借助Z为辅助塔移动到Y塔，接着将X塔上编号为n的圆盘从X移动到Z塔。最后将Y塔上的n-1个圆盘借助A为辅助塔移动到Z塔。

**因此可采用递归算法**

![Center 1][]

public class Hanoi { private static int i = 1;//记录执行的次数 public static void main(String[] args) { int num;//盘子的个数 try { System.out.print("请输入盘子的个数："); Scanner input = new Scanner(System.in); num = input.nextInt(); String x="A",y="B",z="C";//定义三座塔 hanoi(num,x,y,z); } catch (Exception e) { System.out.println("请输入正整数！"); } } /** * * @param n 盘标号 * @param x 源位置 * @param z 目的位置 */ public static void move(int num,String x, String z){ System.out.println("第"+i+++"步，将"+num+"号盘子从"+x+"移动到"+z); } /** * * @param num 盘标号 * @param x ”A“ * @param y ”B“ * @param z ”C“ */ public static void hanoi(int num,String x, String y, String z){ if(num == 1){ move(1,x,z); //一个盘子时，直接从x移动z }else{ hanoi(num-1,x,z,y);//将num-1个盘子从x移动y，借助z move(num,x,z); //将当前最大的盘子num从x移动到z hanoi(num-1,y,x,z);//将num-1个盘子从y移动z，借助x } } }

输出结果示例：

![Center 2][]

[Center]: /images/20220710/39af72852d5c4ed7b22c226ab1721a3f.png
[Center 1]: /images/20220710/94c549df2dfc4b408ed6f7407677b6f5.png
[Center 2]: /images/20220710/98b1aaccdd034464b1686cf74475ae0f.png