汉诺塔问题

梦里梦外; 2021-09-28 17:06 457阅读 0赞

汉诺塔(Tower of Hanoi)源于印度传说中，大梵天创造世界时造了三根金钢石柱子，其中一根柱子自底向上叠着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

若给汉诺塔传说中三根柱子分别用英文字母a,b,c命名，其中只有a柱子摆放n片圆盘(1<=n<=100000), 若要把a柱子上的所有圆盘转移到c柱子上，问最少需要移动多少次圆盘。

移动圆盘的规则如下：

1.  每次只能移动一片圆盘
2.  直径大的圆盘必须摆放在直径小的圆盘之上

问题：打印圆盘在每根柱子上的移动情况；计算圆盘移动的次数。

**递归思路：**我们的目标是在遵守规则的情况下把一根柱子上的盘子全部都移动到另一根柱子上，在三根柱子中假设其中一根为源柱，其中一根为目标柱，最后一根为辅助柱。源柱即所要移动圆盘的柱子，目标柱即圆盘所要移向的柱子，辅助柱即为了保持圆盘小的在上大的在下暂存盘子的柱子。递归是一种描述重复子问题的思想也是一种逆思想，在这里我们可以把1~（n-1）移动到辅助柱看作一步，然后把第n个盘子移动到目标柱，再然后把移动到辅助柱上的盘子也看作一个整体（此时源柱、目标柱、辅助柱已经改变：辅助柱已经变成源柱,目标柱仍是目标柱,源柱已变成辅助柱），再将辅助柱子的盘子挪到原空间上去。

**步骤：**

在这里，把A看作源柱（source）、B看作目标柱（goal）、C看作辅助柱（help），为了方便记忆下面代码直接写出各个英文单词。

1.  把1~（n-1）从A移动到C，把B作为辅助
2.  把n从A移动到B
3.  把1~（n-1）从C移动到B（柱的角色已经改变且把已经移动到C柱上的盘子看作一个子问题），把A作为辅助

**代码：**

static void hanoiTower(int n,String  source,String goal,String help) {//此为最终结果:我们要把n个盘子从源(柱1)移动到目标(柱2)
            if(n==1) {//出口
                System.out.println("move " +n+ "  from "+source + " to "+goal);
                return;
            }
            hanoiTower(n-1,source,help,goal);//第二步,将n-1个盘子从源柱挪到辅助柱子,此时以目标柱为辅助
            System.out.println("move " +n+ " from  "+source + " to "+goal);
            hanoiTower(n-1,help,goal,source);//第三步,此时辅助柱已经变成源柱,目标柱仍是目标柱,源柱已变成辅助柱,将辅助柱子的盘子挪到原空间上去
        }

再计算所有盘子移动的次数时，将方法中所有的输出语句改成计数语句即可。