汉诺塔算法

package org.bestupon.algorithm;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * 
 * @author BestUpon
 * @email [email protected]
 * @date 2010-5-28下午09:57:20
 * @ask 据说创世纪时Benares有一座波罗教塔，是由三支钻石棒（Pag）所支撑，开始时神在第一根棒上放置64个由上至下依由小至大排列的金盘
 *      （Disc），并命令僧侣将所有的金盘从第一根石棒移至第三根石棒，且搬运过程中遵守大盘子在小盘子之下的原则，若每日仅搬一个盘子，
 *      则当盘子全数搬运完毕之时，此塔将毁损，而也就是世界末日来临之时。
 * @answer 如果柱子标为ABC，要由A搬至C，在只有一个盘子时，就将它直接搬至C，当有两个盘子，就将B当作辅助柱。如果盘数超过2个，
 *         将第三个以下的盘子遮起来，就很简单了，每次处理两个盘子，也就是：A->B、A ->C、B->C这三个步骤，而被遮住的部份，
 *         其实就是进入程序的递归处理。事实上，若有n个盘子，则移动完毕所需之次数为2^n-1，所以当盘数为64时， 则所需次数为： 
 *         2^64- 1 =18446744073709551615 为5.05390248594782e+16年，也就是约5000世纪，
 *         如果对这数字没什么概念，就假设每秒钟搬一个盘子好了，也要约5850亿年左右。
 * @next  对于这类的问题，一般都是递归的解决办法，如何实现将递归问题非递归化？思考中...
 */
public class Towers_of_Hanoi {

	public static void main(String[] args) {
		int discNum = 3;
		BufferedReader input = null;
		input = new BufferedReader(new InputStreamReader(System.in));

		System.out.println("请输入柱子的数目：");
		String discNumStr = "3";
		try {
			discNumStr = input.readLine();
			discNum = Integer.parseInt(discNumStr);
		} catch (NumberFormatException e) {
			discNum = 3;
			System.out.println("你输入的" + discNumStr + "不是数字!默认取值3个盘子");
		} catch (IOException e) {
			e.printStackTrace();
		}
		Towers_of_Hanoi.moveDisc(discNum, "A", "B", "C");
	}

	/**
	 * 
	 * @param discNum
	 *            盘子的数量
	 * @param pagA
	 *            柱子A 源柱子
	 * @param pagB
	 *            柱子B 辅助柱子
	 * @param pagC
	 *            柱子C 目的柱子
	 */
	private static void moveDisc(int discNum, String pagA, String pagB,
			String pagC) {
		if (discNum == 1) {
			/*
			 * 如果是盘子数是一个的话，直接将这个盘子移动到柱子C就可以了
			 */
			System.out.println("盘  " + discNum + " 由 " + pagA + " 移至 " + pagC);
		} else {
			/*
			 * 如果有2个盘子的话，要以pagB做辅助，首先将最上面的disc1 移至pagB,在将disc2移至pagC，
			 * 接着将disc1移至pagC。如果盘数超过2个， 将第3个以下的盘子遮起来，就很简单了，每次处理2个盘子，
			 * 也就是：pagA->pagB、pagA->pagC、pagB->pagC这三个步骤，而被遮住的部份， 其实就是进入程序的递归处理。
			 * 事实上，若有n个盘子，则移动完毕所需之次数为2^n-1
			 */
			moveDisc(discNum - 1, pagA, pagC, pagB);// 做pagA->pagB的操作
			System.out.println("盘  " + discNum + " 由 " + pagA + " 移至 " + pagB);
			moveDisc(discNum - 1, pagB, pagA, pagC);// 做pagB->pagC的操作
			/**
			 * 其中pagA->pagC 的过程是迭代的过程
			 */
		}
	}

}