python - 3 壶 - 概念化解决方案的问题
问题描述
所以水壶问题非常有名。使用容量为 a 和 b 的 2 罐,产量为 d。壶没有标记。
所以我想尝试解决 3 个容量为 a、b 和 c 的罐子。
下面的代码显示了一个单一问题的解决方案,其中水罐的大小为:5、3 和 1,目标体积为 4。我列出了程序运行的所有可能组合 as possibleStates 只是因为它更容易解释我遇到的问题。
所以我的代码基本上只是在有空间的情况下将最大的水罐倒进第二大水罐,依此类推(它首先对较小的水罐起作用,例如:如果 5 是空的而 3 是满的,则 3 将进入 5)。显然,虽然(如解决方案解决方案所示:(5,0,0))这并不总是最好的方法。使用 (5,0,0) 最好的方法实际上是将 5 清空为 1。获得 4 需要 2 个步骤:(5,0,0) 和 (4,0,1)。
(5,3,0) 产生正确答案的唯一原因是因为 5 不能清空到水罐 2 中,所以尽可能地清空到水罐 1。
我的问题是,我如何对三个水壶问题进行编码,以确保我可以在进一步的步骤 (4,0,1) 中找到解决方案 (5,0,0),而不是遍历 (2,3,0).. ...?
事实是,我实际上有兴趣为任意数量的水壶编写解决方案,但无法从概念上解决如何做到这一点
请注意,我是一名初级程序员,对循环以外的函数了解不多。
global memory
global listSolution
capacity = (5,3,1)
#Set jug capacity
jug1Max = capacity[0]
jug2Max = capacity[1]
jug3Max = capacity[2]
def statusJugs(state):
#set jug status
jug1 = state[0]
jug2 = state[1]
jug3 = state[2]
if(jug1==4 or jug2==4 or jug3 ==4):
listSolution.append(state)
return True
#Has jug state been visited
if((jug1,jug2,jug3) in memory):
return False
memory[(jug1,jug2,jug3)] = 1
#empty jug1
if(jug1>0):
#empty jug1 into jug2
if(jug1+jug2<=jug2Max):
if(statusJugs((0,jug1+jug2,jug3))):
listSolution.append(state)
return True
else:
if(statusJugs((jug1-(jug2Max-jug2), jug2Max, jug3)) ):
listSolution.append(state)
return True
#empty jug1 into jug3
if(jug1+jug3<=jug3Max):
if( statusJugs((0,jug2,jug1+jug3))):
listSolution.append(state)
return True
else:
if( statusJugs((jug1-(jug3Max-jug3), jug2, jug3Max)) ):
listSolution.append(state)
return True
#empty jug2
if(jug2>0):
#empty jug2 into jug1
if(jug1+jug2<=jug1Max):
if( statusJugs((jug1+jug2, 0, jug3)) ):
listSolution.append(state)
return True
else:
if( statusJugs((jug1Max, jug2-(jug1Max-jug1), jug3)) ):
listSolution.append(state)
return True
#empty jug2 into jug3
if(jug2+jug3<=jug3Max):
if( statusJugs((jug1, 0, jug2+jug3)) ):
listSolution.append(state)
return True
else:
if( statusJugs((jug1, jug2-(jug3Max-jug3), jug3Max)) ):
listSolution.append(state)
return True
#empty jug3
if(jug3>0):
#empty jug3 into jug1
if(jug1+jug3<=jug1Max):
if( statusJugs((jug1+jug3, jug2, 0)) ):
listSolution.append(state)
return True
else:
if( statusJugs((jug1Max, jug2, jug3-(jug1Max-jug1))) ):
listSolution.append(state)
return True
#empty jug3 into jug2
if(jug2+jug3<=jug2Max):
if( statusJugs((jug1, jug2+jug3, 0)) ):
listSolution.append(state)
return True
else:
if( statusJugs((jug1, jug2Max, jug3-(jug2Max-jug2))) ):
listSolution.append(state)
return True
return False
possibleStates = [(5,3,1),(5,3,0),(5,0,1),(5,0,0),(0,3,1),(0,3,0),(0,0,1)]
for counter in range (0,len(possibleStates)):
listSolution = []
memory={}
initial_state = possibleStates[counter]
print("Solution for:",possibleStates[counter])
statusJugs(initial_state)
listSolution.reverse()
print (listSolution)
print ("Length of solution is:", len(listSolution))
print ("\n=======End of solution=======")
解决方案
这将是面向对象编程中的一个非常好的练习。我建议您花一些时间来了解这一点(使用 Python)。如果做得好,你最终会得到更简单的代码,更容易检查和理解。祝你好运!
推荐阅读
- azure-data-factory - 将 json blob 复制到 ADX 表
- java - 如何声明具有相同数据类型的多个参数?(爪哇)
- react-native - 禁用
触摸事件和交互 react-native-maps - android - 片段 exitTransition 与 enterTransition 重叠
- mysql - 与 ASP.NET 和 IIS 一起使用时,MySQL 临时表何时被删除?
- vb.net - 我可以在 Visual Basic 应用程序中手动设置随机化的种子吗
- azure-active-directory - 如何使用图形 API 向应用注册添加权限?
- swift - 使用应用程序语言中的国家/地区代码而不是电话区域设置语言检索国家/地区名称
- android - 如何将值从片段发送到视图模型(存储库)?
- android - 为模块运行仪器测试时禁用 Firebase 初始化