汉诺塔算法
package org.bestupon.algorithm;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;/** ** @author BestUpon * @email bestupon@foxmail.com * @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 的过程是迭代的过程 */}}}
页:
[1]