高级汉诺塔问题分析

李恒道

题目如下

给定一个数组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的