辞职了，散分！并改进一上汉诺塔的算法

辞职了，散分！并改进一下汉诺塔的算法。
    来公司一年多，经理就没接到什么像样的项目，大部分时间都是去支援别的项目组；我支援过测试、支援过对日外包、支援过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版汉诺塔的递归源码：

中序遍历这个二叉树，遍历某个节点时，输出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;
}
你还需要有一个节点类：

插入后是这个样子：

如此不断的出队列、入队列、插链表.....直到队列的队头节点的num为1，循环终止。
3、遍历双链表，从top.getNext()开始，依次输出，如果遇到num为0的节点，表示已经到达尾部，此时循环终止。
PS:以上非递归算法，时间复杂度和递归算法一样；非递归算法生成了2^n-1个节点，而递归算法有2^n-1个的函数压入调用栈，所以非递归算法在空间复杂度上比递归算法小。

欢迎大家指正！
              
[解决办法]
分析得真透彻！！！
[解决办法]
帮顶，应该写在博客里啊
[解决办法]
+++++1 
 
[解决办法]
学习了，膜拜中。。。。
[解决办法]

[解决办法]
看看，飘过！！！！！！！
[解决办法]
长见识了！！！！
[解决办法]
好像分析的很到位的样子
[解决办法]
这对于一些初学者来说，简直就是身边的老师
[解决办法]
正好没分发帖
[解决办法]
过来学习下。
[解决办法]
盘子数量为奇数和偶数，每一步是不一样的。
[解决办法]
如此计算下去，队列和链表都在不停地加长，虽然不是严格的递归算法，但还是有递归的痕迹。
[解决办法]

[解决办法]
学习了
[解决办法]

[解决办法]
下雪天的，来冒个泡泡吧，有点小冷
[解决办法]
刚开始还以为是个女吊丝，唉，这年头程序猿伤不起呀。祝愿能找到好的工作。
[解决办法]
话说看不懂的说，标记一下，以后过来看。
[解决办法]
你的女神不错哦
[解决办法]

[解决办法]
不错 ，顺便接分 
[解决办法]
高手啊，看不懂了。。。
[解决办法]
 
 

我试过。。
[解决办法]
引用:
楼主是男的

我试过。。


LZ 是男的  你试过 的意思是？

哦 好吧。。 我懂了~~~~
[解决办法]
干嘛说点什么就老拿人类地球宇宙毁灭作为最后结局那，真他妈庸俗无耻。
[解决办法]
牛，收藏了!!!!