`
qzww5324
  • 浏览: 37241 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

汉诺塔(Hanoi)

阅读更多

      汉诺塔(Towers of Hanoi)是法国人M.Claus(Lucas)于1883年从泰国带至法国的,河内(Hanoi)为越战时北越的首都,即现在的胡志明市;1883年法国数学家 Edouard Lucas曾提及这个故事,据说创世纪时Benares有一座波罗教塔,是由三支钻石棒(Pag)所支撑,开始时神在第一根棒上放置64个由上至下依由小 至大排列的金盘(Disc),并命令僧侣将所有的金盘从第一根石棒移至第三根石棒,且搬运过程中遵守大盘子在小盘子之下的原则,若每日仅搬一个盘子,则当 盘子全数搬运完毕之时,此塔将毁损,而也就是世界末日来临之时。     

      以三根柱子A,B,C为例,初始情况下,在A上有n个盘子。

逐步分析n在不同情况时的操作步骤。

 

当n=1时: 将盘子从A 移到 C (A->C) 完成移动。

当n=2时: (1)将n-1(即 1)个盘子从A移动到B;

                (2)将A上最后一个盘子从A移动到C;

                (3)将B上的盘子移动到C上 完成移动;

当n=3时: (1)将n-1(即 2)个盘子从A移动到B(借助C)

                       具体步骤:(a)假设 要从A移动的n-1个盘子为 m,将 m-1(即 1)个盘子从A移动到C;

                                     (b)将m个盘子中剩余的盘子(这里 剩余1个)从A移动到B;

                                     (c)将C上的那个盘子移动到B,完成移动;

                (2)将A上最后一个盘子从A移动到C;

                (3)将B上剩余的盘子移动到C(借助A)

                        具体步骤:(a)同样假设B上要移动的盘子数为m,将 m-1个盘子从B移动到A;

                                      (b)将m个盘子中剩余的盘子(这里 剩余1个)从B移动到C;

                                      (c)将A上的那个盘子移动到C,完成移动;

 

 

总结以上的步骤,当n>1时,操作步骤都可以分为三大步,而n>2时1,3两个步骤又都包含了三个类似的步骤,不同的地方仅在 移动的起始点(A),借助点(B)和 目的点 (C),以这三个值做为参数,再加上盘子数,可用以下代码表示。

 

public class Hanoi {
	 public static void main(String args[]) throws IOException {
	        int n;
	        BufferedReader buf;
	        buf = new BufferedReader(new InputStreamReader(System.in));

	        System.out.print("请输入盘数:");
	        n = Integer.parseInt(buf.readLine());

	        Hanoi hanoi = new Hanoi();
	        hanoi.move(n, 'A', 'B', 'C');
	    }

	    public void move(int n, char a, char b, char c) {
	        if(n == 1)
	        	//从a,移到 c
	            System.out.println("盘 " + n + " 由 " + a + " 移至 " + c);
	        else {
	        	//从a,借助c,移到 b
	            move(n - 1, a, c, b);
	            //从a,移到 c
	            System.out.println("盘 " + n + " 由 " + a + " 移至 " + c);
	            //从b,借助a,移到 c
	            move(n - 1, b, a, c);
	        }
	    }
}

 

以3个盘子为例 输出结果:

请输入盘数:3
盘 1 由 A 移至 C
盘 2 由 A 移至 B
盘 1 由 C 移至 B
盘 3 由 A 移至 C
盘 1 由 B 移至 A
盘 2 由 B 移至 C
盘 1 由 A 移至 C
 

 

 

 

 

 

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics