Java算法一：汉诺塔
Java算法一：汉诺塔（河内塔Towers of Hanoi）
问题说明：
汉诺塔：又称河內塔(Towers of Hanoi)是法国人M.Claus(Lucas)于1883年从泰国带至法国的，河內为越战时北越的首都，即现在的胡志明市；1883年法国数学家 Edouard Lucas曾提及这个故事，据说创世纪时Benares有一座波罗教塔，是由三支钻石棒（Pag）所支撑，开始时神在第一根棒上放置64个由上至下按照由小至大排列的金盘（Disc），并命令僧侣将所有的金盘从第一根石棒移至第三根石棒，且搬运过程中遵守大盘子在小盘子之下的原则，若每日仅搬一个盘子，则当盘子全数搬运完毕之时，此塔将损毁，而也就是世界末日來临之时。
另一个版本：（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
传说不重要，大致思想是一致的。
解法：
假设三个柱子分别位A、B、C。有n个盘子，实际上就是将n-1个盘子先移到辅助柱子B上，再将最后一个盘子移到目标柱C柱上。然后再设法将B柱上的n-1个盘子移到C柱上。这里需要用到一个递归的思想。
运行结果：
Java代码：
|
package com.allen;
import java.math.BigInteger; import java.util.Scanner;
public class Hanoi { public static void main(String[] args) { System.out.println("请输入n个盘子："); Scanner cin = new Scanner(System.in); while(cin.hasNext()){ int n=cin.nextInt(); char x='A',y='B',z='C'; haoi(n,x,y,z); } cin.close(); } static void haoi(int n, char source,char depend,char purpose) { if(n==1) { move(n,source,purpose); } else { haoi(n-1,source,purpose,depend); move(n,source,purpose); haoi(n-1,depend,source,purpose); } } static int i=1; static void move(int n, char source,char purpose) { System.out.println("第"+(i++)+"步：将盘子"+n+"从"+source+"-------->移到"+purpose); } } |