Java河内塔问题

河内之塔(Towers of Hanoi)是法国人M.Claus(Lucas)于1883年从泰国带至法国的&＃xff0c;河内为越战时北越的首都&＃xff0c;即现在的胡志明市&＃xff1b;1883年法国数学家 Edouard Lucas曾提及这个故事&＃xff0c;据说创世纪时Benares有一座波罗教塔&＃xff0c;是由三支钻石棒&＃xff08;Pag&＃xff09;所支撑&＃xff0c;开始时神在第一根棒上放置64个由上至下依由小至大排列的金盘&＃xff08;Disc&＃xff09;&＃xff0c;并命令僧侣将所有的金盘从第一根石棒移至第三根石棒&＃xff0c;且搬运过程中遵守大盘子在小盘子之下的原则&＃xff0c;若每日仅搬一个盘子&＃xff0c;则当盘子全数搬运完毕之时&＃xff0c;此塔将毁损&＃xff0c;而也就是世界末日来临之时。事实上&＃xff0c;若有n个盘子&＃xff0c;则移动完毕所需之次数为2^n - 1&＃xff0c;所以当盘数为64时&＃xff0c;则所需次数为&＃xff1a;2⁶⁴- 1 &＃61; 18446744073709551615 为5.05390248594782e&＃43;16年&＃xff0c;也就是约5000世纪&＃xff0c;如果对这数字没什么概念&＃xff0c;就假设每秒钟搬一个盘子好了&＃xff0c;也要约5850亿年左右。

思路&＃xff1a;

当只有一个盘子的时候&＃xff0c;只需要从将A塔上的一个盘子移到C塔上。

当A塔上有两个盘子是&＃xff0c;先将A塔上的1号盘子移动到B塔上&＃xff0c;再将A塔上的2号盘子移动的C塔上&＃xff0c;最后将B塔上的小盘子移动到C塔上。

 当A塔上有3个盘子时&＃xff0c;先将A塔上编号1至2的盘子&＃xff08;共2个&＃xff09;移动到B塔上&＃xff08;需借助C塔&＃xff09;&＃xff0c;然后将A塔上的3号最大的盘子移动到C塔&＃xff0c;最后将B塔上的两个盘子借助A塔移动到C塔上。

所以:

当A塔上有n个盘子是&＃xff0c;先将A塔上编号1至n-1的盘子&＃xff08;共n-1个&＃xff09;移动到B塔上&＃xff08;借助C塔&＃xff09;&＃xff0c;然后将A塔上最大的n号盘子移动到C塔上&＃xff0c;最后将B塔上的n-1个盘子借助A塔移动到C塔上。

public class Main {static int i &＃61; 1;public static void main(String[] args) {Scanner sc &＃61; new Scanner(System.in);int n &＃61; sc.nextInt();char from &＃61; &＃39;X&＃39;, depend_on &＃61; &＃39;Y&＃39;, to &＃61; &＃39;Z&＃39;;hanoi(n, from, depend_on, to);}public static void hanoi(int n, char from, char depend_on, char to) {if (n &＃61;&＃61; 1) {move(n, from, to);return;} else {hanoi(n - 1, from, to, depend_on);//X-----Ymove(n, from, to);//X-----Zhanoi(n - 1, depend_on, from, to);//Y-----Z}}public static void move(int n, char from, char to) {System.out.println("第" &＃43; (i&＃43;&＃43;) &＃43; "步:" &＃43; n &＃43; "号盘子" &＃43; from &＃43; "--------" &＃43; to);}
}