文章目录
前言
解题思路
代码
前言
给定一个数组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;
}
}
