汉诺塔的规则是:一共三根柱子,一根柱子从上到下套着有小到大的若干个圆盘,要将所有圆盘按照这个排放顺序移动到第三根柱子上,并且每次只能移动一个圆盘.
可以将整个过程分为三个步骤来看:
第一步:将除最大圆盘外的n-1个圆盘移动辅助柱子上
第二步:将最大的圆盘移动到目标柱子
第三步:将n-1个圆盘从辅助柱子移动到目标柱子
其中第一步又可以拆成一模一样的三步,可以看成一个n-1层的塔要移动到目标柱子,只不过目标柱子换了一个:
第三步也可以拆分成一模一样的三步:
多拆几次就会发现规律:第一步和第三步无论如何拆成更小的汉诺塔,都只是目标柱和辅助柱发生调换,其他部分都是一模一样.所以我们将第一步和第三步进行递归运算就可以解决汉诺塔问题.
static void hanNuo(int n,String A,String B,String C){
if (n==1){
System.out.println("把第"+n+"个从"+A+"移动到"+C);
}else {
hanNuo(n-1,A,C,B);
System.out.println("把第"+n+"个从"+A+"移动到"+C);
hanNuo(n-1,B,A,C);
}
}每进入一次递归塔的层数减一 ,由于第一步和第三步每拆分一次目标塔和辅助塔就会互换,同理,每进入一次递归也会将两个塔互换,因为第一步拆分目标塔是在塔二和塔三之间循环,所以我们在进入递归时也将传入代表"塔二"和"塔三"的参数互换,同理第三步也将互换代表"塔一"和"塔二"的参数.
方法中的第二步由于第一步已经递归完成,所以可以直接使用打印语句进行输出.
到此这篇关于java递归实现汉诺塔步骤介绍的文章就介绍到这了,更多相关java汉诺塔内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网！
