来公司一年多，经理就没接到什么像样的项目，大部分时间都是去支援别的项目组；我支援过测试、支援过对日外包、支援过CGI的项目、支援过.net......叫我干这些无聊的工作也就算了，经理还美其名曰“多学点东西啊，干软件的就要懂得东西多......”,我去，理由真好。唯一做过的一次JavaWeb项目，技术含量也不是很多，都是些数据库的CRUD和前台Dom的CRUD。
而且工资一直没涨，太憋屈，我就辞了。
吐槽结束。
为什么和大家一起来讨论汉诺塔呢？因为传说中，汉诺塔早在远古时期就和“世界末日”绑定在一起，今天就用这个帖子纪念我的第一次辞职和伟大的世界末日。
相信大家一定对汉诺塔有映像，我就不做过多的解释了。
以下是百度百科上的原文(http://baike.baidu.com/view/191666.htm)：一位法国数学家曾编写过一个印度的古老传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。
不管这个传说的可信度有多大，如果考虑一下把64片金片，由一根针上移到另一根针上，并且始终保持上小下大的顺序。这需要多少次移动呢?这里需要递归的方法。假设有n片，移动次数是f(n).显然f(1)=1,f(2)=3,f(3)=7，且f(k+1）=2*f(k)+1。此后不难证明f(n)=2^n-1。n=64时，
f（64）= 2^64-1=18446744073709551615
假如每秒钟一次，共需多长时间呢？一个平年365天有 31536000 秒，闰年366天有31622400秒，平均每年31556952秒，计算一下，
18446744073709551615/31556952=584554049253.855年
这表明移完这些金片需要5845亿年以上，而地球存在至今不过45亿年，太阳系的预期寿命据说也就是数百亿年。真的过了5845亿年，不说太阳系和银河系，至少地球上的一切生命，连同梵塔、庙宇等，都早已经灰飞烟灭。
我想大家一定都能理解汉诺塔的递归算法，早在谭浩强(个人认为谭浩强和严蔚敏都是计算机教育界的顶尖大师)的书上，汉诺塔递归以及斐波那契的递归是作为范例讲的；以下是Java版汉诺塔的递归源码： public void hannoi(int num,String from,String with,String to)
{
if(num==1){
//递归出口!
System.out.println("盘子:"+1+from+">>>>"+to);
}else{
hannoi(num-1,from,to,with);
System.out.println("盘子:"+num+from+ ">>>>" +to);
hannoi(num-1,with,from,to);
}
}
public static void main(String[] args) {
Hannoi h = new Hannoi();
h.hannoi(3, "A","B","C");
}
用文字描述“某一趟汉诺移动”，算法是这样的：
1、对于第num个盘子的“汉诺移动”，都需要传入三个参数 盘子号num、开始柱from、借助柱with、目标柱to；
2、先把本次的from柱作为num-1个盘子的from柱，本次to柱作为num-1个盘子的with柱，本次的with柱作为num-1个盘子的to柱，对num-1个盘子进行“汉诺移动”；
3、再把本次的盘子从from柱移动到to柱；
4、然后，由于本次的盘子已经在to柱，而num-1个盘子全在with柱，所以需要把num-1个盘子从with柱借助于from柱移动to柱，即：hannoi(num-1,with,from,to)
用递归描述起来似乎很简单，但对于某些逻辑思维不强的人来说，他们还是一知半解，主要会出现以下两个疑问：
1、虽然能用程序写出来，但程序的内部是如何进行构建和运行的呢？
2、如果手边只有一张纸、一支笔，没有VisualStadio、没有Eclipse、甚至没有NotePad，如何
用最短的时间把解决步骤写出来？
下面，听我来详细解释。
一、把算法和我们接触过的模型结合起来。
仔细观察一下汉诺塔的递归算法，就会发现，它和二叉树的中序遍历基本一致。
中序遍历的文字描述：
若二叉树为空则结束返回，
否则：
（1）中序遍历左子树。
（2）访问根结点。
（3）中序遍历右子树。
Java版算法：
class TreeNode{
public int data;
public TreeNode leftChild;
public TreeNode rightChild;
public static void inOrderTraversal(TreeNode node){
if(node == null){
return;
}else{
inOrderTraversal(node.leftChild);
System.out.println(node.data);
inOrderTRaversal(node.rightChild);
}
}
}我记得数据结构的“划重点课”上（前面的课我都没咋去），老师曾经说过这样一句话：
二叉树的先序遍历、中序遍历、后序遍历、层序遍历四种遍历是所有树和图、所有非线性算法的基础和原理，必须牢牢掌握这四种算法的递归(层序遍历一般不递归)以及非递归；掌握不了这四种算法，就无法掌握高级的排序和查找，也无法学好下学期的算法课，写的程序就永远是入门的、线性的、低效率的。
以前我没怎么好好学习数据结构，也不太理解他的这句话，导致我以后的算法课是抄别人的抄过的，毕设也是抄的，后来又被学校推荐到了一个不太好的公司，接着后面工作无聊，辞职......看来老师说的真对。
回到我们的汉诺塔话题，结合二叉树的中序遍历，我们很容易就画出3阶汉诺塔的空间递归树：
中序遍历这个二叉树，遍历某个节点时，输出from和to，with无须输出，就可以得到3阶汉诺塔的移动顺序：
盘子:1A>>>>C
盘子:2A>>>>B
盘子:1C>>>>B
盘子:3A>>>>C
盘子:1B>>>>A
盘子:2B>>>>C
盘子:1A>>>>C
可以看到，汉诺塔算法所生成的二叉树是一个相当完美的“完全二叉树”，所以它的总节点数是2^3-1=7个。
二、先简化一下算法；通过层序遍历，构建双链表；顺序遍历双链表，输出！
1、再仔细观察一下递归树，例如第一层的节点：A--null--C,“分裂成”了第二层的两个节点：A--C--B和B--A--C，而第二层的第一个节点A--C--B,又“分裂成”了：A--null--C和C--null--B。简化一下:如果不考虑with柱，只考虑from和to柱，AC可以分裂成AB和BC，AB可以分裂成AC和CB......相信你已经看出规律了，所以可以进一步简化为下面的递归树：2、通过队列来构造双链表：
为了实现算法，你需要写这样一个小函数：
private static final String str="ABC";
public String getWith(String from,String to){
String with;
//找出ABC中的某个和from、to都不相等的字符串，赋值给with
return with;
}
你还需要有一个节点类：/**
* 汉诺塔节点
*
*/
public class HanNode {
/**
* 盘子的编号
*/
private int num;/**
* from柱
*/
private String from;/**to柱
*
*/
private String to;/**
* 双链表中的前驱结点
*/
private HanNode pre;/**
* 双链表中的后继结点
*/
private HanNode next;
public int getNum() {
return num;
}
public void setNum(int num) {
this.num = num;
}
public String getFrom() {
return from;
}
public void setFrom(String from) {
this.from = from;
}
public String getTo() {
return to;
}
public void setTo(String to) {
this.to = to;
}
public HanNode getPre() {
return pre;
}
public void setPre(HanNode pre) {
this.pre = pre;
}
public HanNode getNext() {
return next;
}
public void setNext(HanNode next) {
this.next = next;
}
public HanNode(int num, String from, String to) {
super();
this.num = num;
this.from = from;
this.to = to;
}
public HanNode() {
super();
}
@Override
public String toString() {
return " [盘子:" + num + ", 从:" + from + "到:" + to + "]";
}}你还需要设置两个全局变量top和last作为双链表的头和尾，为了和其他的节点区分开来，设置它们的num为0；
下面的任务就是通过队列来构造双链表，对于某一趟运算：
①取出一个节点currentNode出队列，把这个currentNode的from和to传入getWith()函数，然后生成两个新的节点leftNode{num=currentNode.getNum()-1，from=from，to=with}和rightNode{num=currentNode.getNum()-1,from=with,to=to},压入队列。
②把生成的leftNode和rightNode插入到双链表中的currentNode的两端（需要断裂原来的链并生成新的链）
以第二层的第一个节点（{n-1,A,B}）为例，插入前是这个样子（为了清晰，没画头节点和尾节点）：插入后是这个样子：如此不断的出队列、入队列、插链表.....直到队列的队头节点的num为1，循环终止。
3、遍历双链表，从top.getNext()开始，依次输出，如果遇到num为0的节点，表示已经到达尾部，此时循环终止。
PS:以上非递归算法，时间复杂度和递归算法一样；非递归算法生成了2^n-1个节点，而递归算法有2^n-1个的函数压入调用栈，所以非递归算法在空间复杂度上比递归算法小。欢迎大家指正！
而且工资一直没涨，太憋屈，我就辞了。
吐槽结束。
为什么和大家一起来讨论汉诺塔呢？因为传说中，汉诺塔早在远古时期就和“世界末日”绑定在一起，今天就用这个帖子纪念我的第一次辞职和伟大的世界末日。
相信大家一定对汉诺塔有映像，我就不做过多的解释了。
以下是百度百科上的原文(http://baike.baidu.com/view/191666.htm)：一位法国数学家曾编写过一个印度的古老传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。
不管这个传说的可信度有多大，如果考虑一下把64片金片，由一根针上移到另一根针上，并且始终保持上小下大的顺序。这需要多少次移动呢?这里需要递归的方法。假设有n片，移动次数是f(n).显然f(1)=1,f(2)=3,f(3)=7，且f(k+1）=2*f(k)+1。此后不难证明f(n)=2^n-1。n=64时，
f（64）= 2^64-1=18446744073709551615
假如每秒钟一次，共需多长时间呢？一个平年365天有 31536000 秒，闰年366天有31622400秒，平均每年31556952秒，计算一下，
18446744073709551615/31556952=584554049253.855年
这表明移完这些金片需要5845亿年以上，而地球存在至今不过45亿年，太阳系的预期寿命据说也就是数百亿年。真的过了5845亿年，不说太阳系和银河系，至少地球上的一切生命，连同梵塔、庙宇等，都早已经灰飞烟灭。
我想大家一定都能理解汉诺塔的递归算法，早在谭浩强(个人认为谭浩强和严蔚敏都是计算机教育界的顶尖大师)的书上，汉诺塔递归以及斐波那契的递归是作为范例讲的；以下是Java版汉诺塔的递归源码： public void hannoi(int num,String from,String with,String to)
{
if(num==1){
//递归出口!
System.out.println("盘子:"+1+from+">>>>"+to);
}else{
hannoi(num-1,from,to,with);
System.out.println("盘子:"+num+from+ ">>>>" +to);
hannoi(num-1,with,from,to);
}
}
public static void main(String[] args) {
Hannoi h = new Hannoi();
h.hannoi(3, "A","B","C");
}
用文字描述“某一趟汉诺移动”，算法是这样的：
1、对于第num个盘子的“汉诺移动”，都需要传入三个参数 盘子号num、开始柱from、借助柱with、目标柱to；
2、先把本次的from柱作为num-1个盘子的from柱，本次to柱作为num-1个盘子的with柱，本次的with柱作为num-1个盘子的to柱，对num-1个盘子进行“汉诺移动”；
3、再把本次的盘子从from柱移动到to柱；
4、然后，由于本次的盘子已经在to柱，而num-1个盘子全在with柱，所以需要把num-1个盘子从with柱借助于from柱移动to柱，即：hannoi(num-1,with,from,to)
用递归描述起来似乎很简单，但对于某些逻辑思维不强的人来说，他们还是一知半解，主要会出现以下两个疑问：
1、虽然能用程序写出来，但程序的内部是如何进行构建和运行的呢？
2、如果手边只有一张纸、一支笔，没有VisualStadio、没有Eclipse、甚至没有NotePad，如何
用最短的时间把解决步骤写出来？
下面，听我来详细解释。
一、把算法和我们接触过的模型结合起来。
仔细观察一下汉诺塔的递归算法，就会发现，它和二叉树的中序遍历基本一致。
中序遍历的文字描述：
若二叉树为空则结束返回，
否则：
（1）中序遍历左子树。
（2）访问根结点。
（3）中序遍历右子树。
Java版算法：
class TreeNode{
public int data;
public TreeNode leftChild;
public TreeNode rightChild;
public static void inOrderTraversal(TreeNode node){
if(node == null){
return;
}else{
inOrderTraversal(node.leftChild);
System.out.println(node.data);
inOrderTRaversal(node.rightChild);
}
}
}我记得数据结构的“划重点课”上（前面的课我都没咋去），老师曾经说过这样一句话：
二叉树的先序遍历、中序遍历、后序遍历、层序遍历四种遍历是所有树和图、所有非线性算法的基础和原理，必须牢牢掌握这四种算法的递归(层序遍历一般不递归)以及非递归；掌握不了这四种算法，就无法掌握高级的排序和查找，也无法学好下学期的算法课，写的程序就永远是入门的、线性的、低效率的。
以前我没怎么好好学习数据结构，也不太理解他的这句话，导致我以后的算法课是抄别人的抄过的，毕设也是抄的，后来又被学校推荐到了一个不太好的公司，接着后面工作无聊，辞职......看来老师说的真对。
回到我们的汉诺塔话题，结合二叉树的中序遍历，我们很容易就画出3阶汉诺塔的空间递归树：
中序遍历这个二叉树，遍历某个节点时，输出from和to，with无须输出，就可以得到3阶汉诺塔的移动顺序：
盘子:1A>>>>C
盘子:2A>>>>B
盘子:1C>>>>B
盘子:3A>>>>C
盘子:1B>>>>A
盘子:2B>>>>C
盘子:1A>>>>C
可以看到，汉诺塔算法所生成的二叉树是一个相当完美的“完全二叉树”，所以它的总节点数是2^3-1=7个。
二、先简化一下算法；通过层序遍历，构建双链表；顺序遍历双链表，输出！
1、再仔细观察一下递归树，例如第一层的节点：A--null--C,“分裂成”了第二层的两个节点：A--C--B和B--A--C，而第二层的第一个节点A--C--B,又“分裂成”了：A--null--C和C--null--B。简化一下:如果不考虑with柱，只考虑from和to柱，AC可以分裂成AB和BC，AB可以分裂成AC和CB......相信你已经看出规律了，所以可以进一步简化为下面的递归树：2、通过队列来构造双链表：
为了实现算法，你需要写这样一个小函数：
private static final String str="ABC";
public String getWith(String from,String to){
String with;
//找出ABC中的某个和from、to都不相等的字符串，赋值给with
return with;
}
你还需要有一个节点类：/**
* 汉诺塔节点
*
*/
public class HanNode {
/**
* 盘子的编号
*/
private int num;/**
* from柱
*/
private String from;/**to柱
*
*/
private String to;/**
* 双链表中的前驱结点
*/
private HanNode pre;/**
* 双链表中的后继结点
*/
private HanNode next;
public int getNum() {
return num;
}
public void setNum(int num) {
this.num = num;
}
public String getFrom() {
return from;
}
public void setFrom(String from) {
this.from = from;
}
public String getTo() {
return to;
}
public void setTo(String to) {
this.to = to;
}
public HanNode getPre() {
return pre;
}
public void setPre(HanNode pre) {
this.pre = pre;
}
public HanNode getNext() {
return next;
}
public void setNext(HanNode next) {
this.next = next;
}
public HanNode(int num, String from, String to) {
super();
this.num = num;
this.from = from;
this.to = to;
}
public HanNode() {
super();
}
@Override
public String toString() {
return " [盘子:" + num + ", 从:" + from + "到:" + to + "]";
}}你还需要设置两个全局变量top和last作为双链表的头和尾，为了和其他的节点区分开来，设置它们的num为0；
下面的任务就是通过队列来构造双链表，对于某一趟运算：
①取出一个节点currentNode出队列，把这个currentNode的from和to传入getWith()函数，然后生成两个新的节点leftNode{num=currentNode.getNum()-1，from=from，to=with}和rightNode{num=currentNode.getNum()-1,from=with,to=to},压入队列。
②把生成的leftNode和rightNode插入到双链表中的currentNode的两端（需要断裂原来的链并生成新的链）
以第二层的第一个节点（{n-1,A,B}）为例，插入前是这个样子（为了清晰，没画头节点和尾节点）：插入后是这个样子：如此不断的出队列、入队列、插链表.....直到队列的队头节点的num为1，循环终止。
3、遍历双链表，从top.getNext()开始，依次输出，如果遇到num为0的节点，表示已经到达尾部，此时循环终止。
PS:以上非递归算法，时间复杂度和递归算法一样；非递归算法生成了2^n-1个节点，而递归算法有2^n-1个的函数压入调用栈，所以非递归算法在空间复杂度上比递归算法小。欢迎大家指正！
初始化count=0,遍历双链表的时候，每调用一次getNext()，count++,这样可以给出每一步是什么动作。
为什么，本人更觉得你是卖国的呢？
看了你许多的评论，尽说些与IT本行业毫不相关的话题。
而且都在些技术贴上，小女子看嘛，你根本就是贼喊捉贼。
别人辞职也算是卖国，别人靠自己的能力移民外国也算是卖国，某些部门尽干些不得人心的事，没见过他有什么意见。
别以为全世界程序员都像ououpp那样，上网发贴有工资！
一遇到不同意见，就给别人戴上大顶帽子，接着再给自己上光环。
恶心！