Chan Chen Coding...

Hanoi Tower 汉诺塔的简单分析 Java

 当然、这是一个经典的递归问题~
    想必来看这篇博文的同学对汉诺塔应该不会陌生了吧,

  写这篇博还是有初衷的:

  之前学数据结构的时候自己看书、也上网上查了很多资料,资料都比较散、而且描述的不是很清楚,对于当时刚刚

接触算法的我,要完全理解还是有一定难度。今天刚好有时间就整理了下思路、重写分析了一下之前的疑惑的地方、

没有透彻的地方便都豁然开朗了。所以迫不及待把我的想法记录下来,和大家分享。

  如果你也是和之前的我一样对hanoi tower没能完全消化,或者刚刚接触汉诺塔,那希望我的这种理解方式能给你些

许帮助,如果你觉得已经完全掌握的比较牢靠了,那也可以看看,有好的idea可以一起分享;毕竟交流讨论也是一种很好的

学习方式。

  好了,废话不多说,切入正题。

关于汉诺塔起源啊、传说啊神马的就不啰嗦了,我们直接切入正题:
问题描述:

  有一个梵塔,塔内有三个座A、B、C,A座上有诺干个盘子,盘子大小不等,大的在下,小的在上(如图)。

把这些个盘子从A座移到C座,中间可以借用B座但每次只能允许移动一个盘子,并且在移动过程中,3个座上的盘

子始终保持大盘在下,小盘在上。

描述简化:把A柱上的n个盘子移动到C柱,其中可以借用B柱。

  

  我们直接假设有n个盘子:

  先把盘子从小到大标记为1、2、3......n

  先看原问题三个柱子的状态:
状态0  A:按顺序堆放的n个盘子。B:空的。C:空的。

  目标是要把A上的n个盘子移动到C。因为必须大的在下小的在上,所以最终结果C盘上最下面的应该是标号为n的盘子,试想:

要取得A上的第n个盘子,就要把它上面的n-1个盘子拿开吧?拿开放在哪里呢?共有三个柱子:A显然不是、如果放在C上

了,那么最大的盘子就没地方放,问题还是没得到解决。所以选择B柱。当然,B上面也是按照大在下小在上的原则堆放的

(记住:先不要管具体如何移动,可以看成用一个函数完成移动,现在不用去考虑函数如何实现。这点很重要)。

  很明显:上一步完成后三个塔的状态:

状态1:   A:只有最大的一个盘子。B:有按规则堆放的n-1个盘子。C空的。

  上面的很好理解吧,好,其实到这里就已经完成一半了。(如果前面的没懂,请重看一遍。point:不要管如何移动!)

我们继续:

  这时候,可以直接把A上的最大盘移动到C盘,移动后的状态:

中间状态:  A:空的。B:n-1个盘子。C:有一个最大盘(第n个盘子)

  要注意的一点是:这时候的C柱其实可以看做是空的。因为剩下的所有盘子都比它小,它们中的任何一个都可以放在上面,也就是                    C柱上。

  所以现在三个柱子的状态:

中间状态:  A:空的。B:n-1个盘子。C:空的

  想一想,现在的问题和原问题有些相似之处了吧?。。如何更相似呢?。显然,只要吧B上的n-1个盘子移动到A,待解决的问题和原问题就相比就只是规模变小了

  现在考虑如何把B上的n-1个盘子移动到A上,其实移动方法和上文中的把n-1个盘从A移动到B是一样的,只是柱子的名称换了下而已。。(如果写成函数,只是参数调用顺序改变而已)。 

  假设你已经完成上一步了(同样的,不要考虑如何去移动,只要想着用一个函数实现就好),请看现在的状态:

状态2: A:有按顺序堆放的n-1个盘子。B:空的。C:按顺序堆放的第n盘子(可看为空柱)

就在刚才,我们完美的完成了一次递归。如果没看懂请从新看一遍,可以用笔画出三个状态、静下心来慢慢推理。

我一再强调的:当要把最大盘子上面的所有盘子移动到另一个空柱上时,不要关心具体如何移动,只用把它看做一个函数可以完成即可,不用关心函数的具体实现。如果你的思路纠结在这里,就很难继续深入了。

到这里,其实 基本思路已经理清了。状态2和状态0,除了规模变小 ,其它方面没有任何区别了。然后只要用相同的思维方式,就能往下深入。。。

 

好了,看看如何用算法实现吧:

定义函数Hanoi(a,b,c,n)表示把a上的n个盘子移动到c上,其中可以用到b。

定义函数move(m,n)表示把m上的盘子移动到n上

我们需要解决的问题正是  Hanoi (a,b,c,n)     //上文中的状态0

 

1、把A上的n-1个移动到B:    Hanoi (a,c,b,n-1);       // 操作结束为状态1

2、把A上的大盘子移动到C         move(a,c)    

3、把B上的n-1移动到A     Hanoi (b,c,a,n-1);  //操作结束位状态2(和状态1相比只是规模变小)

 

如果现在还不能理解、请回过头再看一遍、毕竟如果是初学者不是很容易就能理解的。可以用笔记下几个关键的状态,并且看看你有没有真正的投入去看,独立去思考了。

 


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Hanoi {

    
public static void main(String[] args) throws IOException{
        
int n;
        BufferedReader buf;
        buf 
= new BufferedReader(new InputStreamReader(System.in));
        
        System.out.println(
"Please input the number of disk ");
        n 
= Integer.parseInt(buf.readLine());
        
        Hanoi hanoi 
= new Hanoi();
        hanoi.move(n,
'A','B','C');
    }
    
    
public void move(int n, char a, char b, char c){
        
if(n == 1){
            System.out.println(
"Disk " + n + " From " + a + " To " + c);
        }
        
else{
            move(n
-1,a,c,b);
            System.out.println(
"Disk " + n + " From " + a + " To " + c);
            move(n
-1,b,a,c);
        }
    }
}

 

以上、如果有不对的地方、还希望您能指出。

我对递归的一点理解:

解决实际问题时、不能太去关心实现的细节(因为递归的过程恰恰是我们实现的方法)就像这个问题,如在第一步就过多的纠结于如何把n-1个盘子移动到B上、那么你的思路就很难继续深入。只要看做是用函数实现就好,如果你能看出不管怎么移动,其实本质都一样的时候,那么就能较快的得到结果了。就像这个案例,要注意到我们做的关键几步都只是移动的顺序有改变,其中的规则没有改变,如

如果用函数表示的话,就只是参数调用的顺序有所不同了。在递归的运用中、不用关心每一步的具体实现 ,只要看做用一个函数表示就好。分析问题的时候,最好画出自己的推理过程,得到有效的状态图。

思考问题讲求思路的连贯性、力求尽快进入状态,享受完全投入到一件事中的美妙感觉



-----------------------------------------------------
Silence, the way to avoid many problems;
Smile, the way to solve many problems;

posted on 2012-08-31 11:31 Chan Chen 阅读(1722) 评论(1)  编辑  收藏 所属分类: Algorithm

评论

# re: Hanoi Tower 汉诺塔的简单分析 Java[未登录] 2015-02-09 13:53 yan

3、把B上的n-1移动到A     Hanoi (b,c,a,n-1);  //操作结束位状态2(和状态1相比只是规模变小)

跟 这个move(n-1,b,a,c); 最后的code里的不一样呀!




  回复  更多评论   


只有注册用户登录后才能发表评论。


网站导航: