快捷搜索:

用VB编写Hanoi塔问题动态演示程序

1 小序

在谋略机算法设计中,应用递归技巧每每使函数的定义和算法的描述简捷且易于理解。有些数据布局如二叉树等因为其本身固有的递归特点,分外得当用递归的形式来描述。还有一些问题,虽然其本身并没有显着的递归布局,但用递归技巧来求解使设计出的算法简洁、易懂。是以深入掌握递归技巧在算法设计历程中可以设计出加倍有效的算法[1]。

简单地说,递归便是用自己定义自己。应用递归措施构造算法的基础思路是:当求解规模为n的问题时,先将其分化成多少个规模较小的与原问题具有相同特性的子问题,并找出子问题与原问题之间的组合关系,着末根据详细问题构造出递归算法。

递归算法的履行历程分“递推”和“回归”两个阶段。在递推阶段,把较繁杂问题(如:规模为n)的求解推理至较原问题简单一些的问题(如规模为n-1)的求解;在回归阶段,把递推停止时所获得的解,逐级返回,依次获得稍繁杂问题的解,终极获得原问题的解[2]。

Hanoi塔问题是一个范例的得当于使用递归技巧获得简洁算法的例子。Hanoi塔问题源自约19世纪末在欧洲呈现的一种游戏,游戏中首先在一块铜板上放置三根柱子,在第一根柱子上自上而下、由小到大年夜顺序串着64个盘子。游戏的目标是着末将所有盘子从第一根柱子上移到第三根柱子上,移动历程中可以用第二根柱子过渡。游戏规定一次只能移动一个盘子,并且任何时候不容许大年夜盘放在小盘的上面。

现在就给出关于Hanoi塔问题的法度榜样,让其将Hanoi塔问题的履行历程动态演示出来,以赞助读者加深理解递归技巧。

2 算法设计

我们先使用递归技巧对该问题进行算法设计。我们将三根柱子分手标号为A、B、C,目标是要将n个盘子从A柱子移动到C柱子。该问题可以设计如下的递归算法:

第一步 将A柱子上n-1个盘子借助C柱子移动到B柱子上;

第二步 将A柱子上残剩的第n个盘子移动到C柱子上;

第三步 将B柱子上的n-1个盘子借助A柱子移动到C柱子上。

对付第一步和第三步,我们又可以使用类似的措施继承将其求解历程设计为一个规模为n-1的Hanoi塔递归算法。

您可能还会对下面的文章感兴趣: