递归算法就是一个函数通过不断对自己的调用而求得最终结果的一种思维巧妙的算法.无论在哪种语言里,汉诺塔都是递归算法的经典题目.
1.题目简介
有三根相邻的柱子,左边的柱子上从下到上按金字塔状叠放着n个不同大小的圆盘,要把所有盘子一个一个移动到右边的柱子上,并且每次移动同一根柱子上都不能出现大的盘子在小的盘子上方.
2.逻辑分析
假设我们有一个方法move(n)已经实现n个盘子的移动,当我们想再实现n+1个盘子的移动时,该怎么做呢?
>>首先调用move(n),将n个盘子从左边移动到中间的柱子;
>>然后将第n+1个盘子从左边移动到右边的柱子;
>>最后调用move(n),将n个盘子从中间再移动到右边的柱子,即可完成.
按照上面三个步骤,我们可以一直向前推导,直到只有一个盘子时,我们将它移动到正确的位置即可.注意,我们在每次调用move(n)方法时用到的"柱子"的并不一样,因此move(n)方法还应该有两个参数:src柱子和dest柱子.
3.代码实现
public class Hanoi { static int count = 0; public void move(Column src, Column dest, int number) { count++; if (number > 1) { Column transit = Column.values()[3 - src.ordinal() - dest.ordinal()]; int frontnumber = number - 1; this.move(src, transit, frontnumber); System.out.println(number + "号盘子从\t " + src + "\t移动到\t" + dest); this.move(transit, dest, frontnumber); } else { System.out.println(1 + "号盘子从\t " + src + "\t移动到\t" + dest); } } public static void main(String[] args) { new Hanoi().move(Column.LEFT, Column.RIGHT, 3); System.out.println("操作已完成,一共操作了" + count + "次."); } } enum Column { LEFT, MIDDLE, RIGHT }
执行结果:
1号盘子从 LEFT 移动到 RIGHT
2号盘子从 LEFT 移动到 MIDDLE
1号盘子从 RIGHT 移动到 MIDDLE
3号盘子从 LEFT 移动到 RIGHT
1号盘子从 MIDDLE 移动到 LEFT
2号盘子从 MIDDLE 移动到 RIGHT
1号盘子从 LEFT 移动到 RIGHT
操作已完成,一共操作了7次.
相关推荐
递归算法的汉诺塔问题实现ppt,较详细得解释了递归算法的使用以及如何用递归算法来解决汉诺塔问题,QAQ
用C++实现汉诺塔的递归算法,定义了类和方法。
我用vc编了一个用栈实现汉诺塔的非递归程序。可以运行的,里面代码作了说明的!
c++递归实现汉诺塔问题。 算法分析与设计 例题的源码实现。跟书上的一样。
本文实例讲述了C++基于递归算法解决汉诺塔问题与树的遍历功能。分享给大家供大家参考,具体如下: 递归是把问题转化为规模缩小的同类问题,然后迭代调用函数(或过程)求得问题的解。递归函数就是直接或间接调用自身...
汉诺塔递归算法: 问题抽象 3个塔,n个碟子 初始:所有碟子放在1号塔,大的在底下,小的在上面 任务:把碟子移动到2号塔,顺序不变, 可用3号塔辅助 限制 每次只能移动一个碟子 总是大碟子...
用C语言实现汉诺塔的递归算法,另外还有用栈来实现的方式:http://download.csdn.net/detail/jason19905/6419427
汉诺塔问题的递归算法,附详细代码以及运行结果,有详细的算法描述。
汉诺塔的算法,递归算法有详细的c语言程序设计结构,内含递归算法
汉诺塔——经典的递归 *实现移动函数 *递归实现汉诺塔函数
非递归汉诺塔算法,并带有一片武汉大学的算法描述。
适应于大学生学习算法
汉诺塔非递归算法 用栈作为辅助存储结构 和数据结构中中序遍历二叉树的方法类似
用非递归算法,用栈解决问题,C#语言,来解决汉诺塔移动问题
用栈来实现汉诺塔,要明白递归就是栈的重要应用之一,递归是系统自动调用栈来处理。
此程序只是显示了C++中的递归函数的调用过程,即汉诺塔游戏的移动过程。
利用函数递归调用的方法,实现了汉诺塔问题
汉诺塔问题的非递归算法分析是一个有趣的算法分析。
利用C++编写汉诺塔的非递归算法以及其运行程序(算法中包含注释)。
递归应用,用于实现汉诺塔问题,源于经典故事! 主要在于递归调用!