汉诺塔问题

因为自己基础比较差，所以想在工作之余自己再学学，巩固一下，磨刀不误砍柴工嘛。今天看到了汉诺塔（Hanoi）问题，就记录了下来。

首先，大家都知道Hanoi问题是利用递归来解决的，那么什么是递归呢？

递归就是将规模为n的问题，降解成若干个规模为n-1的问题，依次降解，直到问题规模可求，求出低阶规模的解，代入高阶问题中，直至求出规模为n的问题的解。递归包括回溯和递推两个过程。

递归方式写出的方法往往十分简介，但是也有不少缺点：递归算法的运行效率比较低。在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。

 

我们假设有三根杆子from、middle、to。

首先，考虑from杆上只有一个盘子(这样是递归的终止条件)，任务变成：

   *将from杆上的唯一一个盘子移到to杆上；

然后，考虑from杆最下面的一个盘子而非上面的一些盘子，于是任务变成了：

   *将上面的n-1个盘子移到middle杆上；
   *将from杆上剩下的盘子移到to杆上；
   *将middle杆上的全部盘子移到to杆上。

将这个过程继续下去，就是要先完成移动n-1个盘子、n-2个盘子、n-3个盘子....的工作。

用程序来表示：我们定义一个函数move(n,from,middle,to)。该函数的功能是将N个盘子从from杆上借助middle杆移动到to杆上。这样移动n个盘子的工作就可以按照以下过程进行：

      1) move(n-1,from,to,middle);
      2) 将一个盘子从from移动到to上；

      3) move(n-1,middle,from,to)；
重复以上过程，直到将全部的盘子移动到位时为止。看看java源码：

 

public class Hanoi {    
	public static void main(String args[]) throws IOException {        
		int n;        
		BufferedReader buf;       
		buf = new BufferedReader(new InputStreamReader(System.in));        
		System.out.print("请输入盘数：");        
		n = Integer.parseInt(buf.readLine());        
		Hanoi hanoi = new Hanoi();        
		hanoi.move(n, 'A', 'B', 'C');    
	}    
	public void move(int n, char from, char middle, char to) {        
		if(n == 1)            
			System.out.println("盘 " + n + " 由 " + from + " 移至 " + to);    //1      
		else {            
			move(n - 1, from, to, middle);                                                  //2
			System.out.println("盘 " + n + " 由 " + from + " 移至 " + to);    //3        
			move(n - 1, middle, from, to);        						//4
		}    
	}
} 

在上面的代码中，解决问题的就是move方法，它使用了递归实现。其流程似乎很好理解。假设n=3，那么以上程序打印出来的就是：

 

请输入盘数：3

盘 1 由 A 移至 C

盘 2 由 A 移至 B

盘 1 由 C 移至 B

盘 3 由 A 移至 C

盘 1 由 B 移至 A

盘 2 由 B 移至 C

盘 1 由 A 移至 C

可是我想了半天，在自己的脑海里也模拟程序的运行，然后用笔写下运行的结果，却不知道怎么样才能得到以上的结果，看来还是没有彻底的理解递归的过程，Go on。

使用Eclipse的debug+单步执行 后发现在代码else块中实际执行顺序是：2-3-4-3-4-2-3-4。

 

 

 

 

评论

1 楼 qinglangee 2010-01-30  

窦娥冤，窦娥