Java汉诺塔问题

三根木桩：
思路：步骤1，将n-1个盘子，从木桩A移动到木桩B；
步骤2，将第n个最大的盘子，从木桩A移动到木桩C；
步骤三，将n-1个盘子，从木桩B移动到木桩C.

package Stack;
import java.io.*;
public class Hanoi {
	public static void main(String args[]) throws IOException {
		int j;
		String str;
		BufferedReader Keyin=new BufferedReader(new InputStreamReader(System.in));
		System.out.println("请输入盘子的数量：");
		str=Keyin.readLine();
		j=Integer.parseInt(str);
		hanoi(j,1,2,3);
		
	}
	public static void hanoi(int n,int p1,int p2,int p3) {
		if(n==1)
			System.out.println("盘子从"+p1+"移动到"+p3);
		else {
			hanoi(n-1,p1,p3,p2);
			System.out.println("盘子从"+p1+"移动到"+p3);
			hanoi(n-1,p2,p1,p3);
		}
		
	}
}

四根木桩：
首先我们可以先考虑A柱子上面只有三个盘子的情况，对于A柱子上的三个盘子，我们可以先将一个盘子从A柱子移动到B柱子上面，再将第二个盘子移动到C柱子上面，最后将剩下的一个盘子移动到D柱子上面。其实对于这个过程，我们可以将其看成：首先将A柱子上面的盘子分成了两部分，第一部分上面只有一个盘子，第二部分有两个盘子，我们要做的就是先将第一部分的盘子移动到B（C也可以）柱子上面，然后将剩下的盘子移动到D柱子上面，在将B柱子上面的盘子移动到D柱子上面。

思路：

1，对于A柱子上面有n个盘子的时候，我们可以先将盘子分成k和n-k两个部分

2，将A柱子上面的K个盘子使用Hanoi4方法将其借助C,D柱子移动到B柱子上面

3，将A柱子上面剩下的n-k个盘子使用Hanoi3方法将其借助C柱子移动到D柱子上面

4，将B柱子上面的K个盘子使用Hanoi4方法将其移动到D柱子上面

我们来分析一下算法的时间复杂度：

步骤二的时间复杂度我们记为T(K)，Hanoi3问题的时间复杂度为：2^(n-k)-1，所以整个的算法时间复杂度为，其中T(1)=1,

所以我们可以看到时间复杂度与划分的时候的K有关，在这里我们取k=n/2来编写程序：

package Stack;

import java.util.Scanner;
 
public class Hanoi2 {
	private static Scanner sc;
 
	public static void main(String args[])
	{
		System.out.println("请输入盘子的数量：");
		sc = new Scanner(System.in);
		int n=sc.nextInt();
		char a='A',b='B',c='C',d='D';
		Hanoi(a,b,c,d,n);
	}
	private static void Hanoi(char a, char b, char c, char d, int n) {
		if(n==1)
			{
			System.out.println("将盘子从"+a+"柱子移动到"+d+"柱子");
			return;
			}
			Hanoi(a,c,d,b,n/2);
			Hanoi3(a,b,c,d,n-n/2);
			Hanoi(b,c,a,d,n/2);			
	}
 
	private static void Hanoi3(char a, char b, char c, char d, int i) {
		if(i==1)
			System.out.println("将盘子从"+a+"柱子移动到"+d+"柱子");
		else{
			Hanoi3(a, b, d, c, i-1);
			System.out.println("将盘子从"+a+"柱子移动到"+d+"柱子");
			Hanoi3(c, a, b, d, i-1);
		}
	}
}