汉诺塔相信大家都听过,而且也知道用递归来求解。
今天面试,突然问到这个,并要求写出代码,至少是伪代码。
一下子比较晕。仔细想了下,差点把汉诺塔搞错了。一下来自百科
“汉诺塔:汉诺塔(又称河内塔)问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘。”
现在,我们考虑如何使用递归。递归有个特点,那就是,上层把问题交给下层,直到最后可以很快求解时,再递归返回上层,得到答案。这个问题,可以这么理解:
问: n 个圆盘如何移动?
答: 如果知道n-1个圆盘移动顺序,那么我就知道如何移动n个圆盘了
问: n-1个圆盘如何移动?
答: 如果知道 n-2 个圆盘移动顺序,那么我就知道如何移动n个圆盘了。
...
...
...
问: 2个圆盘如何移动?
答: 这个容易,A->C, A->B, B->C
这时,3个圆盘可以移动了,然后4个圆盘也知道移动了,5个……
看代码吧。
public class Hanno {
/**
*
* @param A 起始柱子
* @param B 临时柱子
* @param C 目的柱子
* @param n 未放好的圆盘数量。如果未放好的最大的一个圆盘放到C中最下面,则表示这个圆盘已经放好。
*/
public void move(char A , char B , char C ,int n){
/**
* 小于2个圆盘,无意义。
*/
if(n < 2){
return;
}
/**
* 当圆盘数是2时,我们已经可以轻松的计算出移动顺序了。
*/
if(n == 2){
System.out.println("move from "+A +" to " + B + " ");
System.out.println("move from "+A +" to " + C + " ");
System.out.println("move from "+B +" to " + C + " ");
return;
}
/**
* 这里调整了一下,假设现在未放好的圆盘都在柱子A上。我们把目前圆盘看成两个,最下面的一个和
* 上面的所以看成一个。如何移动最上面的圆盘(被看做一个圆盘)我们不关心(通过递归求解,当最上面的圆盘数为2
* 时,我们可以递归)。我们的目的是把最上面的一个放到B,然后就可以把最下面一个放到C
* 这样就完成了最下面一个的放置。根据函数,我们可以如下表示。
*/
move(A,C,B,n-1);
/**
* 把上面的一摞(或者一个,看做一个)圆盘移动到B以后,我们把A中最后一个圆盘移动到C
* 所以直接移动。
*/
System.out.println("move from " + A + " to " + C );
/**
* 这时的情况是A柱子空了,B柱子变成n-1个圆盘,C柱子上是放好的圆盘了。
* 那么,我们继续移动,把B柱子上的圆盘,移动到C柱子,这里其实等于一开始时,把A和B换一下。
* 对于C柱子,最大的一个圆盘在下面了,所以无论什么圆盘,都可以放上面。可以看成是空的。
* 这样问题转换成求解n-1个圆盘。知道递归到不动点。
*/
move(B,A,C,n-1);
}
public static void main(String args[]){
Hanno hanno = new Hanno();
hanno.move('A', 'B', 'C', 3);
}
这里一个关键是,把柱子上的圆盘看成是两个,有些步骤,不用考虑如何移动,只需要递归到可以求解。
我一开始,也想到了,但是我还是想错了,不能把圆盘分成上面一个单独作为一个,下面的所有看做一个,这样是不行的。只有把下面的看成一个,然后上面的所有看成一个。
并且,移动的时候,按照简单的两个移动的思维,就组成了函数的逻辑。
- 大小: 8.9 KB
分享到:
相关推荐
---汉诺塔源代码--- ---汉诺塔源代码--- ---汉诺塔源代码--- ---汉诺塔源代码--- ---汉诺塔源代码---
算法分析设计中三柱汉诺塔算法的拓展,四柱汉诺塔的设计算法代码
汉诺塔(又称河内塔)问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上安大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另...
简单汉诺塔游戏
这是一个关于汉诺塔的flash小游戏,适合做各种设计
汉诺塔是传统的智力游戏,与华容道、魔方等类似。这是汉诺塔游戏的Python源代码,使用了基本的递归方式实现汉诺塔求解问题。 欢迎大家下载。
双色汉诺塔是由之前所介绍过的汉诺塔规则衍生而来。 盘子的颜色有两种
这是一个关于汉诺塔的flash小游戏,适合做各种设计
汉诺塔问题来自一个古老的传说:在世界刚被创建的时候有一座钻石宝塔(塔A).其上有64个金碟。所有碟子按从大到小的次序从塔底堆放至塔顶。紧挨着这座塔有另外两个钻石宝塔(塔B和塔C)。从世界创始之日起,婆罗门的...
汉诺塔模拟程序汉诺塔模拟程序汉诺塔模拟程序汉诺塔模拟程序
汉诺塔java源码汉诺塔java源码汉诺塔java源码汉诺塔java源码汉诺塔java源码汉诺塔java源码汉诺塔java源码
实验报告书 课程名: 数据结构 题 目: 汉诺塔 班 级: 学 号: 姓 名: 一、目的与要求 1)掌握栈与队列的数据类型描述及特点; 2)熟练掌握栈的顺序和链式存储存表示与基本算法的实现; 3)掌握队列的链式存储表示...
汉诺塔 演示程序 二叉树 演示动画 实现动态的观看到汉诺塔的盘子移动过程,动态的观看到树的遍历过程,树的查找过程
汉诺塔Hannoi(java)源程序 包含汉诺塔6个类
汉诺塔演示程序汉诺塔演示程序汉诺塔演示程序汉诺塔演示程序汉诺塔演示程序汉诺塔演示程序汉诺塔演示程序汉诺塔演示程序汉诺塔演示程序汉诺塔演示程序
datastruct.c :汉诺塔结构与可进行的操作的实现方法<由datastruct.h导出>; 方案2:图形界面 graphics.h :汉诺塔实体模拟-结构形式及可对塔进行的操作的接口>; graphics.c :汉诺塔实体模拟-结构形式及可对塔...
汉诺塔问题汉诺塔问题汉诺塔问题汉诺塔问题汉诺塔问题汉诺塔问题
汉诺塔C语言源代码汉诺塔C语言源代码汉诺塔C语言源代码汉诺塔C语言源代码汉诺塔C语言源代码汉诺塔C语言源代码汉诺塔C语言源代码
汉诺塔课程设计报告与源码