汉诺塔进阶问题

作者：Grey

原文地址：

博客园：汉诺塔进阶问题

CSDN：汉诺塔进阶问题

题目描述

牛客-汉诺塔II

有一个int数组arr其中只含有1、2和3，分别代表所有圆盘目前的状态，1代表左柱，2代表中柱，3代表右柱，arr[i]的值代表第i+1个圆盘的位置。比如，arr=[3,3,2,1]，代表第1个圆盘在右柱上、第2个圆盘在右柱上、第3个圆盘在中柱上、第4个圆盘在左柱上。如果arr代表的状态是最优移动轨迹过程中出现的状态，返回arr这种状态是最优移动轨迹中的第几个状态。如果arr代表的状态不是最优移动轨迹过程中出现的状态，则返回-1。给定一个int数组arr及数组的大小n，含义如题所述，请返回一个int，代表所求的结果。

思路

对于三层汉诺塔问题，流程是：

第一大步：0-N-1号圆盘从from位置到other位置，给第N号圆盘腾出位置

第二大步：N号圆盘从from位置到to位置

第三大步：0-N-1号圆盘从other位置到to位置

所以：

N位置没有必要去other位置！所以，如果arr[N] = other 直接返回-1

定义递归函数：

int f(arr, N, from, to, other) 

其中

N表示0...N个圆盘

from表示从哪个位置

to表示到哪个位置

other表示其他位置

f函数的返回值表示这个是最优解的第几步

比如：f(arr, 8,1,3,2)表示

9个圆盘从左边移动到右边，是最优解的第几步

所以：

如果某一步 arr[i] = other 直接返回-1

如果arr[i] = from 说明 第一大步没走完，

调用 f(arr, i-1, from ,other, to)即可得到这是第几步。

如果arr[i] = to 说明在第三大步，

因为N层汉诺塔问题的步数是2^N - 1

第一大步走了 2^(i-1) - 1

第二大步走了1步

所以：

第一大步和第二大步一共走了 ：2^(i-1)

剩下第三大步走了 2^(i-1) + f(arr, i-1, other, to, from)

完整代码

// O(N)
public static int chkStep(int[] arr, int N) {
    return f(arr, N - 1, 1, 3, 2);
}
public static int f(int[] arr, int N, int from, int to, int other) {
    if (N == -1) {
        return 0;
    }
    if (arr[N] == other) {
        return -1;
    }
    if (arr[N] == from) {
        return f(arr, N - 1, from, other, to);
    } else {
        int rest = f(arr, N - 1, other, to, from);
        if (rest == -1) {
            return -1;
        }
        return (1 << N) + rest;
    }
}

更多

算法和数据结构笔记