汉诺塔问题:古代有一个梵塔塔内有3个基座,A基座上有64个盘子盘子大小不等,大的在下小的在上。有一个老和尚想把盘子由A座移到B座但每次只能移动一个盘子,3個基座上的盘子都始终保持大的在下小的在上。移动过程中可以利用C基座做辅助求解其移动过程。
汉诺塔问题是递归算法比较经典的唎题几乎是每个老师讲解递归算法时都会讲到的问题,对于任意n阶汉诺塔问题假设有3个基座A,B C。在基座A上放置有n个直径大小各不同从小到大依次编号为:1、2、3…n。移动时遵循以下规则:
如何实现将A上的盘子按规则移动到B盘上呢根据递归算法的思想:将一个大型复雜的问题层层转化为一个与原问题相似的规模较小的问题,在逐步求解小问题后再回溯得到大问题的解。我们将问题进一步分解当只囿一个盘子是,我们只需要将A基座上的盘子直接移动到B基座上即可当有两个盘子是,我们可以借助C基座完成移动过程具体移动步骤为:A->C(第1个盘子),A->B(第2个盘子),C->B(第1个盘子);把n个盘子抽象的看作“两个盘子”,“一个”由1~n-1号组成最底下是n号盘子,则移动过程为:
把n阶汉诺塔问题记作hanoi(int n, char a, char b, char c)
这里的A,BC并不总代表A、B、C三个底座,其意义为:第一个参数n代表基座上的盘子数a:代表每一次移动的起始基座,b:代表每一次移动的终点基座c:代表每一次移动的辅助基座。由上述约定以后的操作等价于:
格式:PPTX ? 页数:65页 ? 上传日期: 05:07:06 ? 浏览次数:1 ? ? 2500积分 ? ? 用稻壳阅读器打开
全文阅读已结束如果下载本文需要使用