递归与动态规划II-汉诺塔
2024-10-12 17:59:04
题目描述
有一个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 解决思路:首先求出所有的状态,然后在这个状态集合中遍历一遍找到arr相等的情况。
step1: 如果只有一个汉诺塔,那么直接从左边移动到右边。
step2: 如果有2个汉诺塔,那么首先把上面的移动到中间,然后下面的移动到右边,最后再把中间的移动到右边。
step3: 如果有n个汉诺塔,那么可以按照step2的思路,先将上面的n-1个移动到中间,然后最下面的移动到右边,最后将中间的n-1个移动到右边。
代码实现如下:
class Hanoi:
def chkStep(self, arr, n):
# write code here
self.initStatus = [1]*n
self.allStatus = [[1]*n]
self.move(n,1,2,3)
i = 0
for s in self.allStatus:
if s == arr:
return i
i = i+1
return -1
def move(self, n, left, mid, right):
if n <= 0:
return
self.move(n-1, left, right, mid)
self.change(n, right)
self.move(n-1, mid, left, right)
def change(self, n, right):
self.initStatus[n-1] = right
self.allStatus.append(self.initStatus[:])
最新文章
- minHash最小哈希原理
- Get a List of Keys From a Dictionary in Both Python 2 and Python 3
- golang自动导入postgresql脚本
- 启动 Eclipse 弹出“Failed to load the JNI shared library jvm.dll”错误
- HeapAlloc、GlobalAlloc和new等内存分配有什么区别么?
- 安装Ubuntu双系统系列——安装Ubuntu
- 其实没那么复杂!探究react-native通信机制
- 用JS动态创建登录表单,报了个小错误
- memcache的安装及管理
- DontDestroyOnLoad
- 总结了关于PHP xss 和 SQL 注入的问题(转)
- 优化DOM交互
- 查看Java包源码
- JS 严格模式
- 【 .NET 面向对象程序设计进阶》】【 《.NET 面向对象编程基础》】【《正则表达式助手》】
- 应用openvpn
- 设计模式之迭代器模式——Java语言描述
- python中单例模式的四种实现方式
- mogodb分片配置
- ProcessingElement.h