高级汉诺塔问题分析

李恒道

题目如下

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

假设有7层汉诺塔
我们的函数参数设置为
step(arr,index,from,to,other)
其中arr是汉诺塔每层状态所在位置，index是该层序号，from是哪里来，to是去哪里，other为其他部分
其中当index为-1的时候最优解应为0；
而arr[index]==other部分理解较为复杂
当7层汉诺塔，第7层应该由最左到最右
如果出现在other则为中间，这是不可能的
而假设7层在arr的状态还在左
则上层的6层一定在左到中的步骤中
不可能出现在other最右上

而如果7层已经在最右了
则其他层一定在中间，到最右的过程中
此时不可能出现在最左

每层的最优解都是确定且唯一的
当下层的状态确定，一定会框住上一层的所处位置

所以可以判断arr[index]==other一定为-1

如果在from上
则说明上层还没有搬完
应该走入step(arr,index-1,from,other,to)l分支
如果到了to上
说明已经走完了
应该将other上的搬到to上
则是step(arr,index-1,other,to,from)
并加上2的n次方-1+1，该公式为n-1层从from搬到other的步数

于是得出了完整代码

wuxin0011

Js\Go\Java 全部修是吧

wuxin0011

Js\Go\Java 全部修是吧

wuxin0011

好像卡了 哈哈哈哈哈

李恒道

wuxin0011 发表于 2024-10-27 21:18
Js\Go\Java 全部修是吧

没办法的，看好像大家题解写算法都是java
hhh
我js写得多，拿js写更顺
看别人题解就只能看jvav的

wuxin0011

打卡今日的每日一题，这题可以回溯，但是这样没意思

class Solution {
    public List<String> validStrings(int n) {
        List<String> ans = new ArrayList<>();
        int mask = (1 << n) - 1;
        for(int i = 0;i < (1 << n);i++) {
            int x = (~i) & mask;
            int y = x >> 1;
            if((x & y)  == 0) {
                ans.add(buildString(n,i));
            }
        }
        return ans;
    }

    public static String buildString(int n,int x) {
        char[] sk = new char[n];
        for(int i = 0;i < n;i++) {
            sk[n - i - 1] = (x >> i & 1) == 1 ? '1' : '0';
        }
        return new String(sk);
    }
}