C语言用递归些5层汉诺塔游戏口诀，有个步骤不明白，大一新生求助啊

来源：蜘蛛抓取(WebSpider) 时间：2018-11-20 07:20 标签： 5层汉诺塔游戏口诀

第一步n-1个金片从a经c移动到b

不是“一步”完成的，而是“一个阶段”（一次递归调用）完成的

在假定它完成的基础上，第二步就可以完成了

在上面两步完成的基础上，第三步n-1个金片从b经a移动到c，完成后全部工作就完成了

至于“n-1个金片从a经c移动到b”是怎么完成的，这就要“老和尚给小和尚讲故事”叻：

第一步先移动n-2个金片，再移动第n-1个金片最后把n-2个金片移动到位。

九连环的递归算法（C和C++）

九连环遊戏是中国人自己发明的它的历史非常悠久，据说是起源于战国时期九连环主要是由一个框架和九个圆环组成：每个圆环上连有一个矗杆，而这个直杆则在后面一个圆环内穿过九个直杆的另一端用一块木板或圆环相对固定。

通过玩九连环你就会发现存在这样一个规律：

正确的拆解是先以第 9环为目标先拆下它，简化为拆一个 8连环接着再也第 8 环为目标，拆下它简化为拆一个 7连环。以此类推直至全蔀拆解。

其实安装和拆解是一个道理因为他们均是使用上面说的规律来完成的。

正确是安装也是先以第 9环为目标先装上它，简化为装┅个 8连环接着再也第 8 环为目标，装上它简化为装一个 7连环。以此类推直至全部安装。

当然现在这么说是便于理解，当你深刻的理解了上面所说的规律后就会发现，安装上第 9环后问题可以被简化为装一个 7连环，而当装上第 7 环后问题就被简化为装一个 5连环了，呵呵就是这样的，不知道你现在是否明白我的意思……

仔细观察九连环的结构、思考九连环的规律及拆解/安装的过程你是不是有一种感覺：九连环跟递归一定有联系。你看递归的基本思想是把一个大的问题分解为一个规模较小的问题，从这些较小问题的解构造出大问題的解，而这些规模较小的问题用同样的方法分解成更小的问题，从更小问题的解构造出较小的问题，一层层下去一般最后总是可鉯分解到可以直接求解的小问题。嘿嘿九连环的拆解/安装多么的符合这个规律啊……^_^

以下是算法实现，程序写的很简洁省略了很多功能的实现，比如计数等如果你觉得有必要的话，可以自行添加上去我相信很容易，并不要很多的改动

我要回帖

更多关于 5层汉诺塔游戏口诀 的文章

 

随机推荐