递归调用应用实例-汉诺塔

递归调用应用实例-汉诺塔

√汉诺塔传说

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

假如每秒钟移动一次，共需多长时间呢？移完这些金片需要5845.54亿年以上，太阳系的预期寿命据说也就是数百亿年。真的过了5845.54亿年，地球上的一切生命，连同梵塔、庙宇等，都早已经灰飞烟灭

分析 :

在思考这个问题的时候 ,我们可以想 ,假设没有那么多的盘子 ,而是仅仅只有一大一小两个盘子的话 ,这个操作就很简单 ,首先将大的盘子移动到C的位置 ,小一点的盘子移动到B的位置(假设两个盘子的位置都在A处) ,通过将两个盘分开 ,之后再将小的盘子放到大盘子上就完成了所有的盘子的移动

既然2个盘子的情况十分简单的话 ,那么不妨将无论多少盘子都思考为 ,最下面一张盘为一张盘 ,上面的复数张盘子都是一张盘的思维方式 ,之后将上面所有的盘子移动到一个位置和最下面的盘子分开之后 ,在合到一起即可(也就是上面的所有盘子移动到B ,下面的移动到C ,再将上面的移动到C即完成了重合)

代码示例

public class HanoiTower {
    public static void main(String[] args) {
        Tower t1 = new Tower();
        t1.move(5,'A','B','C');
    }
}
​
class Tower {
    //num表示要移动的个数 a,b,c表示对应的塔
    public void move(int num, char a, char b, char c)
    {
        //如果只有一个盘 num = 1
        if (num == 1){
            System.out.println(a + "->" + c);
        }else {
            move(num - 1, a , c , b);
            //移动上面所有盘从a到b ,但是借助c
            System.out.println(a + "->" + c);
            //把最下面的盘移动到c
            move(num - 1, b , a , c);
            //再把b塔的所有盘移动到c(借助a塔)即可完成移动
        }
​
    }
}

代码分析 (这里我们仍然使用了递归来解决这个问题)

class Tower
//这里定义了一个汉诺塔类

public void move(int num, char a, char b, char c)
//这里定义了一个move方法,由于是通过打印的方式将移动的过程展现出来,因此并没有返回值
//传入的三个参数分别为 想要查看移动的盘子数量
//后面的三个字符参数分别对应三个塔

if (num == 1)
//判断假设我们传入的数量为1的话,那就没有递归的必要
//直接将这一个盘子移动到C塔即可

else {
      move(num - 1, a , c , b);
      //移动上面所有盘从a到b ,但是借助c
      System.out.println(a + "->" + c);
      //把最下面的盘移动到c
      move(num - 1, b , a , c);
      //再把b塔的所有盘移动到c(借助a塔)即可完成移动
      }
//这里的else就采用我们之前提出的方法,也就是将所有的盘子看成上面所有的盘子,下面最后的一个盘子
//将二者认定为两个盘子来进行移动操作
move(num - 1, a , c , b);
//num-1表示除开下面一个盘子的剩余盘子,a,c,b如代码下的注释一致
//也就是将上面的-1的盘子递归移动到b塔中去,移动结束之后只剩下了最下面一个盘
System.out.println(a + "->" + c);
//移动a塔中剩余的盘子到c塔
//此时三塔的情况就是剩余的塔在b塔,最后一个盘子在c塔
move(num - 1, b , a , c);
//这个操作就是将b塔中的剩余盘子移动到c塔的盘子上面即可完成移动的操作
​
​
​