汉诺塔问题

---

前言

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

解题思路

7层汉诺塔问题的一个状态

最优解的第一个状态
全部盘子都在左边

第二个状态就是1号盘子在右边
第三个状态就是2号盘子在中间

i: 1~i的圆盘需要移动
F: 1~i的圆盘现在处在什么圆盘上，可能是左中右.
t:需要去的位置可能是左，中,右
other:除了from, to的另外一个位置

i层的圆盘没有任何道理是在other.上

如果index还在From上,说明第一大步没走完
第一步:1~i-1 从from到other
第二步:i从from到to
第三步:1~i-1从other到to

把每一步都用递归分解
最后相加,得出为第几步

代码

	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;
		}
	}