题目如下
给定一个数组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的步数
于是得出了完整代码