java数据算法-汉诺塔

1、有三根相邻的柱子，标号为A,B,C。

2、A柱子上从下到上按金字塔状叠放着n个不同大小的圆盘。

3、现在把所有盘子一个一个移动到柱子C上，并且每次移动同一根柱子上都不能出现大盘子在小盘子上方。

题解步骤

1、当n=1时；

将1号从A移动到C即可

2、当n=2时；

第一步：将1号从A移动到B

第二步：将2号从A移动到C

第三步：将1号从B移动到C

3、当n=3时；

第一步：将1号从A移动到C

第二步：将2号从A移动到B

第三步：将1号从C移动到B

第四步：将3号从A移动到C

第五步：将1号从B移动到A

第六步：将2号从B移动到C

第七步：将1号从A移动到C

......

由上述可以看出，每次都会有将最大的一个从A移动到C的步骤。假如有n（n>1）个需要移动的盘子，我们可以将这些步骤分为3步：

1、将1到n-1的盘子通过C的辅助从A移动到B

2、将第n个盘子移动到C

3、将1到n-1de盘子通过A辅助从B移动到C

由此我们可以想到用递归的方法。
 

/*** @see [相关类/方法]（可选）* @since [产品/模块版本] （可选）*/
public class HanoiTower {public static void hanoi(int n, String a, String b,String c) {if (n == 1) {// 只有一个圆盘时直接从A石柱移动到C石柱move(n, a, c);} else {// 将前n-1个圆盘从石柱A移动到石柱Bhanoi(n - 1, a, c, b);// 将第n号圆盘从石柱A移动到石柱Cmove(n, a, c);// 将前n-1个圆盘从石柱B移动到石柱Chanoi(n - 1, b, a, c);}}public static void move(int n, String i, String j) {System.out.println("第" + n + "个圆盘，" + "从" + i + "移动到" + j);}public static void main(String[] args) {hanoi(2,"A","B","C");}
}