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 的过程是迭代的过程
*/
}
}
}
分享到:
相关推荐
程序设计 汉诺塔算法演示
这是个汉诺塔程序,在调试的时候,输入的数字最好不要大于15,因为每大一个数 所得的结果的步骤都会多一倍。如果你有耐心等待结果的话除外。汉诺塔是在欧洲 流行的一种游戏,有a,b,c三个竿。a竿上有若干个由大到小的...
汉诺塔的算法流程 仅供参考,本程序,可以实现N个盘子的汉诺塔排序,并在屏幕上显示操作步骤
采用C++ Buidler开发环境,C++ 语言,结合线程技术,将经典的汉诺塔算法的执行过程动态的演示出来,对于用户理解汉诺塔算法产生巨大的帮助
汉诺塔 (又称河内塔)问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放...
汉诺塔算法的递归与非递归实现 汉诺塔算法是程序设计中的经典递归问题,来源于印度古老的传说。问题的描述是:有三根金刚石的棒,第一根上面套着 64 个圆的金片,最大的一个在底下,其余一个比一个小,依次叠上去,...
知道汉诺塔的同学,有想知道其中原理的,可以看看,一个小游戏,需要源码的发邮件至:568954956@qq.com,VS2010
这个程序是汉诺塔算法的可视化软件,如果在学习这个算法但是始终搞不清时可以使用这个软件帮助理解。
汉诺塔算法 C++ 有截图 结果如下: 请输入盘子数:4 各步骤如下: A-->B A-->C B-->C A-->B C-->A C-->B A-->B A-->C B-->C B-->A C-->A B-->C A-->B A-->C B-->C 总步骤数为:15 Press any key to continue
数据结构 汉诺塔算法
一步步演示汉诺塔算法的执行流程
汉诺塔算法的演示,比较简单
网上看来的,比较详细。包含了递归以及不用递归的代码。 C和C++版的都有。
里面有递归和非递归算法,画图板,换位递归
//程序实现了mystack栈的声明和定义,并且通过函数 //move_stacks的递归调用和函数move_a_ring实现汉 //诺塔的算法,并用函数print_stacks和pr_chars实现汉诺 //塔的动画效果
今天看到了汉诺塔算法,自己实现了,并将移动过程在界面上演示出来,共入门的参考。
VC 汉诺塔算法
VC++汉诺塔算法.7z