【递归】汉诺塔问题

原创 老姚 随笔 递归,俺跟你拼了 1206阅读 2017-05-09 17:44:08 举报

递归公式很好用。其实有些问题虽然没有啥递归公式,但是它是递归定义的。
此时,也很容易把定义转化为代码。

本文以汉诺塔为例子,相信大家都很熟悉这个问题。

汉诺塔
具体地说,有三个柱子ABC,然后A柱子上有一些圆盘,比如说5个吧。
这5个圆盘,从上到下的排列方式是从小到大的,可以依次编号为1、2、3、4、5。
问题是要你把A柱子上的圆盘全部移动到C上面。
具体要求:
1.每次只能移动一个圆盘。
2.可以任意使用这三个柱子,但每个圆盘只能放在比它大的圆盘上。

其实这个问题解决办法,就是递归定义的,只是不那么明显,甚至还有点不可思议。
我们定义一个函数表示移动,move(n, from, to, by)。
比如move(5, 'A', 'C', 'B')表示A柱子有5个圆盘,通过B柱子,然后全部移动到C柱子上。

思路是什么呢?
我先想办法把前4个移动到B上,
然后把最大的那个移动从A移动到C上,
然后想办法再把B上那4个移动到C上。
“想办法”中的“办法”就是同样的思路,这个思路就是递归定义的。

因此用move表示就是:
move(5, 'A', 'C', 'B')等价于:
1.move(4, 'A', 'B', 'C')
2.把5从A直接移动C上
3.move(4, 'B', 'C', 'A')

翻译成代码就是
javascript 代码

另外甚至有人把汉诺塔做成了游戏,并且可视化演示解决过程(点击solve按钮):
html 代码

本文完。

《递归系列目录》

看到此处,我们该想到,陆游诗人对前端界做出的最大贡献:
纸上得来终觉浅,绝知此事要躬行。

评论 ( 1 )
最新评论