Hanoi塔递归算法实现过程

时间:2022-12-16 15:17:39


Hanoi介绍:https://baike.baidu.com/item/%E6%B1%89%E8%AF%BA%E5%A1%94/3468295


配图:

 Hanoi塔递归算法实现过程

 

编程要求:

参照配图写出函数,实现以最短步骤,将n块垫子从A全部移动到C位置,即打印出每一步的移动过程。(如A--->C,表示A位置移动到C位置的过程。)

 

初步分析:

通过观察发现移动n块垫子从AC,就需要先将n-1块(上面的垫子)移动到B位置,然后才能将最下面的垫子移动到C,最后将n-1块垫子从B移动到C

 

因为每次逻辑相似,得出一个猜想:可以递归解决这个问题……下面开始分析递归的几要素——

 

1、结束条件:很显然,垫子移动完成就结束了。

2、改变的参数:垫子数每次减1

3、共通的逻辑:移动n个垫子到C,得先将上面n-1垫子移走,然后将下面垫子移动到C,然后目标变成:将n-1个垫子移动到C,得先将上面n-2个垫子移走,然后……

 

 


小试牛刀:

 

public static void printMove(int n){

if(n==0) return;

printMove(n-1); //移动n-1

System.out.println("A--->C"); //打印移动过程

printMove(n-1); //移动n-1

}

 

执行结果:

input:printMove(2);

Output:

             Hanoi塔递归算法实现过程

input:printMove(3);

Output:

             Hanoi塔递归算法实现过程

 

分析一下结果,发现打印的次数是符合2^n-1的规律的,思考的方向是没有问题的。但是显然这样的打印结果只有AC,不符合我们要求。观察发现ABC的位置变换必须灵活的改变,可能得作为参数传入。

而且最底下垫子要移动到C,上层的垫子可能需要由AB,也可能由BA。更加确定刚才的想法,开始修改。

 

最终修改如下:(注意调用函数时参数位置的改变)

 

public static void printMove(int n,char A,char B,char C){

if(n==0) return; //垫子移动完结束

printMove(n-1,A,C,B); //将上层n-1垫子从A移到B

System.out.println(A+"--->"+C); //打印(相当于每次将最底下的垫子移动到C)

printMove(n-1,B,A,C);//将上层n-1垫子从B移到C

}

 

测试:

input:printMove(2,'A','B','C');

Output:

             Hanoi塔递归算法实现过程


input:printMove(3,'A','B','C');

Output:

             Hanoi塔递归算法实现过程


多次测试没有出现异常的情况,完。