avascript解汉诺塔问题

传说某间寺院有三根柱子，在创世之初，第一根柱子串有64个金盘，盘的尺寸由下到上一个比一个小。寺院里的僧侣依照一个古老的预言，每天移动一个盘；大盘不能叠在小盘上面，预言说盘子全部移动到到第三根柱子时，世界就会灭亡。

最少移动步数是随着盘子的个数呈指数增长（2^n-1）的。对指数增长有概念的同学应该能够看出移动64个盘子所需的步数是个天文数字，即使僧侣们每秒可完成一个盘子的移动，也需要5846亿年才能完成，整个宇宙现在也不过137亿年。这个世界灭亡传说的本意大概是在祝福世界不要灭亡吧。

在《猩球崛起》故事中就是用同样的问题来给猩猩们测智商，用了4个盘子。

四个盘子最少需要挪动2^4-1=15步，这只猩猩最快15步就完成了，难怪科学家们要大吃一惊了。

下面是一个有7个盘子的儿童玩具，最少需要2^7-1=127步完成。

最后，用javascript编制一个递归算法，来做一做这个儿童游戏吧：

 
 


  
  
var hanoi = function(k,src,tmp,dst){  

  
  
    if(k>0){  

  
  
        hanoi(k-1,src,dst,tmp);//把上面k-1个盘子从src通过dst搬到tmp  

  
  
        iCount+=1;  

  
  
        put("iCount = " + iCount + " move disc " + k + " from " + src + " to " + dst);//把最大的盘子从src搬到dst  

  
  
        hanoi(k-1,tmp,src,dst);//把k-1个盘子从tmp通过src搬到dst  

  
  
    }     

  
  
}  

  
  
 

  
  
var iCount=0;//计数  

  
  
var n = 7; //盘子个数  

  
  
pt("Math.pow(2,"+n+")-1");  

  
  
hanoi(n,'A','B','C');  

  
  
put("~~~~~~~~~game over~~~~~~~~~~~~~~~"); 
 
 

调试信息: 
Math.pow(2,7)-1 127
iCount = 1 move disc 1 from A to C
iCount = 2 move disc 2 from A to B
iCount = 3 move disc 1 from C to B
iCount = 4 move disc 3 from A to C
iCount = 5 move disc 1 from B to A
iCount = 6 move disc 2 from B to C
iCount = 7 move disc 1 from A to C
iCount = 8 move disc 4 from A to B
iCount = 9 move disc 1 from C to B
iCount = 10 move disc 2 from C to A
iCount = 11 move disc 1 from B to A
iCount = 12 move disc 3 from C to B
iCount = 13 move disc 1 from A to C
iCount = 14 move disc 2 from A to B
iCount = 15 move disc 1 from C to B
iCount = 16 move disc 5 from A to C
iCount = 17 move disc 1 from B to A
iCount = 18 move disc 2 from B to C
iCount = 19 move disc 1 from A to C
iCount = 20 move disc 3 from B to A
iCount = 21 move disc 1 from C to B
iCount = 22 move disc 2 from C to A
iCount = 23 move disc 1 from B to A
iCount = 24 move disc 4 from B to C
iCount = 25 move disc 1 from A to C
iCount = 26 move disc 2 from A to B
iCount = 27 move disc 1 from C to B
iCount = 28 move disc 3 from A to C
iCount = 29 move disc 1 from B to A
iCount = 30 move disc 2 from B to C
iCount = 31 move disc 1 from A to C
iCount = 32 move disc 6 from A to B
iCount = 33 move disc 1 from C to B
iCount = 34 move disc 2 from C to A
iCount = 35 move disc 1 from B to A
iCount = 36 move disc 3 from C to B
iCount = 37 move disc 1 from A to C
iCount = 38 move disc 2 from A to B
iCount = 39 move disc 1 from C to B
iCount = 40 move disc 4 from C to A
iCount = 41 move disc 1 from B to A
iCount = 42 move disc 2 from B to C
iCount = 43 move disc 1 from A to C
iCount = 44 move disc 3 from B to A
iCount = 45 move disc 1 from C to B
iCount = 46 move disc 2 from C to A
iCount = 47 move disc 1 from B to A
iCount = 48 move disc 5 from C to B
iCount = 49 move disc 1 from A to C
iCount = 50 move disc 2 from A to B
iCount = 51 move disc 1 from C to B
iCount = 52 move disc 3 from A to C
iCount = 53 move disc 1 from B to A
iCount = 54 move disc 2 from B to C
iCount = 55 move disc 1 from A to C
iCount = 56 move disc 4 from A to B
iCount = 57 move disc 1 from C to B
iCount = 58 move disc 2 from C to A
iCount = 59 move disc 1 from B to A
iCount = 60 move disc 3 from C to B
iCount = 61 move disc 1 from A to C
iCount = 62 move disc 2 from A to B
iCount = 63 move disc 1 from C to B
iCount = 64 move disc 7 from A to C
iCount = 65 move disc 1 from B to A
iCount = 66 move disc 2 from B to C
iCount = 67 move disc 1 from A to C
iCount = 68 move disc 3 from B to A
iCount = 69 move disc 1 from C to B
iCount = 70 move disc 2 from C to A
iCount = 71 move disc 1 from B to A
iCount = 72 move disc 4 from B to C
iCount = 73 move disc 1 from A to C
iCount = 74 move disc 2 from A to B
iCount = 75 move disc 1 from C to B
iCount = 76 move disc 3 from A to C
iCount = 77 move disc 1 from B to A
iCount = 78 move disc 2 from B to C
iCount = 79 move disc 1 from A to C
iCount = 80 move disc 5 from B to A
iCount = 81 move disc 1 from C to B
iCount = 82 move disc 2 from C to A
iCount = 83 move disc 1 from B to A
iCount = 84 move disc 3 from C to B
iCount = 85 move disc 1 from A to C
iCount = 86 move disc 2 from A to B
iCount = 87 move disc 1 from C to B
iCount = 88 move disc 4 from C to A
iCount = 89 move disc 1 from B to A
iCount = 90 move disc 2 from B to C
iCount = 91 move disc 1 from A to C
iCount = 92 move disc 3 from B to A
iCount = 93 move disc 1 from C to B
iCount = 94 move disc 2 from C to A
iCount = 95 move disc 1 from B to A
iCount = 96 move disc 6 from B to C
iCount = 97 move disc 1 from A to C
iCount = 98 move disc 2 from A to B
iCount = 99 move disc 1 from C to B
iCount = 100 move disc 3 from A to C
iCount = 101 move disc 1 from B to A
iCount = 102 move disc 2 from B to C
iCount = 103 move disc 1 from A to C
iCount = 104 move disc 4 from A to B
iCount = 105 move disc 1 from C to B
iCount = 106 move disc 2 from C to A
iCount = 107 move disc 1 from B to A
iCount = 108 move disc 3 from C to B
iCount = 109 move disc 1 from A to C
iCount = 110 move disc 2 from A to B
iCount = 111 move disc 1 from C to B
iCount = 112 move disc 5 from A to C
iCount = 113 move disc 1 from B to A
iCount = 114 move disc 2 from B to C
iCount = 115 move disc 1 from A to C
iCount = 116 move disc 3 from B to A
iCount = 117 move disc 1 from C to B
iCount = 118 move disc 2 from C to A
iCount = 119 move disc 1 from B to A
iCount = 120 move disc 4 from B to C
iCount = 121 move disc 1 from A to C
iCount = 122 move disc 2 from A to B
iCount = 123 move disc 1 from C to B
iCount = 124 move disc 3 from A to C
iCount = 125 move disc 1 from B to A
iCount = 126 move disc 2 from B to C
iCount = 127 move disc 1 from A to C
~~~~~~~~~game over~~~~~~~~~~~~~~~

 本文转自 hexiaini235 51CTO博客，原文链接：http://blog.51cto.com/idata/1101850，如需转载请自行联系原作者