汉诺塔算法——我们开始认识

  • 2017-09-11
  • 117
  • 0

汉诺塔”是一个著名的益智游戏,好像也是来自古罗马,简单说就是有3个珠子,第一个柱子上从大到小当着一些圆盘,最大的在最下面,最小的最上面,现在想把所有的圆盘都移动到第三根柱子上,规则是:
1.每次只能移动一个圆盘;
2.整个过程中不允许较大的圆盘放在娇小的圆盘上面。


示意图如下:


这是一个很经典的递归算法,一般大学计算机中算法课中也会提到

下面说下用js的写法

// js写法
var hanoi = function (disc, a, b ,c) {
  if (disc > 0) {
    hanoi(disc - 1, a, c, b);
    console.log('移动 盘子' + disc + '从' + a + '到' + c);
    hanoi(disc -1, b, a, c)
  }
}

hanoi(4, 'a', 'b', 'c');

输出:

"移动 盘子1从a到b"
"移动 盘子2从a到c"
"移动 盘子1从b到c"
"移动 盘子3从a到b"
"移动 盘子1从c到a"
"移动 盘子2从c到b"
"移动 盘子1从a到b"
"移动 盘子4从a到c"
"移动 盘子1从b到c"
"移动 盘子2从b到a"
"移动 盘子1从c到a"
"移动 盘子3从b到c"
"移动 盘子1从a到b"
"移动 盘子2从a到c"
"移动 盘子1从b到c"

总结
经典。

评论

还没有任何评论,你来说两句吧

- 友情链接 - Theme by Qzhai