问题描述

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

解决思路

设从左到右三根柱子分别为A、B、C。

第1步：想办法将A上的n-1个圆盘经过C移动到B；

第2步：将A上的第n个圆盘直接移动到C；

第3步：想办法将B上的n-1个圆盘经过C移动到A。

重复以上步骤，直到所有的圆盘都移动到C。

代码实现

/**
 * 使用递归解决汉诺塔问题
 */
public void moveHanio(int n, String from, String buffer, String to) {
    if (n == 0) {
        return;
    }
    moveHanio(n - 1, from, to, buffer);
    System.out.println(String.format("%s -> %s", from, to));
    moveHanio(n - 1, buffer, to, from); // 恢复至原始问题，但问题规模减小1
}