汉诺塔问题(递归篇)

篇幅略长,但没有废话,请耐心。

汉诺塔问题是印度一个古老的游戏。有3根柱子(A,B,C),A柱子上从上到下,排列了从小到大的若干个盘子,要求将盘子从A搬到C。

规则:1、一次搬动一个

   2、只有最上面的盘子能被搬动。

   3、大盘子不可放到小盘子的上方。

从简到繁的推理下:

1、如果A上有1个盘子,搬到C上只需要1步。

2、如果A上有2个盘子,需要A1搬到B,A2搬到C,再将A1搬到C,需要搬动3步。

3、如果A上有3个盘子,如下图: 8个图,搬动了7次。

 

汉诺塔问题(递归篇)

                图一

4.如果A上有4个盘子,如下图:需要15步骤。

汉诺塔问题(递归篇)

              图二

 

好了,可以推理下了。

n=1 (1)   n=2(3)  n=3(7)  n=4(15)

哈哈哈,火眼金睛的我已经看出来了,Tn = 2^n - 1。  什么?你说 Tn = 2Tn-1 + 1。  嗯。。。貌似也对。数学归纳法证明下二者是不是有联系。

想了想,证明啥啊,这是考算法啊,还是考数学啊?

再仔细观察图二中的第7,8两步。如果把B柱子看成A,把A看成B,去掉C的盘子,这不就是图一吗。这么一看,确实是Tn = 2Tn-1 + 1。

Tn,Tn-1 了解了,递归啊。

javascript 按照步骤写个思路。

/**
* @param {Object} n n个盘子
* @param {Object} a 初始盘在所在的柱子
* @param {Object} c 最终挪到的柱子
* @param {Object} b 可借用的柱子
*/
function towersOfHnt(n,a,c,b){
  if(n >= 1){
    towersOfHnt(n-1,a,b,c);    //此步骤可以看成是图二中的前7步,将A中的盘子挪到B
    

    console.log("从"+a.name+"["+a.value+"]搬动一只盘子到"+c.name+"["+c.value+"]");
    c.value.splice(0,0,a.value[0]);
    a.value.splice(0,1);      //此步骤可以看成第8步骤,将A的最后一个盘子挪到C


    towersOfHnt(n-1,b,c,a);    //此步骤看成9到15步骤,调换顺序,重新挪动盘子。
    count++;
  }
}

var count = 0;
function calculate(){
  var a1 = {
    name : "柱子A",
    value : [1,2,3,4,5]
  }
  var b1 = {
    name : "柱子B",
    value : []
  }
  var c1 = {
    name : "柱子C",
    value : []
  }
  var n1 = 5;
  towersOfHnt(n1,a1,c1,b1);
  console.log("一共搬动了"+count+"次");
}
calculate();

 

运行上面的代码,按5个盘子来看下步骤与结果是否正确。

 

汉诺塔问题(递归篇)

无论是Tn= 2^n - 1还是Tn = 2Tn-1 +1都正确。 证明完毕,结束。

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/zyyppd.html