12.递归汉诺塔

使用递归实现汉诺塔

public class Main {
	public static void move(char pos1,char pos2) {
		System.out.print(pos1+" => "+pos2+" ");
	}
	public static void han(int n,char pos1,char pos2,char pos3) {
		if(n == 1) {
			move(pos1,pos3);
			return ;
		}
		han(n-1,pos1,pos3,pos2);
		move(pos1,pos3);
		han(n-1,pos2,pos1,pos3);
	}
	public static void main(String[] args) {
		han(1,'A','B','C');
		System.out.println();
		han(2,'A','B','C');
		System.out.println();
		han(3,'A','B','C');
	}
}

求移动的次数

package test04;

public class Main {
	static int sum = 0;
	public static void move(char pos1,char pos2) {
		System.out.print(pos1+" => "+pos2+" ");
		sum++;
	}
	public static void han(int n,char pos1,char pos2,char pos3) {
		if(n == 1) {
			move(pos1,pos3);
			return ;
		}
		han(n-1,pos1,pos3,pos2);
		move(pos1,pos3);
		han(n-1,pos2,pos1,pos3);
	}
	
	public static void main(String[] args) {
		han(1,'A','B','C');
		System.out.println(sum);
		System.out.println();
		sum = 0;
		han(2,'A','B','C');
		System.out.println(sum);
		System.out.println();
		sum = 0;
		han(3,'A','B','C');
		System.out.println(sum);
		System.out.println();
	}
}

2的n次方减去1