【Fiay】【Java】汉诺塔算法 递归实现

 

/**
 * 汉诺塔问题
 * 
 * 精确计算出到底需要移动多少次才能够将汉诺塔从柱子A搬到柱子B（柱子C作缓冲）
 * 输入：汉诺塔的层次数
 * 输出：移动次数和移动动作
 * 思路：递归
 * 使用：直接在main函数new Test(汉诺塔的层次数)
 * 
 * @author Fiay
 * 
 */
public class Test {
	private static String a = "柱子A";
	private static String b = "柱子B";
	private static String c = "柱子C";
	private int level;
	private int turns;
	/*省略Getter and Setter*/
	public Test(){}
	public Test(int level){
		this.level = level;
		this.turns = getTurnsByLevel(this.level);
		System.out.println("完成！\n共需要"+turns+"步");
	}
	
	public int getTurnsByLevel(int level){
		System.out.println("汉诺塔层次数为："+level+"\n开始！");
		showSolution(level,a,b,c);
		return turns-1;
	}
	
	public void showSolution(int level,String a,String b,String c){
		if(level>0){
			showSolution(level-1,a,c,b);
			System.out.println(turns+" - 从（"+a+"）移到（"+b+"）\t");
			showSolution(level-1,c,b,a);
		}else{
			turns++;
		}
	}
	
	public static void main(String args[]){
		new Test(2);
		//new Test(3);
		//new Test(4);
	}
}

评论

1 楼 fiay1991 2012-12-02  

汉诺塔次数计算公式，设层次数为x，操作次数为F(x),当层次为0时，操作次数为0，则有：
     
      F(0) = 0;

      F(1) = 2 * F(1-1) + 1 = 1;

      F(2) = 2 * F(2-1) + 1 = 2 * F(1) + 1 = 3;

      F(3) = 2 * F(3-1) + 1 = 2 * F(2) + 1 = 7;

      F(4) = 2 * F(4-1) + 1 = 2 * F(3) + 1 = 15;

      依此类推，可得： F(x) = 2 * F(x-1) + 1;

      又从1 3 7 15可看出，

      1 = 2^1 - 1;
     
      3 = 2^2 - 1;

      7 = 2^3 - 1;

      15 = 2^4 - 1;

      依此类推，可得：F(x) = 2^x - 1;