重温汉诺塔

                                                重温汉诺塔
       上高中时，在同学的文曲星上第一次看到汉诺塔这个游戏，靠着机械的背诵，勉强可以玩过几关。当时觉得很好玩，也很难，也没有多想。后来学习计算机，知道了这个汉诺塔这个东西中其实还蕴含着数学的道理，觉得是个奇妙的发明。
今天看书，突然看到了汉诺塔的解法的伪代码，觉得挺好的，于是Google了一下汉诺塔的由来，分享一下。
　                                                          汉诺塔的由来
　　汉诺塔是源自印度神话里的玩具。(一直以为是中国发明的呢，嘻嘻)
上帝创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按大小顺序摞着64片黄金圆盘。
　　上帝命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
       有人相信婆罗门至今还在一刻不停地移动着圆盘。

       也有预言说，这件事完成时宇宙会在一瞬间闪电式毁灭。但是这一天什么时候到来，还是个未知？

       

       写的还挺玄乎的，不过还挺有意思的。其实聪明的人早已算出来这天在什么时候了。呵呵，当然不是2012年啦，具体什么时候，看我娓娓道来。

       程序伪代码:

Algorithm solveTowers( numberOfDisks, startPole, tempPole, endPole)
{
     If(numberOfDisks > 0)
    {
    //所有盘子都在最左侧的柱子里，把最大的盘子以外的盘子都移动到中间的柱//子中
      solveTowers( numberOfDisks - 1, startPole, endPole, tempPole);

    //把最大的盘子移动到最右侧的柱子中
      将汉诺塔的盘子从startPole移动到endPole
  
    //把中间柱子中的盘子移到最右侧的柱子上
      solveTowers( numberOfDisks - 1, tempPole,startPole, endPole);
     } 
 
}

     看完了代码，按常理就会分析复杂度了。这类文章实在太多了，不过为了维护故事的完整性，总要写出结尾。
     话说，令m(n)表示解决n个盘子的问题所要移动的此数。显而易见，m(1) = 1 。
     对于上面的伪代码，当n > 1 时， 使用两个递归就是分别解决两个n – 1 盘子的问题。于是有
      m(n) = m(n - 1) + 1 + m( n - 1) = 2m( n - 1) + 1
      通过数学归纳，可以证明m(n) = 2^n – 1             ( n >= 1)
      于是按照剧情，m(64) = 2^64 – 1 ， 假如入移动每个盘子都要1秒的话，这个时间恐怕也要14038618016521年呢。到时候婆罗门王还玩不玩这个玩具还不知道呢。至于宇宙的存亡，嘿嘿，到时在说吧~~