作为一个Java初学者,看韩顺平老师的递归那一段,提到了汉诺塔的问题,但是大家普遍感到困惑,尤其是韩老师讲到的“借助”这个词,让不少同学感到无法理解。
实际上,借助在三行移动的代码里已经体现了,只是这个词让人以为要额外做些什么。下面我结合自己对代码的运行分析,记录一下自己的理解和体会。
public class Main {public static void main(String[] args) {Tower t = new Tower();t.move(4, 'a', 'b', 'c');}}class Tower {/*move方法的含义a为起始柱,c为目标柱,b为第三柱*/void move (int plateNum, char a, char b, char c) {if (plateNum == 1) {System.out.println(a + "->" + c);} else {move (plateNum -1, a, c, b);System.out.println(a + "->" + c);move (plateNum -1, b, a, c);}}}
上面的代码,是韩顺平老师的原始代码。起初我也看得很懵,为了更好地观察,我想到加入一些输出语句,以观察递归的调用情况。
public class Main {public static void main(String[] args) {Tower t = new Tower();t.move(4, 'a', 'b', 'c');}}class Tower {/*move方法的含义a为起始柱,c为目标柱,b为第三柱*/void move (int plateNum, char a, char b, char c) {if (plateNum == 1) {System.out.println(a + "->" + c);} else {System.out.println("==move" + (plateNum -1)+ "个从"+ a +"到"+ b +":");move (plateNum -1, a, c, b);System.out.println((plateNum -1)+ "个从"+ a +"到"+ b +"完成:==");System.out.println();System.out.println(a + "->" + c);System.out.println();System.out.println("==move" + (plateNum -1)+ "个从"+ b +"到"+ c +":");move (plateNum -1, b, a, c);System.out.println((plateNum -1)+ "个从"+ b +"到"+ c +"完成:==");System.out.println();}}}
大家可以看到,我在move方法上面有一小段注释:
/*move方法的含义
a为起始柱,c为目标柱,b为第三柱
*/
这段话的意思,我觉得很关键,至少对我本人来说是这样。因为汉诺塔的问题,一开始就定下了说要把所有的圆盘从a移动到c。所以一开始可能就觉得,a和c有什么特殊之处,而b又被看作被"借助"的一根柱子,其实不用这么看。这个问题的意思无非就是把一个东西从一个地方移动到另一个地方。有起点有终点,至于起点是a/b还是c,根本不重要。所以move这个函数就是说,输入圆盘数,三根柱子,圆盘现在在其中一根柱子上,现在要全部移动到另一根柱子上,就完了。理解这一点很重要,因为move递归的过程中,本质就是大目标move反推出中目标move、小目标move,大目标分割成很多个中目标,中目标分割成很多个小目标,移动圆盘的过程中,对不同的目标move来说,起点和终点都是不一样的,所以abc完全是平等的。但是,在实现move方法的过程中,我们是人为在规定哪个形参代表什么柱子(起点终点)的。这样调用的时候才知道如何传参。我们规定说,a代表我们想要移动的圆盘当前的位置,c代表它的目标位置,b是第三根。
其实,也完全可以这么写:
void move (int plateNum, char start, char third, char dest) {if (plateNum == 1) {System.out.println(start + "->" + dest);} else {move (plateNum -1, start, dest, third);System.out.println(start + "->" + dest);move (plateNum -1, third, start, dest);}}
start 是当前所在柱,dest是目标柱,third是另一根柱子。
好了,参数就解释到这里。下面看上面的代码输出情况:
{==move3个从a到b:[==move2个从a到c:(==move1个从a到b:a->b1个从a到b完成:==)a->c(==move1个从b到c:b->c1个从b到c完成:==)2个从a到c完成:==]a->b[==move2个从c到b:(==move1个从c到a:c->a1个从c到a完成:==)c->b(==move1个从a到b:a->b1个从a到b完成:==)2个从c到b完成:==]3个从a到b完成:==}a->c{==move3个从b到c:==move2个从b到a:==move1个从b到c:b->c1个从b到c完成:==b->a==move1个从c到a:c->a1个从c到a完成:==2个从b到a完成:==b->c==move2个从a到c:==move1个从a到b:a->b1个从a到b完成:==a->c==move1个从b到c:b->c1个从b到c完成:==2个从a到c完成:==3个从b到c完成:==}
为了方便表示结构,我在前一半段中,将目标 手动用加了括号括起来,大目标用“{}”,中目标用"[]",小目标用“()”。
大家可以看到 整个move四个圆盘的总目标,被分成了两个【移动3个圆盘的大目标】(外加一个移动最底下圆盘的目标),然后移动3个圆盘的目标,又被分成了两个【移动2个圆盘的中目标】,移动2个圆盘的目标又被分成了两个【移动1个圆盘的中目标】。
其实这就是递归最直接的体现。为什么简单四行代码就解决了所有问题,因为圆盘数再多,也都是这几行代码叠加出来的。所以实现这个递归,只要实现一个圆盘的移动和两个圆盘的移动就可以了。所以,起初,我们的代码应该是这样的:
void move (int plateNum, char a, char b, char c) {if (plateNum == 1) {System.out.println(a + "->" + c);} else if(plateNum == 2){System.out.println(a + "->" + b);System.out.println(a + "->" + c);System.out.println(b + "->" + c);}}
但是为了实现递归,我们需要将移动2个圆盘的操作进行 “范化”,其它可以用于其它任何数字的圆盘。所以,把plateNum == 2直接去掉,其它的也都用move函数来“范化”,就实现了递归。
void move (int plateNum, char a, char b, char c) {if (plateNum == 1) {System.out.println(a + "->" + c);} else {move (plateNum -1, a, c, b);System.out.println(a + "->" + c);move (plateNum -1, b, a, c);}}
最后,再回到一开始提到的那个问题,“借助”b是如何借助的,就是这三行带来的结果,只是范化后就容易看出来了。
System.out.println(a + "->" + b);System.out.println(a + "->" + c);System.out.println(b + "->" + c);