汉诺塔有关问题分析

上图为汉诺塔的三根柱子。

现在假设，Tn为n个盘子从A移动到C的最小移动次数，那么有

T0 = 0

T1 = 1

T2 = 3( 小盘A->B，大盘A->C，小盘B->C )

当有3个盘子的时候，我们可以采用2个盘子的思想，即：

将上面（3-1）个盘子看做小盘，将最下面的盘子看做大盘，这样的话，由于小盘移动了两次(A->B，B->C)，而大盘只移动了一次，所以可得：

T3 = 2T2 + 1

所以可得Tn的一般式：

Tn = 2Tn-1 + 1( n > 0 )，

整理可得这样的式子：

T0 = 0( n = 0 )

Tn = 2Tn-1 + 1( n > 0 )

这样的话，我们可以得到：

T0 = 0

T1 = 2T0 + 1 = 2 * 0 + 1 = 1

T2 = 2T1 + 1 = 2 * 1 + 1 = 3

T3 = 2T2 + 1 = 2 * 3 + 1 = 7

通过观察可得Tn = 2^n – 1(2^n为2的n次幂)( n>= 0)

运用数学归纳法，可证该式成立。

(以上参考具体数学—计算机科学基础一书)

/*
 *汉诺塔：递归求解
 *以下方法参考了：C语言程序设计教程(第二版)
*/

import java.util.Scanner ;

public class Hanoi_1{
	public static int plate = 0 ;

	public static void main( String args [] ){
		System.out.println( "********************************" ) ;
		Scanner reader = new Scanner( System.in ) ;
		System.out.println( "输入盘子的个数:" ) ;
		plate = reader.nextInt() ;
		System.out.println( "********************************" ) ;

		hanoi( plate, 'A', 'B', 'C' ) ;
	}

	public static void hanoi( int n ,char a, char b, char c ){
		/*
		 *n:盘子的个数
		 *a:源柱子
		 *b:临时柱子
		 *c:目标柱子
		*/

		if( n == 1 )
			move( n, c ) ;
		else{
			hanoi( n - 1, a, c, b ) ;  //将n-1个盘子从A->B,以c为临时柱子
			move( n, c) ;              //将最大盘从A->C,
			hanoi( n - 1, b, a, c) ;   //将n-1个盘子从B->C,以A为临时柱子
		}
	}

	public static void move( int x, char y ){
		System.out.printf("%d -----> %c\n", x, y) ;
		//左边显示的是盘号，盘号越小，盘子越小
		//右边是目标柱子
	}
}

 
<!--[endif]-->