Tower of Hanoi problem

---

前言

给定一个数组arr,长度为N,arr中的值只有1,2,3三种
arr[i] == 1,代表汉诺塔问题中,从上往下第i个圆盘目前在左
arr[i] == 2,代表汉诺塔问题中,从上往下第i个圆盘目前在中
arr[i] == 3,代表汉诺塔问题中,从上往下第i个圆盘目前在右
那么arr整体就代表汉诺塔游戏过程中的一个状况
如果这个状况不是汉诺塔最优解运动过程中的状况,返回-1
如果这个状况是汉诺塔最优解运动过程中的状况,返回它是第几个状况

解题思路

7A state of the Layer Tower of Hanoi problem

The first state of the optimal solution
All plates are on the left

The second state is1Plate No. is on the right
The third state is2The plate is in the middle

i: 1~iThe disc needs to be moved
F: 1~iOn what disk is the disk of ,Possibly left-center-right.
t:The place to go may be left,中,右
other:除了from, toanother location

iThe layer of the disc doesn't make any sense at allother.上

如果index还在From上,Explain that the first big step is not over
第一步:1~i-1 从from到other
第二步:i从from到to
第三步:1~i-1从other到to

Break down each step with recursion
最后相加,get the first step

代码

	public static int kth(int[] arr) {
    
		int N = arr.length;
		return step(arr, N - 1, 1, 3, 2);
	}

	// 0...index这些圆盘,arr[0..index] index+1层塔
	// 在哪？from 去哪？to 另一个是啥？other
	// arr[0..index]这些状态,是index+1层汉诺塔问题的,最优解第几步
	public static int step(int[] arr, int index, int from, int to, int other) {
    
		if (index == -1) {
    
			return 0;
		}
		if (arr[index] == other) {
    
			return -1;
		}
		// arr[index] == from arr[index] == to;
		if (arr[index] == from) {
    
			return step(arr, index - 1, from, other, to);
		} else {
    
			int p1 = (1 << index) - 1;
			int p2 = 1;
			int p3 = step(arr, index - 1, other, to, from);
			if (p3 == -1) {
    
				return -1;
			}
			return p1 + p2 + p3;
		}
	}