论坛 › 其它 › 高级汉诺塔问题分析

李恒道 发表于 2024-10-27 18:50:45

高级汉诺塔问题分析

题目如下
```
给定一个数组arr，长度为N，arr中的值只有1，2，3三种
arr==1，代表汉诺塔问题中，从上往下第i个圆盘目前在左
arr==2，代表汉诺塔问题中，从上往下第i个圆盘目前在中
arr ==3，代表汉诺塔问题中，从上往下第i个圆盘目前在右
那么arr整体就代表汉诺塔游戏过程中的一个状况
如果这个状况不是汉诺塔最优解运动过程中的状况，返回-1
如果这个状况是汉诺塔最优解运动过程中的状况，返回它是第几个状况
```
假设有7层汉诺塔
我们的函数参数设置为
`step(arr,index,from,to,other)`
其中arr是汉诺塔每层状态所在位置，index是该层序号，from是哪里来，to是去哪里，other为其他部分
其中当index为-1的时候最优解应为0；
而arr==other部分理解较为复杂
当7层汉诺塔，第7层应该由最左到最右
如果出现在other则为中间，这是不可能的
而假设7层在arr的状态还在左
则上层的6层一定在左到中的步骤中
不可能出现在other最右上

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

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

所以可以判断`arr==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 发表于 2024-10-27 21:18:19

Js\Go\Java 全部修是吧

wuxin0011 发表于 2024-10-27 21:18:33

Js\Go\Java 全部修是吧

wuxin0011 发表于 2024-10-27 21:19:06

好像卡了 哈哈哈哈哈

李恒道 发表于 2024-10-27 22:00:44

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

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

wuxin0011 发表于 2024-10-29 19:07:54

打卡今日的每日一题，这题可以回溯，但是这样没意思
```java
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;
      for(int i = 0;i < n;i++) {
            sk = (x >> i & 1) == 1 ? '1' : '0';
      }
      return new String(sk);
    }
}
```

查看完整版本: 高级汉诺塔问题分析