汉诺塔问题

一、介绍

汉诺塔（Tower of Hanoi），又称河内塔，是一个源于印度古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。

大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。介绍来源于百度知道。

我小时候也玩过，但当时就是云里雾里的，不知道怎么去解题，简单的可以完成，难的就不行了。

到了现在，如何用代码解题，依旧是一个不小的难度，反正我是得琢磨一会。

二、解题思路

有三根柱子，分别是起始的柱子，辅助的柱子，目标的柱子，我们需要将圆盘从开始移动到目标。

但由于汉诺塔的这项规则，在小圆盘上不能放大圆盘上，我们就可以将其分为两部分，分为上面一部分，下面一部分。

下面一部分永远比上面一部分要大，所以需要先将上面这一部分移动到辅助的位置。

当上面这部分有多个时，照样看成上下两部分，上面部分移动到辅助位置（最开始的目标位置，现在变成了辅助位置）

如此重复执行，直到完成所有的迁移。

大家可以先试试这个小游戏，找找灵感

代码如下，主要使用到了递归

package com.banmoon.algorithm.classical;

public class Hanoi {

    public static void main(String[] args) {
        hanoi(3, 'A', 'B', 'C');
    }

    /**
     * 移动汉诺塔
     * @param i 当前的盘子
     * @param from 开始的位置
     * @param assist 辅助的位置
     * @param to 目标的位置
     */
    public static void hanoi(int i, char from, char assist, char to) {
        // 将盘子看成两部分，最下面的一个，和最上面的所有
        if (i == 1) {
            // 如果仅有一个盘子，直接移动即可
            System.out.println(String.format("将第%s个盘子从%s移动到%s", i, from, to));
        }
        else {
            // 将上面的所有移动到，辅助位置（如此一来，辅助位置就变成了此处的目标位置）
            hanoi(i-1, from, to, assist);
            // 将当前的盘子移动到目标位置
            System.out.println(String.format("将第%s个盘子从%s移动到%s", i, from, to));
            // 将目前处于辅助位置的盘子，分成两部分，上面部分移动到原先开始的位置，下面部分移动到目标位置
            hanoi(i-1, assist, from, to);
        }
    }

}