软件编程
位置：首页>> 软件编程>> java编程>> java递归实现汉诺塔步骤介绍

java递归实现汉诺塔步骤介绍

作者：zzz45611　　发布时间：2022-03-03 09:44:17　

标签：java,汉诺塔

        汉诺塔的规则是:一共三根柱子,一根柱子从上到下套着有小到大的若干个圆盘,要将所有圆盘按照这个排放顺序移动到第三根柱子上,并且每次只能移动一个圆盘.

        可以将整个过程分为三个步骤来看:

java递归实现汉诺塔步骤介绍

第一步:将除最大圆盘外的n-1个圆盘移动辅助柱子上

第二步:将最大的圆盘移动到目标柱子

第三步:将n-1个圆盘从辅助柱子移动到目标柱子

其中第一步又可以拆成一模一样的三步,可以看成一个n-1层的塔要移动到目标柱子,只不过目标柱子换了一个:

java递归实现汉诺塔步骤介绍

第三步也可以拆分成一模一样的三步: 

java递归实现汉诺塔步骤介绍

        多拆几次就会发现规律:第一步和第三步无论如何拆成更小的汉诺塔,都只是目标柱和辅助柱发生调换,其他部分都是一模一样.所以我们将第一步和第三步进行递归运算就可以解决汉诺塔问题.

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);
    }
   }

        每进入一次递归塔的层数减一 ,由于第一步和第三步每拆分一次目标塔和辅助塔就会互换,同理,每进入一次递归也会将两个塔互换,因为第一步拆分目标塔是在塔二和塔三之间循环,所以我们在进入递归时也将传入代表"塔二"和"塔三"的参数互换,同理第三步也将互换代表"塔一"和"塔二"的参数.

        方法中的第二步由于第一步已经递归完成,所以可以直接使用打印语句进行输出.

来源：https://blog.csdn.net/zzz45611/article/details/122380248

0
投稿

猜你喜欢

手机版 软件编程 asp之家 www.aspxhome.com