博客

    了解汉诺非递归算法前，先了解汉诺塔递归算法最好，这样可以了解汉诺塔的一些逻辑。代码如下：

package Text;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;

public class Demo {
	
	public String msg ="";
	
	
	public static void test(Demo demo){
		String msg = demo.getMsg();
		 msg = msg +"World";
		 System.out.println("11"+msg);
		 demo.setMsg(msg);
	}
	public static void main(String[] args){
		
		Demo demo =new Demo();
//		demo.setMsg("Hello") ;
//		test(demo);
//		System.out.println(demo.getMsg());
		Scanner sc =new Scanner(System.in);
		demo.getABC(sc.nextInt());
//		List list = new ArrayList();
//		list.add(1);
//		list.add(2);
//		list.add(3);
//		list.add(0, 4);
//		for(Object o : list){
//			System.out.println((Integer) o);
//			
//		}
//		list.remove(0);
//		
//		for(Object o : list){
//			System.out.println((Integer) o);
//			
//		}
//		System.out.println(list.get(0));

	}
	public String getMsg() {
		return msg;
	}
	public void setMsg(String msg) {
		this.msg = msg;
	}
	
	
	
	/**思路：规律：最开始有几个盘子就算几阶，阶层分奇偶，奇数阶层一种变化，偶数阶层一种变化。奇数层变化：oddOrder，偶数成变化：evenOrder，根据阶层数的奇偶，阶层的奇偶变化相互转换，关键是思维模型，
	 *     先知道第一次的移动过程，然后按顺序结合规律，%2得到阶数，该阶数的奇偶和规律中的奇偶相反（原因：移动的次数%2得到的阶数是从0开始的，规律中的阶数是从1开始的），先偶后奇，得到移动过程*/
	/**思维模型：以3阶为例,每层往下，一个过程下会多出两个过程，两个过程在上边的是由左边的第二位、第三位互换得来，在下边的是由左边的第二位和第一位互换得来。
	 *         ABC
	 *     ACB
	 *         CAB
	 * ABC
	 *         BCA
	 *     BAC
	 *         ABC
	 * */
	private void getABC(int num){
		
		List<Integer> aa = new ArrayList<Integer>();
		List<Integer> bb = new ArrayList<Integer>();
		List<Integer> cc = new ArrayList<Integer>();
		
		Double d = Math.pow(2, num);
		for(int ii =1; ii <= num; ii++){
			aa.add(ii);
		}
		String[][] oddOrder = new String[3][3];//阶层为奇数的字母的规则
		String[][] evenOrder = new String[3][3];//阶层为偶数的字母的规则
		Map<Integer, Integer> orderMap = new HashMap<Integer, Integer>();
		if(num % 2 == 0){
			numToNum(aa, bb, cc, "A", "B");
			oddOrder = new String[][]{{"A","B","C"},{"C","A","B"},{"B","C","A"}};
			evenOrder = new String[][]{{"A","C","B"},{"B","A","C"},{"C","B","A"}};
			
		}else{
			numToNum(aa, bb, cc, "A", "C");
			oddOrder = new String[][]{{"A","C","B"},{"B","A","C"},{"C","B","A"}};
			evenOrder = new String[][]{{"A","B","C"},{"C","A","B"},{"B","C","A"}};
		}
		      
		orderMap.put(0,0);
		
		for(int i = 2; i <= d - 1 ; i++){
			int order = 0;
			int ii = i;
			while(ii != 0 && ii%2 == 0){
				ii = ii/2;
				order++;
			}
			
			if(orderMap.get(order) == null){
				
				orderMap.put(order, 0);
				
			}else{
				
				orderMap.put(order, orderMap.get(order) == 2 ? 0 : orderMap.get(order) + 1);
				
			}
			
			if(order%2 != 0){
				numToNum(aa, bb, cc, evenOrder[0][orderMap.get(order)], evenOrder[2][orderMap.get(order)]);
			}else{
				numToNum(aa, bb, cc, oddOrder[0][orderMap.get(order)], oddOrder[2][orderMap.get(order)]);
			}
			
		}
		
	}
	
	private void numToNum(List<Integer> a ,List<Integer> b, List<Integer> c,String num1, String num2){
		System.out.print(num1 + "-->" +num2);
		int n = 0;
		if("A".equals(num1)){
			n = a.get(0);
			delNum(a);
			if("B".equals(num2)){
				addNum(b,n);
			}else{
				addNum(c,n);
			}
			
		}else if("B".equals(num1)){
			n = b.get(0);
			delNum(b);
			if("C".equals(num2)){
				addNum(c,n);
			}else{
				addNum(a,n);
			}
		}else{
			n = c.get(0);
			delNum(c);
			if("A".equals(num2)){
				addNum(a,n);
			}else{
				addNum(b,n);
			}
		}
		System.out.print(" n = "+n + " ");
	}
	
	private void addNum(List<Integer> num, int a){
		num.add(0, a);
	}
	private void delNum(List<Integer> num){
		num.remove(0);
	}

}