首页 > 试题广场 >

61-递归和动态规划-汉诺塔II

[编程题]61-递归和动态规划-汉诺塔II
  • 热度指数:2314 时间限制:C/C++ 3秒,其他语言6秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解

有一个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,代表所求的结果。

测试样例:
[3,3]
返回:3
头像 重生之我要当分子
发表于 2024-12-31 21:38:28
解题思路 为了找到给定状态在汉诺塔最优移动轨迹中的序号,我们可以使用以下步骤: 状态有效性检查: 确保每个圆盘的位置只在左柱(1)和右柱(3)之间,且不在中柱(2)上。 计算序号: 从最后一个圆盘开始,向前遍历每个圆盘。 根据当前圆盘的位置更新状态,并计算在最优移动轨迹中的序号。 展开全文

问题信息

难度:
18条回答 15301浏览

热门推荐

通过挑战的用户

查看代码
61-递归和动态规划-汉诺塔II