汉诺塔问题

作者本文的目标是利用递归求解汉诺塔的具体步骤

汉诺塔是什么

汉诺塔（Tower of Hanoi），又称河内塔，是一个源于印度古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

在这里插入图片描述

游戏思路

使用递归法，从复杂情况中找到最简单最特殊的情况，这就是递归结束的条件。
分析游戏，本游戏最核心的要求就是在小圆盘上不能放大圆盘
我们将三根柱子分别命名为A,B,C。

public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        System.out.println("请输入圆盘个数：");
        int n=sc.nextInt();
        System.out.println("过程为");
        hanoi(n,'a','b','c');
    }

在开始前，我们要输入圆盘个数，以及各个柱子的名称。

1.最简单的情况——一个圆盘

分析游戏，最简单的情况就是只有一个圆盘
只需将第A柱子上的圆盘移动到C柱子上就可。

在这里插入图片描述
只需要一步，从A柱移动到C柱上。

该过程简述为 A->C
此时我们可以写出递归的最特殊的情况，n==1；程序代码如下

//这里pos代表柱子
 public static void move(char pos1,char pos2){
        
        System.out.print(pos1 +"->"+ pos2+" ");
    }

运行程序
在这里插入图片描述

依次类推，增加盘子个数

2.两个圆盘

初始情况如下图，A柱上放有两个圆盘

在这里插入图片描述

此时就需要借助B柱来进行移动。
1.先将A柱上的圆盘1移动到B柱上
2.再将A柱上的圆盘2移动到C柱上
3.将B柱上的圆盘1移动到C柱上

第一步
在这里插入图片描述
第二步

第三步

该过程简述为 A->B A->C B->C
程序如下

public static void hanoi(int n,char pos1,char pos2,char pos3){
        if(n==1){
            move(pos1,pos3);
            return;
        }
        hanoi(n-1,pos1,pos3,pos2);
        move(pos1,pos3);
        hanoi(n-1,pos2,pos1,pos3);
    }

在这里插入图片描述

3.三个圆盘

在进行三个圆盘的移动时，我们总结1个圆盘和2个圆盘的过程，再加上递归的思想，我们的目的是先要将最大的盘也就是图中的盘3先放到C柱上。此时我们的步骤如下
1.先通过C柱将A柱上的1，2盘移动到B柱上
2.将A柱上的3盘移动到C柱上
3.利用A柱，再将B柱上的盘1，2移动到C柱上

在这里插入图片描述
第一步

简述过程 A->C A->B C->B
第二步

简述过程 A->C
第三步

简述过程
B->A B->C A->C

在这里插入图片描述

解释递归过程

递归代码如下

public static void hanoi(int n,char pos1,char pos2,char pos3){
        if(n==1){
            move(pos1,pos3);
            return;
        }
        hanoi(n-1,pos1,pos3,pos2);
        move(pos1,pos3);
        hanoi(n-1,pos2,pos1,pos3);
    }
    public static void move(char pos1,char pos2){
//        System.out.println("过程为");
        System.out.print(pos1 +"->"+ pos2+" ");
    }

声明，我们这里输入如下
hanoi(n,'a','b','c');
pos1->a
pos2->b
pos3->c
当我们输入n=3时，进入递归中，首先n！=1，所以执行hanoi(n-1,pos1,pos3,pos2);这一步，传入数据为hanoi(1,a,c,b );
这时我们进入另一次递归，也就是从头开始
在这里插入图片描述
此时传入的是hanoi(2,a,c,b);
这时n还是不等于1，则再次进入递归

这里注意每次形参的位置发生变化

在这里插入图片描述

进入第二次递归后，此时传入的是hanoi(2,a,c,b);n！=1，进入hanoi(1,a,b,c)
此时n==1，接收到move（a，c）打印a->c.这时第二次递归结束，返回第一次递归中红点这一步，因为我们上一步传入的是hanoi(2,a,c,b);
此时接收到move（a，b），这时打印出a->b.

在这里插入图片描述
这一步完成之后，进入红点下一步的hanoi(n-1,pos2,pos1,pos3);
这以后注意，n的值为2，再次进入递归，以此类推。

完整代码

public class test {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        System.out.println("请输入圆盘个数：");
        int n=sc.nextInt();
        System.out.println("过程为");
        hanoi(n,'a','b','c');
    }
    public static void hanoi(int n,char pos1,char pos2,char pos3){
        if(n==1){
            move(pos1,pos3);
            return;
        }
        hanoi(n-1,pos1,pos3,pos2);
        move(pos1,pos3);
        hanoi(n-1,pos2,pos1,pos3);
    }
    public static void move(char pos1,char pos3){
//        System.out.println("过程为");
        System.out.print(pos1 +"->"+ pos3+" ");
    }
}